Cod sursa(job #1199639)

Utilizator sorin2kSorin Nutu sorin2k Data 20 iunie 2014 00:54:44
Problema Oite Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>
#include<utility>
#include<vector>
#include<cstdlib>
using namespace std;

int compar(const void *a, const void *b) {
	return *(int *)a - *(int *)b;
}

int main() {
	FILE *in = fopen("oite.in", "r");
	FILE *out = fopen("oite.out", "w");
	const int MOD = 66013;
	vector<pair<int, int>> h[MOD];
	int oite[1024];
	int n, l, i, j, sol = 0, mod;
	fscanf(in, "%d %d", &n, &l);

	for(i = 0; i < n; i++) {
		fscanf(in, "%d", oite+i);
	}
	qsort(oite, n, sizeof(int), compar);
	// insereaza in hash toate perechile de numere; cheia = suma lor
	for(i = 0; i < n; i++) {
		for(j = i + 1; j < n; j++) {
			h[(oite[i] + oite[j]) % MOD].push_back(make_pair(oite[i] + oite[j], i));
		}
	}
	// pt fiecare pereche de numere, cauta in hash l - suma lor si verifica
	// daca numerele sunt diferite
	for(i = 0; i < n; i++) {
		for(j = i + 1; j < n; j++) {
			int cauta = l - oite[i] - oite[j];
			if(cauta > 0) {
				mod = cauta % MOD;
				for(vector<pair<int, int>>::iterator it = h[mod].begin(); it != h[mod].end(); ++it) {
					if(it->first == cauta && it->second > j) {
						sol++;
					//	cout << i << " " << j << "    " << it->second << endl;
					}
				}
			}
		}
	}
	fprintf(out, "%d\n", sol);
	return 0;
}