Cod sursa(job #2577878)

Utilizator mirceamaierean41Mircea Maierean mirceamaierean41 Data 10 martie 2020 00:05:39
Problema Loto Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.33 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

vector < pair<int, int> > v;
vector <int> f;
int n, s, a;

inline int binary_search(int val)
{
	int st = 0, dr = f.size() - 1, mij;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (v[mij].first == val) return mij;
		if (v[mij].first < val) st = mij + 1;
		else dr = mij - 1;
	}
	return -1;
}

int main()
{
	fin >> n >> s;
	for (int i = 0; i < n; ++i)
	{
		fin >> a;
		f.push_back(a);
		for (int j = 0; j < f.size(); ++j)
			v.push_back({ f[j] + a, f[j] });
	}
	sort(v.begin(), v.end());

	bool ok = false;
	int i1, i2, i3;

	for (size_t i = 0; i < v.size(); ++i)
	{
		for (size_t j = 0; j <= i; ++j)
		{
			int val = s - v[i].first - v[j].first;
			int ind = binary_search(val);
			if (ind != -1)
			{
				ok = true;
				i1 = i;
				i2 = j;
				i3 = ind;
			}
		}
	}
	if (ok == false) fout << "-1";
	else
	{
		multiset <int> s;
		s.insert(v[i1].second);
		s.insert(v[i1].first - v[i1].second);
		s.insert(v[i2].second);
		s.insert(v[i2].first - v[i2].second);
		s.insert(v[i3].second);
		s.insert(v[i3].first - v[i3].second);
		set <int> ::iterator it;
		for (it = s.begin(); it != s.end(); ++it)
			fout << *it << " ";
	}
	return 0;
}