Cod sursa(job #1021859)

Utilizator Iustin_BulimarFMI Iustin Bulimar Iustin_Bulimar Data 4 noiembrie 2013 12:47:54
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <fstream>
#include<algorithm>

using namespace std;

ifstream cin("loto.in");
ofstream cout("loto.out");

struct suma
{
    int s, i, j, l;
};
short n;
int s, v[101], i, j, l, k;
suma x[1000001];
bool r;

void qsort(suma v[], int st, int dr)
{
      int i=st, j=dr;
      int piv = v[(st+dr)/2].s;
      while (i <= j)
      {
            while (v[i].s < piv) i++;
            while (v[j].s > piv) j--;
            if (i <= j)
            {
                  swap(v[i],v[j]);
                  i++;
                  j--;
            }
      }
      if (st < j) qsort(v, st, j);
      if (i < dr) qsort(v, i, dr);
}
int cautbin(suma v[], int n, int x)
{
    int st=1, dr=n, m;
    while(st<=dr)
    {   m=st+(dr-st)/2;
        if(v[m].s==x) return m;
        if(v[m].s>x) dr=m-1;
        else st=m+1;
    }
    return -1;
}
int main()
{
    cin>>n>>s;
    for(i=1; i<=n; i++) cin>>v[i];
    k=1;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            for(l=1; l<=n; l++)
            {
                x[k].s=v[i]+v[j]+v[l];
                if(x[k].s<s)
                {
                    x[k].i=i;
                    x[k].j=j;
                    x[k].l=l;
                    k++;
                }
            }
    k--;
    qsort(x, 1, k);
    for(i=1; i<=k; i++)
    {
        j=cautbin(x, k, s-x[i].s);
        if(j>0)
        {
            cout<<x[i].i<<" "<<x[i].j<<" "<<x[i].l<<" "<<x[j].i<<" "<<x[j].j<< " "<<x[j].l;
            r=1;
            break;
        }
    }
    if(r==0) cout<<-1;
    return 0;
}