Cod sursa(job #529488)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 5 februarie 2011 11:33:19
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

ifstream aa("loto.in");
ofstream ss("loto.out");
struct aaa{
	int y,z[3];
};
int n,s,i,j,k,x[102],qq[8],nr,pas;
aaa w[1000001];
int cmp(aaa a,aaa b) {
	return a.y<b.y;
}
void citire();
void caut();
int main() {
	citire();
	for (i=1;i<=nr;++i) {
		caut();		
		if (w[j].y+w[i].y==s && j!=0) {
			qq[1]=w[i].z[0]; qq[2]=w[i].z[1]; qq[3]=w[i].z[2]; qq[4]=w[j].z[0]; qq[5]=w[j].z[1]; qq[6]=w[j].z[2];
			sort(&qq[1],&qq[7]);
			for (i=1;i<=6;++i)
				ss << x[qq[i]] << " ";
			return 0;
		}
	}
	ss << "-1";
	return 0;
}

void caut() {
	pas=1<<18;
	for (j=0;pas>0;pas>>=1) {
		while (j+pas<=nr && w[j+pas].y+w[i].y<=s)
			j+=pas;
	}
}

void citire() {
	aa >> n >> s;
	for (i=1;i<=n;++i) {
		aa >> x[i];
	}
	for (i=1;i<=n;++i) {
		for (j=i;j<=n;++j) {
			for (k=j;k<=n;++k) {
				w[++nr].y=x[i]+x[j]+x[k];
				w[nr].z[0]=i; w[nr].z[1]=j; w[nr].z[2]=k;
			}
		}
	}
	sort(&w[1],&w[nr+1],cmp);
}