Cod sursa(job #1614656)

Utilizator aimrdlAndrei mrdl aimrdl Data 26 februarie 2016 00:57:53
Problema Loto Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <iostream>

#define MAX 1000005

using namespace std;

struct number {
	int val;
	int t1, t2, t3;
};

int in[100];
number v[MAX];
long long n, s;

void mergeSort (number *v, int n) {
	if (n == 1) return;
	
	mergeSort(v, n / 2);
	mergeSort(v + n / 2, n - n / 2);
	
	number *aux = new number[n];
	int i = 0, j = n / 2, k = 0;
	
	while (i < n / 2 && j < n) {
		if (v[i].val < v[j].val) {
			aux[k++] = v[i++];
		} else {
			aux[k++] = v[j++];
		}
	}
	
	while (i < n / 2) {
		aux[k++] = v[i++];
	}
	
	while (j < n) {
		aux[k++] = v[j++];
	}
	
	for (int i = 0; i < n; ++i) {
		v[i] = aux[i];
	}
	
	delete[] aux;
}

int search (number *v, int n, long long x) {
	int l = 0, r = n;
	
	while (r - l > 1) {
		int mid = l + (r - l) / 2;
		
		if (v[mid].val <= x) {
			l = mid;
		} else {
			r = mid;
		}
	}
	
	if (v[l].val == x) return l;
	
	return -1;
}

int genSum () {
	int pos = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			for (int k = i; k < n; ++k) {
				v[pos].val = in[i] + in[j] + in[k];
				v[pos].t1 = in[i];
				v[pos].t2 = in[j];
				v[pos].t3 = in[k];
				++pos;
			}
		}
	}
	
	return pos;
}

int main (void) {
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	
	cin >> n >> s;
	
	for (int i = 0; i < n; ++i) {
		cin >> in[i];
	}
	
	int max = genSum();
	
	mergeSort(v, max);
	
	for (int i = 0; i < max; ++i) {
		int l;
		l = search(v, max, s - v[i].val);
		if (l != -1) {
			cout << v[i].t1 << " " << v[i].t2 << " " << v[i].t3 << " ";
			cout << v[l].t1 << " " << v[l].t2 << " " << v[l].t3;
			return 0;
		}
	}
	
	cout << "-1";
	
	return 0;
}