Pagini recente » Istoria paginii runda/oji_simulare_2020_cl10 | Cod sursa (job #3168047) | Cod sursa (job #1522425) | Cod sursa (job #1225737) | Cod sursa (job #3154693)
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
struct sum {
int value, i, j, k;
bool operator < (const sum &other) const {
return value < other.value;
}
};
bool binarySearch(int s, vector <sum> &sums) {
int aux = 0;
for (int i = (1 << 20); i; i >>= 1) {
if (aux + i > (int) sums.size()) {
continue;
}
int poz = aux + i - 1;
if (sums[poz].value <= s) {
aux += i;
}
}
if (aux == 0 || sums[aux - 1].value != s) {
return 0;
}
cout << sums[aux - 1].i << ' ' << sums[aux - 1].j << ' ' << sums[aux - 1].k << ' ';
return 1;
}
int main() {
#ifdef LOCAL
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
#ifndef LOCAL
freopen("loto.in", "r", stdin);
freopen("loto.out", "w", stdout);
#endif
int n, s;
cin >> n >> s;
vector <int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
vector <sum> sums(n * n * n);
int ind = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
sums[ind].value = v[i] + v[j] + v[k];
sums[ind].i = v[i], sums[ind].j = v[j], sums[ind].k = v[k];
ind++;
}
}
}
sort(sums.begin(), sums.end());
bool found = 0;
for (int i = 0; i < (int) sums.size() && !found; i++) {
int otherSum = s - sums[i].value;
if (otherSum < 0) {
break;
}
if (binarySearch(otherSum, sums)) {
cout << sums[i].i << ' ' << sums[i].j << ' ' << sums[i].k;
found = 1;
}
}
if (!found) {
cout << -1;
}
return 0;
}