Pagini recente » Cod sursa (job #1545579) | Cod sursa (job #2724417) | Cod sursa (job #2588921) | Cod sursa (job #2088571) | Cod sursa (job #610650)
Cod sursa(job #610650)
#include <fstream.h>
ifstream fin ("loto.in");
ofstream fout ("loto.out");
typedef struct elem
{
long Suma;
long unu;
long doi;
long trei;
};
long i, N, S, vector[101], l = -1, gata = 0;
elem v[1000001], auxil;
void quickSort(elem *arr, int elements)
{
#define MAX_LEVELS 300
int piv, beg[MAX_LEVELS], end[MAX_LEVELS], i=0, L, R, swap ;
beg[0]=0;
end[0]=elements;
while (i>=0)
{
L=beg[i];
R=end[i]-1;
if (L<R)
{
piv=arr[L].Suma;
while (L<R)
{
while (arr[R].Suma>=piv && L<R) R--;
if (L<R) memcpy (&arr[L++], &arr[R], sizeof (elem));
while (arr[L].Suma<=piv && L<R) L++;
if (L<R) memcpy (&arr[R--], &arr[L], sizeof(elem));
}
arr[L].Suma=piv;
beg[i+1]=L+1;
end[i+1]=end[i];
end[i++]=L;
if (end[i]-beg[i]>end[i-1]-beg[i-1])
{
swap=beg[i];
beg[i]=beg[i-1];
beg[i-1]=swap;
swap=end[i];
end[i]=end[i-1];
end[i-1]=swap;
}
}
else
{
i--;
}
}
}
/*void qsort (long l1, long l2)
{
long l1a = l1, l2a = l2, pivot = 0;
if (l1 >= l2) return;
while (l1 < l2)
{
if (v[l1].Suma > v[l2].Suma)
{
memcpy (&auxil, &v[l1], sizeof (elem));
memcpy (&v[l1], &v[l2], sizeof (elem));
memcpy (&v[l2], &auxil, sizeof (elem));
if (pivot)
{
l2--;
pivot = 0;
}
else
{
l1++;
pivot = 1;
}
}
else
{
if (pivot) l1++;
else l2--;
}
}
qsort (l1a, l1 - 1);
qsort (l1 + 1, l2a);
}*/
int main ()
{
fin >> N >> S;
for (i = 0; i < N; i++)
{
fin >> vector[i];
}
fin.close ();
long j, k;
for (i = 0; i < N; i++)
{
for (j = i; j < N; j++)
{
for (k = j; k < N; k++)
{
v[++l].Suma = (v[l].unu = vector[i]) + (v[l].doi = vector[j]) + (v[l].trei = vector[k]);
if (v[l].Suma > S) l--;
}
}
}
quickSort (v, l + 1);
long aux, h, step;
for (i = 0; i <= l; i++)
{
aux = S - v[i].Suma;
for (step = 1; step < l; step <<= 1);
for (h = 0; step; step >>= 1)
{
if (h + step < l && v[h + step].Suma <= aux) h += step;
}
if (v[h].Suma == aux)
{
fout << v[i].unu << " " << v[i].doi << " " << v[i].trei << " " << v[h].unu << " " << v[h].doi << " " << v[h].trei;
fout.close ();
return 0;
}
}
fout << "-1";
fout.close ();
return 0;
}