Cod sursa(job #1011558)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 16 octombrie 2013 22:24:53
Problema Loto Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.41 kb
#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;
}