Cod sursa(job #608070)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 14 august 2011 20:38:10
Problema Loto Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.57 kb
#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "loto.in"
#define outfile "loto.out"
#define nMax 131

using namespace std;

vector < pair < pair <int, int>, pair <int, int> > > sums;
vector <int> v;
int n, s, firstGroupSum = -1;

void read() {
  scanf("%d %d\n", &n, &s);
  for(int i = 1; i <= n; ++i) {
    int x;
    scanf("%d", &x);
    v.push_back(x);
  }
}

int binSearch(int x) {
  int le = 0, ri = sums.size() - 1, res = 0;
  while(le <= ri) {
    int mi = (le + ri) >> 1;
    if(sums[mi].first.first == x) {
      res = mi;
      break;
    } else if(sums[mi].first.first < x)
      le = mi + 1;
    else ri = mi - 1;
  }
  return res;
}

void solve() {

  for(unsigned i = 0; i < v.size(); ++i)
    for(unsigned j = 0; j < v.size(); ++j)
      for(unsigned k = 0; k < v.size(); ++k)
        sums.push_back(make_pair(make_pair(v[i] + v[j] + v[k], v[i]), make_pair(v[j], v[k])));

  sort(sums.begin(), sums.end());

  for(unsigned i = 0; i < sums.size(); ++i)
    if(sums[binSearch(s - sums[i].first.first)].first.first == s - sums[i].first.first) {
      firstGroupSum = sums[i].first.first;
      break;
    }
}

void printGroup(int gr) {
  printf("%d %d %d ", sums[gr].first.second, sums[gr].second.first, sums[gr].second.second);
}

void write() {
  if(firstGroupSum < 0)
    printf("-1\n");
  else {
    printGroup(binSearch(firstGroupSum));
    printGroup(binSearch(s - firstGroupSum));
    printf("\n");
  }
}

int main() {
  freopen(infile, "r", stdin);
  freopen(outfile, "w", stdout);

  read();
  solve();
  write();

  fclose(stdin);
  fclose(stdout);
  return 0;
}