Cod sursa(job #1601665)

Utilizator LuurAndrei Florea Luur Data 16 februarie 2016 09:56:40
Problema Loto Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int N;
long S, A[101], nr = 0;
struct DTA{
    int a, b, c;
    long  s;
};
DTA V[1000001];
bool cmp(long x, long y){
    return x < y;
}
bool sortOp(DTA x, DTA y){
   return x.s < y.s;
}
int BiSCh(int x) {
  int i, ps, 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(){
    FILE *in = fopen("loto.in", "r");
    FILE *out = fopen("loto.out", "w");
    fscanf(in, "%d%ld", &N, &S);
    for( int i = 1; i <= N ; ++i){
        fscanf(in, "%ld",&A[i]);
    }
    for(int i = 1; i <= N; ++i){
        for(int j = 1; j <= N; ++j){
            for(int k = 1; k <= N; ++k){
                DTA T; T.a = i; T.b = j; T.c = k; T.s = A[i]+A[j]+A[k];
                V[nr++] = T;
            }
        }
    }
    sort(V, V+N*N*N,sortOp);
    bool t = 1;
    for(int i = 1; i <= N && t; ++i){
        for(int j = 1; j <= N && t; ++j){
            for(int k = 1; k <= N && t; k++){
                    long FND = S - A[i]-A[j]-A[k];
                    long EX = BiSCh(FND);
                    if (V[EX].s == FND){
                        t = 0;
                        fprintf(out,"%ld %ld %ld %ld %ld %ld",A[i], A[j], A[k], A[V[EX].a], A[V[EX].b], A[V[EX].c]);
                    }
            }
        }
    }
    if (t) fprintf(out,"-1");
    return 0;
}