Pagini recente » Monitorul de evaluare | Cod sursa (job #1765979) | Cod sursa (job #2093695) | Cod sursa (job #2453314) | Cod sursa (job #412844)
Cod sursa(job #412844)
#include<fstream>
#include<algorithm>
#define NMAX 500000
using namespace std;
ifstream fin ("loto.in");
ofstream fout ("loto.out");
int m,n,v[101];
long long S,sum;
typedef struct{
int i,j,k,s;
}loto;
loto l[NMAX];
void sift(loto l[],int n , int k)
{
int son;
loto aux;
do
{
son = 0;
if( 2*k <=n )
{
son = 2*k;
if(2*k+1 <= n && l[2*k+1].s > l[2*k].s)
son = 2*k+1;
if(l[son].s <= l[k].s)
son = 0;
}
if(son)
{
aux = l[son];
l[son] = l[k];
l[k] = aux;
k = son;
}
}while(son);
}
void build_heap(int n)
{
int i;
for(i = n/2 ; i ; i--)
sift(l,n,i);
}
void heapsort()
{
int i;
loto aux;
for(i = n ; i >= 2 ; i--)
{
aux = l[i];
l[i] = l[1];
l[1] = aux;
sift(l,i-1,1);
}
}
int bs(int val)
{
int i , step;
for( step = 1 ; step < n ; step <<=1 );
for(i = 0 ; step ; step >>=1 )
if( i + step < n && l[ i + step].s <= val )
i += step;
if(l[i].s == val )
return i;
else
return 0;
}
void make_sum()
{
int i , j ,k;
for(i = 1 ; i <= m ; i++ )
for(j = i ; j <= m ; j++)
for(k = j ; k <= m ; k++)
{
l[++n].s = v[i] + v[j] + v[k];
l[n].i = i;
l[n].j = j;
l[n].k = k;
}
}
int main ()
{
int i;
fin >> m >> S;
for( i = 1 ; i <= m ; i++)
fin >> v[i] ;
n = 0;
make_sum();
build_heap(n);
heapsort();
int poz;
for(i = 1 ; i <= n ; i++ )
{
sum = S - l[i].s;
poz = bs(sum);
if(poz)
{
fout << v[l[i].i] <<' ' << v[l[i].j] <<' ' << v[l[i].k] <<' ' << v[l[poz].i] <<' ' << v[l[poz].j] <<' ' << v[l[poz].k] << '\n';
return 0;
}
}
fout << "-1\n" ;
fin.close();
fout.close();
return 0;
}