Pagini recente » Cod sursa (job #3234726) | Borderou de evaluare (job #596500) | Borderou de evaluare (job #508726) | Cod sursa (job #1261613) | Cod sursa (job #761136)
Cod sursa(job #761136)
#include <cstdio>
#include <cstdlib>
using namespace std;
#define max 1000000
int v[max][4];
int N, S, vv[100];
int BS(int val);
int partition(int start, int end)
{
int pivot = v[start][0], i = start, j = end, k;
while(i <= j)
{
while(v[i][0] < pivot) i++;
while(v[j][0] > pivot) j--;
if(i <= j)
{
int aux[4];
for(k = 0; k < 4; k++) aux[k] = v[i][k];
for(k = 0; k < 4; k++) v[i][k] = v[j][k];
for(k = 0; k < 4; k++) v[j][k] = aux[k];
i ++;
j --;
}
}
return i;
}
void QS(int start, int end)
{
if(start < end)
{
int m = partition(start, end);
QS(start, m - 1);
QS(m, end);
}
}
int main()
{
freopen("loto.in", "r", stdin);
freopen("loto.out", "w", stdout);
int i, j, k, cnt = 0;
scanf("%i %i", &N, &S);
for(i = 0; i < N; i++) scanf("%i", &vv[i]);
for(i = 0; i < N; i++)
for(j = 0; j < N; j++)
for(k = 0; k < N; k++)
{v[cnt][0] = (vv[i] + vv[j] + vv[k]); v[cnt][1] = i; v[cnt][2] = j; v[cnt][3] = k; cnt ++;}
N = N * N * N;
QS(0, N - 1);
bool ok = false;
for(i = 0; i < N; i++)
{
if(BS(S - v[i][0]) != -1)
{
int pos = BS(S - v[i][0]);
for(j = 1; j <= 3; j++) printf("%i ", vv[v[i][j]]);
for(j = 1; j <= 3; j++) printf("%i ", vv[v[pos][j]]);
printf("\n");
ok = true;
break;
}
}
if(!ok) printf("-1\n");
scanf("%i", &i);
return 0;
}
int BS(int val)
{
int m, left = 0, right = N - 1;
while(left <= right)
{
int m = (left + right) / 2;
if(v[m][0] == val) return m;
if(v[m][0] < val) left = m + 1;
else right = m - 1;
}
return -1;
}