Cod sursa(job #2590134)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 27 martie 2020 15:57:46
Problema Loto Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iostream>
#define dim 103
#define pp 10201
using namespace std;
ifstream fin("loto.in");
ofstream fout("loto.out");
pair<int,int> r[dim*dim*dim];
int v[dim],n,s,i,sz;
int caut(int st,int dr,int x)
{
    ///caut fix val x
    while(st<=dr)
    {
        int mid=(st+dr)/2;
        if(r[mid].first>x)
        {
            dr=mid-1;
        }
        else if(r[mid].first<x)
        {
            st=mid+1;
        }
        else
        {
            return mid;
        }
    }
    return 0; /// nua fost gasit
}
void afis(int x)
{
    fout<<v[x%101]<<" "<<v[(x/101)%101]<<" "<<v[x/pp]<<" ";
}
int main()
{
    fin>>n>>s;
    for(i=1; i<=n; i++)
        fin>>v[i];
    for(int i=1; i<=n; i++)
    {
        for(int j=i; j<=n; j++)
            for(int k=j; k<=n; k++)
            {
                if(v[i]+v[j]+v[k]<s)
                {
                    r[++sz].first=v[i]+v[j]+v[k];
                    /// tin in baza 101 pt ca sunt indici pana la 100 si nu am nevoie de ei la afisat
                    r[sz].second=i*pp+j*101+k;
                }
            }
    }
    sort(r+1,r+sz+1);
    for(int it=1; s>=2*r[it].first&&it<=sz; it++)
    {
        int rez=caut(it,sz,s-r[it].first);
        if(rez)
        {
            afis(r[it].second);
            afis(r[rez].second);
            return 0;
        }
    }
    fout<<-1;
}