Cod sursa(job #1715068)

Utilizator giotoPopescu Ioan gioto Data 9 iunie 2016 22:22:09
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <cstdio>
#include <bitset>
#include <algorithm>
using namespace std;

int mid,p,u,aux,n,i,sum,s,nr,a[102],sol[8];
struct elem{
    int s,a,b,c;
}su[1000002];
bool cmp(elem x,elem y){
    if(x.s>y.s)
        return 0;
    if(x.s==y.s&&(x.a>y.a||(x.a==y.a&&x.b>y.b)))
        return 0;
    return 1;
}
bitset <300000001> f;
int main()
{
    freopen("loto.in", "r", stdin);
    freopen("loto.out", "w", stdout);
    scanf("%d%d", &n, &s);
    for(i=1;i<=n;++i)
        scanf("%d", &a[i]);
    for(i=1;i<=n;++i){
        sum=a[i];
        for(int j=1;j<=n;++j){
            sum+=a[j];
            for(int t=1;t<=n;++t){
                f[sum+a[t]]=1;
                su[++nr].s=sum+a[t];
                su[nr].a=a[i];
                su[nr].b=a[j];
                su[nr].c=a[t];
            }sum-=a[j];
        }
    }
    sort(su+1,su+nr+1,cmp);
    for(i=1;i<=nr;++i){
        if(s-su[i].s>=0){
            if(f[s-su[i].s]==1){
                p=1,u=nr;
                aux=s-su[i].s;
                while(p<=u){
                    mid=(p+u)/2;
                    if(aux<su[mid].s) u=mid-1;
                    else if(aux>su[mid].s) p=mid+1;
                    else break;
                }
                sol[1]=su[mid].a;
                sol[2]=su[mid].b;
                sol[3]=su[mid].c;
                sol[4]=su[i].a;
                sol[5]=su[i].b;
                sol[6]=su[i].c;
                sort(sol+1,sol+7);
                for(i=1;i<=6;++i)
                    printf("%d ",sol[i]);
                return 0;
            }
        }
    }
    return 0;
}