Cod sursa(job #1257692)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 8 noiembrie 2014 09:33:04
Problema Loto Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.08 kb
#include <fstream>
#include <algorithm>
#define Ve 103
#define Ve2 1000003
using namespace std;
ifstream f("loto.in");
ofstream g("loto.out");
struct asd
{
    int s,n1,n2,n3;
}v[Ve2];
int a[Ve],n,s,k,i,j,r,s1;
void sortare(int left, int right) {
      int i = left, j = right;
      int pivot = v[(left + right) / 2].s;

      /* pivotul */
      while (i <= j) {
            while (v[i].s < pivot)
                  i++;
            while (v[j].s > pivot)
                  j--;
            if (i <= j) {

                  swap(v[i].s,v[j].s);
                  swap(v[i].n1,v[j].n1);
                  swap(v[i].n2,v[j].n2);
                  swap(v[i].n3,v[j].n3);
		//daca vrei sa mai sortezi un vector in functie de asta mai bagi un swap
                  i++;
                  j--;
            }
      };

      /* recursion */
      if (left < j)
            sortare( left, j);
      if (i < right)
            sortare( i, right);
}
int caut(asd b[1000],int x,int left, int right)
{   int mij;
    while(left <= right){
        mij = (left + right)/2;
        if(b[mij].s == x)
            return mij;
        else
        if(b[mij].s < x)
            left = mij +1;
        else
        if(b[mij].s > x)
            right = mij - 1;
    }
    return 0;
}
int main()
{
    f >> n >> s1;
    for(i = 1; i <= n; i++)
        f >> a[i];
    for(i = 1; i <= n; i++)
        for(j = 1; j <= n; j++)
            for(k = 1; k <= n; k++){
                v[++r].s = a[i] + a[j] + a[k];
                v[r].n1 = a[i];
                v[r].n2 = a[j];
                v[r].n3 = a[k];
                }
    sortare(1,r);
    int ok = 0;
    for(i = 1; i <= r/2; i ++){
        if(caut(v,s1-v[i].s,1,r)!=0){
            g << v[i].n1 <<" ";
            g << v[i].n2 <<" ";
            g << v[i].n3 <<" ";
            g << v[caut(v,s1-v[i].s,1,r)].n1<<" ";
            g << v[caut(v,s1-v[i].s,1,r)].n2<<" ";
            g << v[caut(v,s1-v[i].s,1,r)].n3;
            ok = 1;
            break;
        }
    }
    if(ok == 0) g<<-1;
    return 0;
}