Cod sursa(job #1011527)

Utilizator PsychoAlexAlexandru Buicescu PsychoAlex Data 16 octombrie 2013 22:00:34
Problema Loto Scor 55
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.7 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;
}

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++)
                    {
                        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++)
//            {
//                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;
}