Mai intai trebuie sa te autentifici.
Cod sursa(job #412845)
Utilizator | Data | 6 martie 2010 17:33:41 | |
---|---|---|---|
Problema | Loto | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 1.96 kb |
#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;
}
*/
int bs(int val)
{
int li,ls,m;
li = 1;
ls = n;
while(li <= ls)
{
m = (li + ls) >> 1;
if(l[m].s == val)
return m;
else
if(l[m].s > val)
ls = m - 1;
else
li = m + 1;
}
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;
}