Perfect Trio
Time limit: 1 s.
Memory limit: 256 MB
Three friends are playing a coordination game called “Perfect Trio”.
They are given a list of celebrities, where the \(i\)-th celebrity has exactly \(A_i\) followers. To win the game, they must choose exactly three distinct celebrities such that the sum of their follower counts is exactly \(S\).
Determine whether such a trio exists. If it does, output any valid three follower counts. Otherwise, output \(-1\).
Input
The first line contains two integers \(N\) and \(S\) — the number of celebrities and the target total number of followers.
The second line contains \(N\) integers \(A_1, A_2, \ldots, A_N\), where \(A_i\) is the follower count of the \(i\)-th celebrity.
It is guaranteed that \(3 \le N \le 10000\) and \(0 \le A_i, S \le 7 \cdot 10^8\).
Output
If there exist three distinct celebrities whose follower counts sum to \(S\), print any three such values.
Otherwise, print \(-1\).
Scoring
| Subtask | Additional constraints | Points |
|---|---|---|
| \(1\) | \(N = 3\) | \(7\) |
| \(2\) | \(N = 4\) | \(8\) |
| \(3\) | \(N = 5\) | \(9\) |
| \(4\) | \(N \le 100\) | \(26\) |
| \(5\) | \(N \le 10000\), \(S \le 100000\) | \(31\) |
| \(6\) | \(N \le 10000\), \(S \le 7 \cdot 10^8\) | \(19\) |
Examples
Input
3 6
1 2 3
Output
1 2 3
Input
6 1000
182 587 952 374 39 741
Output
39 374 587
Note
In the sample, the three chosen follower counts are \(374\), \(39\), and \(587\). Their sum is \[374 + 39 + 587 = 1000.\]
Note that:
- the three chosen celebrities must be distinct;
- if there are multiple valid answers, you may print any of them;
- the values may be printed in any order.
Solution
Sort the follower counts. Fix the first celebrity at position \(i\), then use two pointers to find two later values whose sum is \(S-A_i\).
If the current sum is too small, move the left pointer right. If it is too large, move the right pointer left. The three array positions are always distinct, even when some follower counts are equal.
The complexity is \(O(N^2)\) time and \(O(1)\) extra memory apart from the sorted array.
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
long long target;
cin >> n >> target;
vector<long long> a(n);
for (long long& value : a) {
cin >> value;
}
sort(a.begin(), a.end());
for (int i = 0; i < n - 2; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
long long sum = a[i] + a[left] + a[right];
if (sum == target) {
cout << a[i] << ' ' << a[left] << ' ' << a[right] << '\n';
return 0;
}
if (sum < target) {
left++;
} else {
right--;
}
}
}
cout << -1 << '\n';
}