Cod sursa(job #1721011)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 24 iunie 2016 01:25:53
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <functional>
#include <string>
#include <cstring>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <iomanip>
#define NMAX 105
#define MOD 2000003
#define INF 0x3f3f3f3f
#define pb push_back

using namespace std;

typedef pair<int, int> pii;

ifstream fin("loto.in");
ofstream fout("loto.out");

int v[NMAX];
set<int> gasit;
struct valori {
	int s,a,b,c;
};

vector<valori> val;
inline bool comp(valori A, valori B) {
	return A.s<B.s;
}

int main() {
	int n,s,i,j,k,ramas,st,dr,mid;

	fin>>n>>s;

	for(i=1;i<=n;++i) fin>>v[i];

	for(i=1;i<=n;++i)
		for(j=i;j<=n;++j)
			for(k=j;k<=n;++k)
				val.pb({v[i]+v[j]+v[k],i,j,k});

	sort(val.begin(),val.end(),comp);

	for(i=1;i<=n;++i) {
		for(j=i;j<=n;++j) {
			for(k=j;k<=n;++k) {
				st=0;
				dr=val.size()-1;
				ramas=s-v[i]-v[j]-v[k];
				while(st<=dr) {
					mid=(st+dr)/2;
					if(val[mid].s<ramas) st=mid+1;
					else if(val[mid].s>ramas) dr=mid-1;
					else {
						fout<<i<<' '<<j<<' '<<k<<' '<<val[mid].a<<' '<<val[mid].b<<' '<<val[mid].c;
						return 0;
					}
				}
			}
		}
	}

	fout<<-1;

	return 0;
}