Cod sursa(job #1606529)

Utilizator kassay_akosKassay Akos kassay_akos Data 20 februarie 2016 12:36:17
Problema Loto Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 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{
	int 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 = -1;
	for (first = 0; (first < n && !q); first++){				// w[first].first <= jumate &&
		second = cautareBinara1(first, s - w[first].first);
		if (second != -1 && w[first].first + w[second].first == s) {
			q = true;
			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]);

		}
	}
	 
	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;
}