Cod sursa(job #2539536)

Utilizator eugen5092eugen barbulescu eugen5092 Data 5 februarie 2020 22:25:30
Problema Loto Scor 85
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream ci("loto.in");
ofstream cou("loto.out");
int n,m,r;
long long s;
int v[105],cautat[1000030];
int grupe[1000030];
void citire()
{
    int p=1;
    ci>>n>>s;
    m=n*n*n;
    r=3*n;
    for(int i=1; i<=n; i++)
    {
        ci>>v[i];

    }
    for(int i=1; i<=n; i++)
    {
        cautat[p++]=v[i];
        cautat[p++]=v[i];
        cautat[p++]=v[i];

    }
    int k=1;
    int i,j,l;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            for(l=1; l<=n; l++)
            {
                //cautat[k]=l;
                grupe[k++]=v[i]+v[j]+v[l];
            }
        }
    }

    sort(grupe+1,grupe+m+1);
    sort(cautat+1,cautat+3*n+1);


}

int cautare(int st,int dr,int k)
{
    int mij,sol;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(grupe[mij]>k )
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
            sol=mij;
        }
    }
return sol;

}
int cautare1(int st,int dr,int k)
{
    int mij,sol;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(cautat[mij]>k )
        {
            dr=mij-1;
        }
        else
        {
            st=mij+1;
            sol=mij;
        }
    }
return sol;

}


void rez()
{
int i,j,veri=0,x,y,t;
for(i=1;i<=m;i++){
    j=cautare(i,m+1,s-grupe[i] );
    if(grupe[j]+grupe[i]==s ){veri=1;break;}
}
if(veri==0){cou<<"-1";}else{
    x=grupe[i];
    y=grupe[j];
    for(int i=1;i<=r-1;i++){
            for(j=i+1;j<=r;j++){

                t=cautare1(j,r,x-cautat[i]-cautat[j]);
                if(cautat[t]+cautat[i]+cautat[j]==x ){
                    cou<<cautat[t]<<" "<<cautat[i]<<" "<<cautat[j]<<" ";
                j=r+1;i=r+1;
                }
            }
    }
    for(int i=1;i<=r-1;i++){
            for(j=i+1;j<=r;j++){

                t=cautare1(j,r,y-cautat[i]-cautat[j]);
                if(cautat[t]+cautat[i]+cautat[j]==y ){
                    cou<<cautat[t]<<" "<<cautat[i]<<" "<<cautat[j]<<" ";
                j=r+1;i=r+1;
                }
            }
    }

}


}

int main()
{
    citire();
    rez();
    return 0;
}