Cod sursa(job #1601757)

Utilizator LuurAndrei Florea Luur Data 16 februarie 2016 11:01:27
Problema Loto Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <fstream>
#define DMAX 1000001
#define TMAX 101
using namespace std;
typedef int  ll;
ifstream in("loto.in");
ofstream out("loto.out");
int n;
long S, a[TMAX], m;
bool t = 1;
struct myType{
    int a, b, c;
    ll s;
}v[DMAX];
bool cmp(ll x, ll y){
    return x < y;
}
bool sortOp(myType x, myType y){
   return x.s < y.s;
}
ll Search(ll x){
  ll i, ps, N = n*n*n;

  for (ps = 1; ps < N; ps <<= 1);
  for (i = 0; ps; ps >>= 1)
    if (i + ps < N && v[i + ps].s <= x) i += ps;
  if (v[i].s == x) return i;
  else return -1;
}
int main(){
    in >> n >> S;
    for(int i = 1; i <= n; i++){
        in >> a[i];
    }
    sort(a+1, a+n+1);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            for(int k = 1; k <= n; k++){
                long long STemp =a[i] + a[j] + a[k];
                if (STemp <= S){
                    v[m].a = a[i]; v[m].b = a[j]; v[m].c = a[k];
                    v[m].s = STemp; m++;
                }
            }
        }
    }
    ll N = m-1;
    sort(v, v+N, sortOp);
    for(int i = 1; i <= n && t; i++){
        for(int j = 1; j <= n && t; j++){
            for(int k = 1; k <= n && t; k++){
                ll c = S - a[i]-a[j]-a[k];
                ll r = Search(c);
                if (c >= 0){
                    if (r != -1){
                        out <<a[i]<<' '<<a[j]<<' '<<a[k]<<' '<<v[r].a<<' '<<v[r].b<<' '<<v[r].c<<'\n';
                        t = 0;
                    }
                }
            }
        }
    }
    if (t) out <<-1<<'\n';
    return 0;
}