Cod sursa(job #1435328)

Utilizator czlateaZlatea Cezar czlatea Data 12 mai 2015 21:22:51
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <algorithm>
using namespace std;

struct LOTO {
    int suma;
    char i1,i2,i3;
};
bool cmp (LOTO x, LOTO y)
{
    return x.suma<y.suma;
}
LOTO v[1000001];
int p[101];
int main() {
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    int i,j,k,n,s,a=1,x,d,t;
    scanf("%d%d",&n,&t);
    for(i=1; i<=n; i++)
        scanf("%d",&p[i]);
    for(i=1; i<=n; i++)
        for(j=i; j<=n; j++)
            for(k=j; k<=n; k++)
            {
                v[a].suma=p[i]+p[j]+p[k];
                v[a].i1=i;
                v[a].i2=j;
                v[a].i3=k;
                a++;
            }
    sort(v+1,v+a,cmp);
    for(i=1; i<=a-1; i++)
    {
        x=t-v[i].suma;
        s=1;
        d=a-1;
        while(s<=d) {
            if(v[(s+d)>>1].suma==x)
            {
                printf("%d %d %d %d %d %d",p[v[i].i1],p[v[i].i2],p[v[i].i3],p[v[(s+d)/2].i1],p[v[(s+d)/2].i2],p[v[(s+d)/2].i3]);
                return 0;
            }
            if(v[(s+d)>>1].suma<x)
                s=(s+d)/2+1;
            if(v[(s+d)/2].suma>x)
                d=(s+d)/2-1;

        }

    }
    printf("-1");
    return 0;
}