Cod sursa(job #648363)

Utilizator ELHoriaHoria Cretescu ELHoria Data 13 decembrie 2011 11:50:39
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.35 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#define st first
#define nd second
#define MP make_pair

using namespace std;

int S , N, v[101] ,l[6] , lg;
pair<int, pair<pair<short,short>,short > >  sume[1000000];

struct cmp{ bool operator() (const pair<int, pair<pair<short,short>,short > > &x,const pair<int, pair<pair<short,short>,short > > &y)
	const { return x.st < y.st;}
};

int binarysearch(int val)
{
	int l = 0 , r = lg , m;
	while(l < r)
	{
		m = (l +r)>>1;
		if(sume[m].st == val) return m;
		if(sume[m].st > val) r = m - 1;
		else
			l = m + 1;
	}
	return -1;
}

void read_data()
{
	freopen("loto.in","r",stdin);
	freopen("loto.out","w",stdout);
	scanf("%d%d",&N,&S);
	for(int i=0;i<N;++i) 
		scanf("%d",&v[i]);
}

int main()
{
	
	read_data();
	sort(v,v+N);
	for(int i = 0;i<N;++i)
		for(int j = 0;j<N;++j)
			for(int k = 0;k<N;++k)
				sume[lg++] = MP(v[i] + v[j] + v[k],MP(MP(i,j),k));
	sort(sume,sume+lg,cmp());
	int pos;
	for(int i = 0;i<lg;++i)
	{
		if( (pos = binarysearch(S-sume[i].st))!=-1)
		{
			l[0] = v[sume[i].nd.st.st] , l[1] = v[sume[i].nd.st.nd] , l[2] = v[sume[i].nd.nd];
			l[3] = v[sume[pos].nd.st.st] , l[4] = v[sume[pos].nd.st.nd] , l[5] = v[sume[pos].nd.nd];
			sort(l,l+6);
			for(int j=0;j<6;++j)printf("%d ",l[j]);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}