Cod sursa(job #1699235)

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