Cod sursa(job #1789776)

Utilizator teo.cons98Constantin Teodor-Claudiu teo.cons98 Data 27 octombrie 2016 15:22:17
Problema Loto Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.79 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream fin("loto.in");
ofstream fout("loto.out");

struct sum
{
    int p1, p2, p3, val;
}v[1000001],A[1000001];


long long n, s, el1, el2, caut;

int e = 0;

void citire()
{
    fin>>n>>s;
    for(int i = 1; i <= n; ++i)
    {
        fin>>A[i].val;
    }
}

void sortare(int p, int u)
{
    int mid = (p + u + 1) / 2;
    if(p < u)
    {
        sortare(p, mid - 1);
        sortare(mid, u);
        int x, y, poz = p;
        x = p;
        y = mid;
        while(x < mid and y <= u)
        {
            if(v[x].val < v[y].val)
            {
                A[poz].val = v[x].val;
                A[poz].p1 = v[x].p1;
                A[poz].p2 = v[x].p2;
                A[poz].p3 = v[x].p3;
                ++x;
            }
            else
            {
                A[poz].val = v[y].val;
                A[poz].p1 = v[y].p1;
                A[poz].p2 = v[y].p2;
                A[poz].p3 = v[y].p3;
                ++y;
            }
            ++poz;
        }
        while(x < mid)
        {
            A[poz].val = v[x].val;
            A[poz].p1 = v[x].p1;
            A[poz].p2 = v[x].p2;
            A[poz].p3 = v[x].p3;
            ++poz;
            ++x;
        }
        while(y <= u)
        {
            A[poz].val = v[y].val;
            A[poz].p1 = v[y].p1;
            A[poz].p2 = v[y].p2;
            A[poz].p3 = v[y].p3;
            ++poz;
            ++y;
        }
        for(int i = p; i <= u; ++i)
        {
            v[i].val = A[i].val;
            v[i].p1 = A[i].p1;
            v[i].p2 = A[i].p2;
            v[i].p3 = A[i].p3;
        }
    }
}

void cautBin(int p, int u)
{
    if(p < u){
    int mid = (p + u + 1)/2;
    if(v[mid].val + caut > s)
    {
        cautBin(p, mid - 1);
    }
    else if(v[mid].val + caut < s)
    {
        cautBin(mid, u);
    }
    if(v[mid].val + caut == s)
    {
        e = mid;
    }}
}

int main()
{
    citire();

    int poz = 1;
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int k = 1; k <= n; ++k)
            {
                v[poz].val = A[i].val + A[j].val + A[k].val;
                v[poz].p1 = A[i].val;
                v[poz].p2 = A[j].val;
                v[poz].p3 = A[k].val;
                ++poz;
            }
        }
    }

    n = poz - 1;

    sortare(1, n);

    for(int i = 1;i < n; ++i)
    {
        caut = v[i].val;
        cautBin(1,n);

        if(e != 0)
        {
            el1 = i;
            el2 = e;
            break;
        }
    }
    if(e == 0) fout<<"-1";
    else fout<<v[el1].p1<<" "<<v[el1].p2<<" "<<v[el1].p3<<" "<<v[el2].p1<<" "<<v[el2].p2<<" "<<v[el2].p3<<endl;
}