Pagini recente » Cod sursa (job #647911) | Cod sursa (job #2856806) | Cod sursa (job #868738) | Cod sursa (job #743866) | Cod sursa (job #1011557)
#include <iostream>
#include <fstream>
#include <algorithm>
std::ifstream fin("loto.in");
std::ofstream fout("loto.out");
struct sssum
{
long sum, a, b, c;
} sume[10000001];
long n, S, a[1001], myS, nrUsed, sol[6], ind;
void change(long &a, long &b)
{
long aux = a;
a = b;
b = aux;
}
inline bool cmp(sssum q, sssum w)
{
if(q.sum <= w.sum)
{
return true;
}
return false;
}
inline bool fnd(sssum q, sssum w)
{
return (q.sum < w.sum);
}
void poz(long li, long ls, long &k)
{
int i1 = 1, j1 = 0;
long i = li, j = ls;
while(i < j)
{
if(sume[i].sum > sume[j].sum)
{
change(sume[i].sum, sume[j].sum);
change(sume[i].a, sume[j].a);
change(sume[i].b, sume[j].b);
change(sume[i].c, sume[j].c);
//daca am interschimbat 2 valori, atunci schimbam directia din care venim
//daca am inceput din stanga, atunci trecem in dreapta
if(i1 == 1)
{
i1 = 0;
j1 = -1;
}
else
//daca am inceput din dreapta, atunci trecem in stanga
{
i1 = 1;
j1 = 0;
}
}
i += i1;
j += j1;
}
k = i;
}
void Qsort(long li, long ls)
{
long k;//k e modificat in poz(int, int, int&)
if(li < ls)
{
poz(li, ls, k);
Qsort(li, k - 1);
Qsort(k + 1, ls);
}
}
void citire()
{
fin>>n>>S;
for(long i = 0; i < n; i++)
{
fin>>a[i];
}
// Qsort(0, n-1);
}
long binSearch(long in, long sf, long su)
{
long m;
while(in <= sf)
{
m = (in + sf) / 2;
if(sume[m].sum + su < S)
{
in = m+1;
}
else
if(sume[m].sum + su > S)
{
sf = m-1;
}
else
{
return m;
}
}
return -1;
}
void rezolvare()
{
float pos = (float) S/a[n-1];
// if(pos > 6)
// {
// std::cout<<"111: "<<-1<<'\n';
// }
// else
// if(S % a[n-1] == 0 && S / a[n-1] == 6)
// {
// for(long i = 0; i < 6; i++)
// {
// fout<<a[n-1]<<' ';
// }
// fout<<'\n';
// }
// else
{
for(long i = 0; i < n; i++)
{
for(long j = i; j < n; j++)
{
for(long k = j; k < n; k++)
{
if(a[i] + a[j] + a[k] < S)
{
sume[ind].sum = a[i] + a[j] + a[k];
sume[ind].a = a[i];
sume[ind].b = a[j];
sume[ind].c = a[k];
}
// if(sume[ind].sum * 2 == S)
// {
// fout<<a[i]<<' '<<a[j]<<' '<<a[k]<<' '<<a[i]<<' '<<a[j]<<' '<<a[k]<<'\n';
// return;
// }
ind++;
}
}
}
///Qsort(0, ind - 1);
std::sort(sume, sume+ind, cmp);
for(int i = 0; i < ind; i++)
{
sssum mm = sume[i];
mm.sum = S-sume[i].sum;
if(std::binary_search(sume, sume+ind, mm, fnd))
{
long indice = binSearch(i, ind-1, sume[i].sum);
fout<<sume[i].a<<' '<<sume[i].b<<' '<<sume[i].c<<' ';
fout<<sume[indice].a<<' '<<sume[indice].b<<' '<<sume[indice].c<<' ';
return;
}
// std::cout<<sume[i].sum<<' ';
}
// bool found = false;
//
//// long p1 = 0, p2 = ind - 1;
////
//// while(p1 <= p2)
//// {
//// if(sume[p1][0] + sume[p2][0] < S)
//// {
//// p1++;
//// }
//// else
//// if(sume[p1][0] + sume[p2][0] > S)
//// {
//// p2--;
//// }
//// else
//// {
//// for(long j = 1; j <= 3; j++)
//// {
//// fout<<sume[p1][j]<<' ';
//// }
//// for(long j = 1; j <= 3; j++)
//// {
//// fout<<sume[p2][j]<<' ';
//// }
//// return;
//// }
//// }
// for(long i = 0; i < ind; i++)
// {
// long indice = binSearch(0, ind-1, sume[i].sum);
// if(indice != -1)/// && sume[i][0] < S)
// {
//// for(long j = 1; j <= 3; j++)
// {
// fout<<sume[i].a<<' '<<sume[i].b<<' '<<sume[i].c<<' ';
// }
//// for(long j = 1; j <= 3; j++)
// {
// fout<<sume[indice].a<<' '<<sume[indice].b<<' '<<sume[indice].c<<' ';
// }
// return;
// }
// }
if(!found)
{
fout<<-1<<'\n';
}
}
}
int main()
{
citire();
rezolvare();
return 0;
}