Cod sursa(job #1321103)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 18 ianuarie 2015 19:33:21
Problema Loto Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I Marime 1.58 kb
#include<stdio.h>
#include<stdlib.h>
#define N 1000010
struct semiloto
{
    long s;
    long a,b,c;
};
long n,nr;
long suma;
long val[N];
long poz[N];
semiloto v[N];

void read()
{
    scanf("%ld%ld",&n,&suma);
    long i;
    for(i=1;i<=n;i++)
    {
        scanf("%ld",&val[i]);
    }
    long j,k;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
            for(k=j;k<=n;k++)
            {
                v[++nr].s=val[i]+val[j]+val[k];
                v[nr].a=val[i];
                v[nr].b=val[j];
                v[nr].c=val[k];
                poz[nr]=nr;
            }
}


int compar(const void *p, const void *q)
{
    long x=*(long *)p;
    long y=*(long *)q;
    if(v[x].s<v[y].s)
        return -1;
    if(v[x].s>v[y].s)
        return 1;
    return 0;
}

long cautare(long x)
{
    long st=1,dr=nr,mid;
    while(st!=dr)
    {
        mid=(st+dr)>>1;//pericol daca st+dr poate depasi long -> ((dr-st)>>1)+st
        if(x<=v[poz[mid]].s)
            dr=mid;
        else
            st=mid+1;
    }
    if(x==v[poz[st]].s)
        return poz[st];
    return 0;
}

void solve()
{
    long i,p;
    for(i=1;i<=nr;i++)
    {
        p=cautare(suma-v[poz[i]].s);
        if(p)
        {
            printf("%ld %ld %ld %ld %ld %ld\n",v[poz[i]].a,v[poz[i]].b,v[poz[i]].c,v[p].a,v[p].b,v[p].c);
            return;
        }
    }
    printf("-1\n");
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);
    read();
    qsort(poz+1,nr,sizeof(poz[0]),compar);
    solve();
    return 0;
}