Cod sursa(job #761136)

Utilizator visanrVisan Radu visanr Data 24 iunie 2012 21:39:26
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.03 kb
#include <cstdio>
#include <cstdlib>
using namespace std;

#define max 1000000

int v[max][4];
int N, S, vv[100];

int BS(int val);

int partition(int start, int end)
{
    int pivot = v[start][0], i = start, j = end, k;
    while(i <= j)
    {
            while(v[i][0] < pivot) i++;
            while(v[j][0] > pivot) j--;
            if(i <= j)
            {
                 int aux[4];
                 for(k = 0; k < 4; k++) aux[k] = v[i][k];
                 for(k = 0; k < 4; k++) v[i][k] = v[j][k];
                 for(k = 0; k < 4; k++) v[j][k] = aux[k];
                 i ++;
                 j --;
            }
    }
    return i;
}

void QS(int start, int end)
{
     if(start < end)
     {
              int m = partition(start, end);
              QS(start, m - 1);
              QS(m, end);
     }
}

int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    int i, j, k, cnt = 0;
    scanf("%i %i", &N, &S);
    for(i = 0; i < N; i++) scanf("%i", &vv[i]);
    for(i = 0; i < N; i++)
          for(j = 0; j < N; j++)
                for(k = 0; k < N; k++)
                      {v[cnt][0] = (vv[i] + vv[j] + vv[k]); v[cnt][1] = i; v[cnt][2] = j; v[cnt][3] = k; cnt ++;}
    N = N * N * N;
    QS(0, N - 1);
    bool ok = false;
    for(i = 0; i < N; i++)
    {
          if(BS(S - v[i][0]) != -1)
          {
                  int pos = BS(S - v[i][0]);
                  for(j = 1; j <= 3; j++) printf("%i ", vv[v[i][j]]);
                  for(j = 1; j <= 3; j++) printf("%i ", vv[v[pos][j]]);
                  printf("\n");
                  ok = true;
                  break;
          }
    }
    if(!ok) printf("-1\n");
    scanf("%i", &i);
    return 0;
}

int BS(int val)
{
    int m, left = 0, right = N - 1;
    while(left <= right)
    {
               int m = (left + right) / 2;
               if(v[m][0] == val) return m;
               if(v[m][0] < val) left = m + 1;
               else right = m - 1;
    }
    return -1;
}