Cod sursa(job #1699239)

Utilizator Bodo171Bogdan Pop Bodo171 Data 6 mai 2016 19:23:44
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <iostream>
#include<fstream>
#include<algorithm>
#define nm 1000005
using namespace std;
int a[105],i,j,p,u,m,w,nr,k,s,n,sum;
struct tip
{
    int s,x,y,z;
}v[nm];
bool comp(tip a,tip b)
{
    return a.s<b.s;
}
int finds(int key)
{
    p=0;u=nr+1;
    while(u-p>1)
    {
        m=(p+u)/2;
        if(v[m].s<key) p=m;
        else u=m;
    }
    if(u==nr+1||v[m].s!=key) return -1;
    return m;
}
int main()
{
    ifstream f("loto.in");
    ofstream g("loto.out");
    f>>n>>sum;
    for(i=1;i<=n;i++)
        f>>a[i];
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
         for(k=j;k<=n;k++)
    {
        ++nr;
        v[nr].s=a[i]+a[j]+a[k];
        v[nr].x=a[i];
        v[nr].y=a[j];
        v[nr].z=a[k];
    }
    sort(v+1,v+nr+1,comp);
    v[0].s=-(1<<30);
    v[nr+1].s=(1<<30);
    for(i=1;i<=nr&&v[i].s<=sum;i++)
    {

        w=finds(sum-v[i].s);
        if(w!=-1)
        {

            g<<v[i].x<<' '<<v[i].y<<' '<<v[i].z<<' '<<v[w].x<<' '<<v[w].y<<' '<<v[w].z;
            return 0;
        }
    }
    g<<-1;
    return 0;
}