Cod sursa(job #1182264)

Utilizator ErikHEErik Henning ErikHE Data 5 mai 2014 17:26:20
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include <iostream>
#include <fstream>
using namespace std;
long a[101];
long v[1000001],index[1000001];
long n,dim,l,baza,k;
        ifstream f("loto.in");
        ofstream g("loto.out");

void iofile()
{
        long long i;

        f>>n>>k;
        baza=(n+1);
        for (i=1;i<=n;i++)
                f>>a[i];

        f.close();
}


void repair(long i)
{
        long l,r,max,aux;
        l=(i*2);
        r=l+1;
        max=i;
        if ((l<=dim)&&(v[l]>v[i]))
                {
                        max=l;
                };
        if ((r<=dim)&&(v[r]>v[max]))
                {
                        max=r;
                };
        if (max!=i)
                {
                        aux=v[i];
                        v[i]=v[max];
                        v[max]=aux;
                        aux=index[i];
                        index[i]=index[max];
                        index[max]=aux;
                        repair(max);
                }
}


void build_heap()
{
        long i;
        for (i=(l/2);i>=1;i--)
            repair(i);
}


void heapsort()
{
        long i,aux;
        build_heap();
        for (i=l;i>=2;i--)
                {
                        aux=v[i];
                        v[i]=v[1];
                        v[1]=aux;
                        aux=index[i];
                        index[i]=index[1];
                        index[1]=aux;
                        dim--;
                        repair(1);
                }
}


void gen_perechi(void)
{
        long i,j,k;
        l=0;
        for (i=1;i<=n;i++)
                for (j=i;j<=n;j++)
                        for (k=j;k<=n;k++)
                                {
                                        l++;
                                        v[l]=a[i]+a[j]+a[k];
                                        index[l]=(baza*baza*i)+(baza*j)+k;
                                }
        dim=l;
}


void aflu_index(long x, long p1,long p2, long p3)//&
{
        p1=(x % baza);
        x=x/baza;
        p2=(x % baza);
        x=x/baza;
        p3=(x % baza);
}


void cauta_sol()
{
        long st,dr,p1,p2,p3,p4,p5,p6;
        st=1;
        dr=l;
        while ((st<=dr)&&((v[st]+v[dr])!=k))
                {
                    if ((v[st]+v[dr])>k)
                        dr--;
                    else
                        st++;
                }
        if (st<=dr)
                {
                        aflu_index(index[st],p1,p2,p3);
                        aflu_index(index[dr],p4,p5,p6);
                        g<<a[p1]<<"\t"<<a[p2]<<"\t"<<a[p3]<<"\t"<<a[p4]<<"\t"<<a[p5]<<"\t"<<a[p6];
                }
                else
                      g<<"-1";
        g.close();
}


int main()
{
        iofile();
        gen_perechi();
        heapsort();
        cauta_sol();
        return 0;
}