Cod sursa(job #1606364)

Utilizator kassay_akosKassay Akos kassay_akos Data 20 februarie 2016 10:34:22
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
//#include <queue>
#include <algorithm>

#define One(x) (x % 256) ;
#define Two(x) ((x / 256 ) % 256) ;
#define Tre(x) ((x / 256) / 256 ) ; 

using namespace std;
const int nmax = 1000002;
int v[nmax][2], nr[101];
vector<pair<int, int>> w;
int n, s , m;

bool compare(const pair<int,int>  &a, const pair<int,int> &b) { return a.first < b.first; }

int cautareBinara1(int start ,int val)  {
	int el = start, ve = m - 1, mid;
	while (el < ve) {								// (1)
		mid = (el + ve) / 2;
		if (w[mid].first <= val)		el = mid + 1;		// (2)
		else							ve = mid;
	}
	mid = (el + ve) / 2;
	if (w[mid].first > val) mid--;
	
	if (w[mid].first == val) return mid;
	return -1;
}


int main(){
	freopen("loto.in", "r", stdin);
	freopen("loto.out", "w", stdout);
	scanf("%d %d", &n, &s);
	for (int i = 0; i < n; i++)
		scanf("%d ", &nr[i]);

	// generare 3 numere
	int ind = -1, cod , a = (1 << 16), b = (1 << 8) ;		// c = 1 => ++
	for (int k = 0; k < n; k++) {
		cod = k * a + k * b;
		for (int i = k; i < n; i++) {
			for (int j = i; j < n; j++, ind++) {
				w.push_back(make_pair(nr[k] + nr[i] + nr[j], cod + j));
			}
			cod += b;
		}
	}

	// sort 
	m = ind + 1;
	sort(w.begin(), w.end(), compare);

	// alege una si cauta perechea a + b = s

	int jumate = s / 2 + s % 2;
	bool q = false;
	int ii = 0,j;
	for (ii = 0; ( ii < n && w[0].first < jumate && !q ) ; ii++){
		j = cautareBinara1(ii, s - w[ii].first );
		if (j != -1) q = true;
	}
	 
	//
	if (j == -1)
		printf("%d ", -1);
	else {
		ii--;
		int r   = One(w[ii].second);
		int rr  = Two(w[ii].second);
		int rrr = Tre(w[ii].second);
		printf("%d %d %d ", nr[r], nr[rr] , nr[rrr] );

		r	= One(w[j].second);
		rr	= Two(w[j].second);
		rrr = Tre(w[j].second);
		printf("%d %d %d", nr[r], nr[rr], nr[rrr] );
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}