Pagini recente » Cod sursa (job #2398199) | Cod sursa (job #2967313) | Cod sursa (job #71855) | Cod sursa (job #2901173) | Cod sursa (job #174337)
Cod sursa(job #174337)
#include<stdio.h>
#define INPUT "loto.in"
#define OUTPUT "loto.out"
#define NMAX 1000001
FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");
int N;
long S, a[ NMAX ], sum[ NMAX ][ 5 ];
void readValues()
{
fscanf(fin, "%d %ld", &N, &S);
for(int i = 1; i <= N; ++i)
fscanf(fin, "%ld", &a[ i ]);
}
void setInitial()
{
long cont = 1;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= N; ++j)
for(int k = 1; k <= N; ++k)
{
sum[ cont ][ 0 ] = a[ i ] + a[ j ] + a[ k ];
sum[ cont ][ 1 ] = a[ i ];
sum[ cont ][ 2 ] = a[ j ];
sum[ cont++ ][ 3 ] = a[ k ];
}
}
inline void exchange(long& val1, long& val2)
{
val1 = val1 + val2;
val2 = val1 - val2;
val1 = val1 - val2;
}
void quickSort(long st, long dr)
{
long l = st, m = dr;
while( l != m)
{
if( ( l < m && sum[ l ][ 0 ] > sum[ m ][ 0 ]) || ( l > m && sum[ l ][ 0 ] < sum[ m ][ 0 ] ) )
{
exchange( sum[ l ][ 0 ], sum[ m ][ 0 ]);
exchange( sum[ l ][ 2 ], sum[ m ][ 1 ]);
exchange( sum[ l ][ 3 ], sum[ m ][ 2 ]);
exchange( sum[ l ][ 4 ], sum[ m ][ 3 ]);
exchange( l, m);
if(l < m)
--m;
else
++m;
}
else
if(l < m)
--m;
else
++m;
}
if(l != st) quickSort( st, l - 1);
if(l != dr) quickSort( l + 1, dr);
}
void printSolution(int code, long fValue, long sValue)
{
if(code == 1)
{
fprintf(fout, "%ld %ld %ld ", sum[ fValue ][ 1 ], sum[ fValue ][ 2 ], sum[ fValue ][ 3 ]);
fprintf(fout, "%ld %ld %ld\n", sum[ sValue ][ 1 ], sum[ sValue ][ 2 ], sum[ sValue ][ 3 ]);
}
else
fprintf(fout, "-1\n");
}
void binSearch()
{
int Valid = 1;
long st = 1, dr = N * N * N;
while( st < dr && Valid)
{
if(sum[ st ][ 0 ] + sum[ dr ][ 0 ] == S)
{
printSolution(1, st, dr);
return;
}
while(sum[ st ][ 0 ] + sum[ dr ][ 0 ] > S)
--dr;
while(sum[ st ][ 0 ] + sum[ dr ][ 0 ] < S)
++st;
}
printSolution(-1,0,0);
}
int main()
{
readValues();
setInitial();
quickSort(1, N * N * N);
binSearch();
fclose(fin);
fclose(fout);
return 0;
}