Pagini recente » Cod sursa (job #2670626) | Cod sursa (job #1756660) | Cod sursa (job #999688) | Cod sursa (job #1313891) | Cod sursa (job #2743955)
#include <fstream>
#include <bits/stdc++.h>
#include <cstring>
#include <stack>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
struct trio
{
int x, y, z;
friend ostream& operator <<(ostream&, const trio&);
trio()
{
x = y = z = -1;
}
trio(int x, int y, int z)
{
this->x = x;
this->y = y;
this->z = z;
}
};
ostream& operator <<(ostream& out, const trio& t)
{
out << t.x << " " << t.y << " " << t.z << " ";
return out;
}
unordered_map<long long, trio> solution_sum;
vector <long long> nr, sums;
int N;
long long S, x, s_nr;
bool binarySearch(int left, int right, int val)
{
while (left < right)
{
int mid = (left + right) / 2;
if (sums[mid] == val) return true;
if (sums[mid] > val)
right = mid;
else if (sums[mid] < val) left = mid + 1;
}
return false;
}
void sumGen(int poz)
{
if (poz >= N)
return;
for (int i = poz; i < N; ++i)
for (int j = i; j < N; ++j)
{
if (!binarySearch(0, sums.size(), nr[poz] + nr[i] + nr[j]))
{
solution_sum[nr[poz] + nr[i] + nr[j]].x = nr[poz];
solution_sum[nr[poz] + nr[i] + nr[j]].y = nr[i];
solution_sum[nr[poz] + nr[i] + nr[j]].z = nr[j];
sums.push_back(nr[poz] + nr[i] + nr[j]);
}
}
sumGen(poz + 1);
}
int main()
{
fin >> N >> S;
for (int i = 0; i < N; ++i)
{
fin >> x;
nr.push_back(x);
}
sort(nr.begin(), nr.end());
if (S > nr[nr.size() - 1]*6 || S < nr[0]*6)
{
fout << -1;
return 0;
}
sumGen(0);
sort(sums.begin(), sums.end());
s_nr = sums.size();
int solution = -1, index_sum = 0;
while (solution == -1 && index_sum <= s_nr)
{
if (binarySearch(0, s_nr, S - sums[index_sum]))
{
fout << solution_sum[sums[index_sum]];
fout << solution_sum[ S - sums[index_sum]];
solution = 0;
}
index_sum++;
}
if (solution == -1)
fout << -1;
return 0;
}