Recently I have solved this problem and here is my solution:
int n, target;
vector<int> values;
vector<tuple<int, int, int>> paired_sums;
int main() {
cin >> n >> target;
values.resize(n);
for(int &v: values) {
scanf("%d", &v);
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
paired_sums.push_back(make_tuple(values[i] + values[j], i, j));
}
}
sort(paired_sums.begin(), paired_sums.end());
int lo = 0, hi = paired_sums.size() - 1;
while(lo < hi) {
int lo_value, lo_i, lo_j;
int hi_value, hi_i, hi_j;
tie(lo_value, lo_i, lo_j) = paired_sums[lo];
tie(hi_value, hi_i, hi_j) = paired_sums[hi];
if(1LL * lo_value + hi_value > target) {
hi--;
}
else if(1LL * lo_value + hi_value < target) {
lo++;
}
else {
set<int> indexs;
indexs.insert(lo_i);
indexs.insert(lo_j);
indexs.insert(hi_i);
indexs.insert(hi_j);
if(indexs.size() != 4) {
break;
}
else {
printf("%d %d %d %d", ++lo_i, ++lo_j, ++hi_i, ++hi_j);
exit(0);
}
}
}
printf("IMPOSSIBLE");
}
After solving this I have come to realize that my code might not pass one test case. Suppose this paired_sums vector has some values ***** 2 3 3 4 **** (here * means other values). the target value is 6. so 2 + 4 is a potential answer. But if their indexes are not unique my code will say IMPOSSIBLE (breaks from the while loop). however, 3 + 3 is also and a potential answer and if the there indexes are unique my code will fail. But this code is accepted. I wonder how!!! Can anyone explain? Thanks in advance.