Cod sursa(job #905783)

Utilizator ELHoriaHoria Cretescu ELHoria Data 6 martie 2013 10:14:37
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.4 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, VMAX = int(1e8);
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;
	S += VMAX*6;
	for(int i = 1;i <= n;i++) {
		cin>>v[i];
		v[i] += VMAX;
	}
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= n;j++) {
			for(int k = 1;k <= n;k++) {
				int sum = v[i] + v[j] + v[k], q;
				if(S > sum && (q = query(S - sum)) != -1) {
					int r[8] = {v[i],v[j],v[k],v[q & 127],v[(q>>7) & 127], v[(q>>14) & 127],0,0};
					sort(r,r + 6);
					for(int w = 0;w < 6;w++) {
						cout<<r[w] - VMAX<<" ";
					}
					return 0;
				}
				if(query(sum) == -1) {
					insert(mp(sum,getState(i,j,k)));
				}
			}
		}
	}
	cout<<-1;
    return 0;
}