Cod sursa(job #3121102)

Utilizator daristyleBejan Darius-Ramon daristyle Data 10 aprilie 2023 19:07:39
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <fstream>

using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

const int MOD_MAX = 666013;
const int N_MAX = 1e2;
const int TRIPLETE_MAX = N_MAX * N_MAX * N_MAX;

int v[N_MAX];

struct sum {
		int x, y, z;

		friend bool operator==(sum &a, sum &b) {
			return (a.x == b.x) && (a.y == b.y) && (a.z == b.z);
		}
};

class HashTable {
private:
		const int NIL = -1;
		int head[MOD_MAX];
		sum key[TRIPLETE_MAX];
		int nxt[TRIPLETE_MAX];
		int mod;
		int curr = 0;

public:
		HashTable(int x) {
			mod = x;

			for(int i = 0; i < mod; ++i)
				head[i] = NIL;
			for(int i = 0; i < N_MAX; ++i)
				nxt[i] = NIL;
		}

		int getkey(sum x) {
			int aux = x.x + x.y + x.z;
			while(aux < 0)
				aux += mod;
			return aux % mod;
		}

		int getkey(int x) {
			while(x < 0)
				x += mod;
			return x % mod;
		}

		void add(sum x) {
			int list = getkey(x);
			key[curr] = x;
			nxt[curr] = head[list];
			head[list] = curr;
			++curr;
		}

		bool find(int x, sum &a) {
			int list = getkey(x);
			int it = head[list];
			while(it != NIL && key[it].x + key[it].y + key[it].z != x)
				it = nxt[it];

			if(it != NIL)
				a = key[it];

			return it != NIL;
		}

		void erase(sum x) {
			int list = getkey(x);
			int ant = head[list], it = nxt[ant];
			if(key[ant] == x){
				head[list] = nxt[ant];
			}else{
				while(it != NIL && key[it] != x){
					ant = it;
					it = nxt[it];
				}

				if(it != NIL){
					nxt[ant] = nxt[it];
				}
			}
		}

		void eraseall(sum x) {
			int list = getkey(x);
			int ant = head[list], it;

			while(key[ant] == x)
				ant = nxt[ant];
			head[list] = ant;

			it = nxt[ant];
			while(it != NIL){
				if(key[it] == x)
					nxt[ant] = nxt[it];

				ant = it;
				it = nxt[it];
			}
		}
};

HashTable ht(MOD_MAX);

int main() {
	int n, s;
	fin >> n >> s;
	for(int i = 0; i < n; ++i)
		fin >> v[i];

	sum sum1, sum2, aux;
	sum1.x = -1;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			for(int k = 0; k < n; ++k){
				aux.x = v[i];
				aux.y = v[j];
				aux.z = v[k];
				ht.add(aux);
				if(ht.find(s - (v[i] + v[j] + v[k]), sum2))
					sum1 = aux;

			}

	if(sum1.x == -1)
		fout << "-1\n";
	else
		fout << sum1.x << ' ' << sum1.y << ' ' << sum1.z << ' ' << sum2.x << ' ' << sum2.y << ' ' << sum2.z << '\n';

	fin.close();
	fout.close();
	return 0;
}