Cod sursa(job #1467482)

Utilizator OpportunityVlad Negura Opportunity Data 3 august 2015 14:51:40
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define pivot 2234
using namespace std;

ifstream fi("loto.in");
ofstream fo("loto.out");

struct cell {
 long nr1, nr2, sum;
}c = {0};

long n,s,sn,a[101];
cell h[1000001];

bool comp(cell c1, cell c2) {
 return c1.sum < c2.sum;
}

cell exists(long nr, long l, long r) {
 if (l==r) {
  if (h[l].sum == nr) {
   return h[l];
  } else {
   return c;
  }
 }
 if (nr > h[(l+r)/2].sum) {
  return exists(nr, (l+r)/2+1, r);
 } else {
  return exists(nr, l, (l+r)/2);
 }
}


int main() {

 fi >> n >> s;
 for (int i = 0; i<n; i++) {
  fi >> a[i];
 }

 for (int i = 0; i<n; i++) {
  for (int j = 0; j<n; j++) {
   for (int k = 0; k<n; k++) {
    cell aux;
    aux.sum = a[i]+a[j]+a[k];
    aux.nr1 = a[i];
    aux.nr2 = a[j];
    h[sn++] = aux;
   }
  }
 }

    sort(h,h+sn,comp);

 for (int i = 0; i<n; i++) {
  for (int j = 0; j<n; j++) {
   for (int k = 0; k<n; k++) {
    if (a[i]+a[j]+a[k] > s) continue;
    cell x = exists(s-a[i]-a[j]-a[k],0,sn-1);
    if (x.sum) {
     fo << x.nr1 << ' ' << x.nr2 << ' ' << (x.sum-x.nr1-x.nr2) << ' ' << a[i] << ' ' << a[j] << ' ' << a[k];
     return 0;
    }
   }
  }
 }
 
 fo << -1;

 return 0;
}