Cod sursa(job #905771)

Utilizator ELHoriaHoria Cretescu ELHoria Data 6 martie 2013 10:01:22
Problema Loto Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define getState(a,b,c) (a + (b<<7) + (c<<14))
#define x first
#define y second
#define mp make_pair

using namespace std;

ifstream cin("loto.in");
ofstream cout("loto.out");

const int nmax = 102, mod = 667013;
int n, S;
int v[nmax];
vector< pair<int,int> > h[mod];

inline void insert(const pair<int,int> &val) {
	int hashCode = val.x < mod ? val.x : val.x%mod;
	if(find(h[hashCode].begin(),h[hashCode].end(),val) == h[hashCode].end()) {
		h[hashCode].push_back(val);
	}
}

inline int query(const int &val) {
	int hashCode = val < mod ? val : val%mod;
	for(vector< pair<int,int> >::const_iterator it = h[hashCode].begin();it != h[hashCode].end();it++) {
		if((*it).x == val) {
			return (*it).y;
		}
	}
	return -1;
}

int main()
{
	cin>>n>>S;
	for(int i = 1;i <= n;i++) {
		cin>>v[i];
	}
	sort(v + 1,v + n + 1);
	int r[8];
	for(int i = 1;i <= n;i++) {
		for(int j = i;j <= n;j++) {
			for(int k = i;k <= n;k++) {
				int sum = v[i] + v[j] + v[k];
				int q;
				if(S > sum && (q = query(S - sum)) != -1) {
					r[0] = 0;
					r[++r[0]] = v[i];
					r[++r[0]] = v[j];
					r[++r[0]] = v[k];
					r[++r[0]] = v[q & 127];
					r[++r[0]] = v[(q>>7) & 127];
					r[++r[0]] = v[(q>>14) & 127];
					sort(r + 1,r + r[0] + 1);
					for(int w = 1;w <= 6;w++) {
						cout<<r[w]<<" ";
					}
					return 0;
				}
				insert(mp(sum,getState(i,j,k)));
			}
		}
	}
	cout<<-1;
    return 0;
}