Cod sursa(job #616807)

Utilizator psycho21rAbabab psycho21r Data 13 octombrie 2011 13:59:18
Problema Loto Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <vector>

using namespace std;

struct halfsum
{
    int s, x, y, z;
} b[1000000], temp[1000000];

void merge (unsigned int a, unsigned int c)
{
    unsigned int left = a, left_end = (a+c)/2, mid = left_end+1, mid_end = c, pos = a;

    while (left <= left_end && mid <= mid_end)
    {
        if(b[left].s < b[mid].s)
            temp[pos++] = b[left++];
        else
            temp[pos++] = b[mid++];
    }

    while (left <= left_end)
        temp[pos++] = b[left++];
    while (mid <= mid_end)
        temp[pos++] = b[mid++];

    for (int i = a; i < pos; ++i)
        b[i] = temp[i];
}

void sort (unsigned int z, unsigned int x)
{
    if (x - z <= 0)
        return;
    sort (z, (z+x)/2);
    sort ((z+x)/2 + 1, x);
    merge (z, x);
}

int main()
{
    ifstream in("loto.in");
    vector <int> a;
    unsigned int n, s, temp, x = 0;
    in >> n >> s;
    for (int i = 0; i < n; ++i)
    {
        in >> temp;
        a.push_back(temp);
    }
    in.close();

    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
            for (int k = j; k < n; ++k)
            {
                temp = a[i] + a[j] + a[k];
                if (temp > s)
                    continue;
                b[x].s = temp;
                b[x].x = a[i];
                b[x].y = a[j];
                b[x++].z = a[k];
            }

    --x;
    sort(0,x);

    int l = 0, sum;
    while (l <= x)
    {
        sum = s - b[l].s - b[x].s;
        if (sum == 0)
        {
            ofstream out("loto.out");
            out << b[l].x << " " << b[l].y << " " << b[l].z << " " << b[x].x << " " << b[x].y << " " << b[x].z;
            out.close();
            return 0;
        }
        else
            if (sum < 0)
                --x;
            else
                ++l;
    }
    ofstream out("loto.out");
    out << -1;
    out.close();
    return 0;
}