Cod sursa(job #1606502)

Utilizator kassay_akosKassay Akos kassay_akos Data 20 februarie 2016 12:22:38
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 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 ) ; 

struct mytype{
	char a, b, c; 
};

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

bool compare(const pair<int, mytype>  &a, const pair<int, mytype> &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) return 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-somes numere
	for (int k = 0; k < n; k++) 
		for (int i = k; i < n; i++) 
			for (int j = i; j < n; j++) {
				mytype e = { k, i, j };
				w.push_back(make_pair(nr[k] + nr[i] + nr[j], e));
			}
	
	// sort 
	m = w.size();
	sort(w.begin(), w.end(), compare);

	int jumate = s / 2 + s % 2;
	bool q = false;
	int first = 0,second;
	for (first = 0; (first < n && w[first].first <= jumate && !q); first++){
		second = cautareBinara1(first, s - w[first].first);
		if (second != -1) q = true;
	}
	 
	if (second == -1)
		printf("%d ", -1);
	else {
		first--;
		printf("%d %d %d %d %d %d", nr[w[first ].second.a], nr[w[first ].second.b], nr[w[first ].second.c],
									nr[w[second].second.a], nr[w[second].second.b], nr[w[second].second.c]);
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}