Cod sursa(job #486055)

Utilizator claudiumihailClaudiu Mihail claudiumihail Data 20 septembrie 2010 13:26:14
Problema Loto Scor 85
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include<fstream>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

#define MAXN 1000001
typedef unsigned int uint32;

struct Parts
{
	Parts()
	{}
	Parts(const uint32 ii, const uint32 jj, const uint32 kk) : i(ii), j(jj)//, k(kk)
	{
		sum=i+j+kk;
	}
	uint32 sum,i,j;
};

Parts sums[MAXN];

struct Comparator
{
	inline bool operator() (const uint32 a, const uint32 b) const
	{
		return a<b;
	}
};

struct ComparatorSums
{
	inline bool operator() (const Parts& a, const Parts& b) const
	{
		return a.sum<b.sum;
	}
};

unsigned int BinSearch(const Parts* v, const unsigned int num, const unsigned int val)
{
	unsigned int step,i;
	for(step=1; step<num; step<<=1) ;
	for(i=0; step; step>>=1)
		if(i+step<num && v[i+step].sum<=val)
			i+=step;
	return i;
}

int main()
{
	int n,x;
	long long S;
	fstream fin("loto.in", fstream::in);
	fstream fout("loto.out", fstream::out);
	vector<uint32> v;
	//vector<Parts> sums;
	//Comparator com;
	ComparatorSums coms;
	
	fin>>n>>S;
	//cout<<n<<" "<<S<<endl;
	for(int i=0; i<n; ++i)
	{
		fin>>x;
		v.push_back(x);
	}
	fin.close();
	//sort(v.begin(), v.end(), com);
	
	/*for(int i=0; i<n; ++i)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;*/
	
	unsigned int num=0;
	for(int i=0; i<n; ++i)
	{
		for(int j=0; j<n; ++j)
		{
			for(int k=0; k<n; ++k)
			{
				//sums.push_back(Parts(v[i],v[j],v[k]));
				sums[num++]=Parts(v[i],v[j],v[k]);
			}
		}
	}

	sort(sums, sums+num, coms);
	
	/*for(int i=0; i<(int)num; ++i)
	{
		cout<<sums[i].sum<<" ";
	}
	cout<<endl;*/

	for(int i=0; i<(int)num; ++i)
	{
		//cout<<sums[i].sum<<" ";
		const unsigned int index=BinSearch(sums+i,num-i,S-sums[i].sum)+i;
		if(index<num && sums[index].sum==S-sums[i].sum)
		{
			fout<<sums[i].i<<" "<<sums[i].j<<" "<<sums[i].sum-(sums[i].i+sums[i].j)<<" "<<sums[index].i<<" "<<sums[index].j<<" "<<
			sums[index].sum-(sums[index].i+sums[index].j)<<endl;
			
			fout.close();
			return 0;
		}
	}
	fout<<-1<<endl;

	fout.close();
	return 0;
}