Cod sursa(job #1488207)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 18 septembrie 2015 09:57:59
Problema Loto Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 110;
const int Vmax = 1000000 + 10;

struct FMM
{
    int S;
    int x , y , z;
};

int n , s , i , STEP , nr;
int a[Nmax];

//unordered_map < int , bool > Hash;
FMM v[Vmax];

int search_(int x)
{
    int i , step = STEP;

    for (i = 0; step; step >>= 1)
        if (i + step <= nr && v[i+step].S < x)
            i += step;

    return i + 1;
}

bool cmp(FMM a , FMM b)
{
    return a.S < b.S;
}

void solve(bool mode)
{
    int i , j , k;

    for (i = 1 ; i <= n; ++i)
        for (j = 1; j <= n; ++j)
            for (k = 1; k <= n; ++k)
            {

                int sum = a[i] + a[j] + a[k];
                if (!mode)
                    nr++,
                    v[nr].S = sum, v[nr].x = a[i], v[nr].y = a[j] , v[nr].z = a[k];
                else if (mode)
                {
                    //if (Hash[s-sum] == 1)
                    {
                        int it = search_(s-sum);
                        if (v[it].S != s - sum) continue;
                        printf("%d %d %d %d %d %d\n", a[i] , a[j] , a[k], v[it].x , v[it].y , v[it].z);
                        return;
                    }
                }
            }

    if (mode) printf("-1\n");
    if (!mode) sort(v + 1 , v + nr + 1 , cmp);
}

int main()
{
    freopen("loto.in","r",stdin);
    freopen("loto.out","w",stdout);

    scanf("%d %d", &n, &s);

    for (i = 1; i <= n; ++i)
        scanf("%d", a + i);

    solve(0);
    for (STEP = 1; STEP < nr; STEP <<= 1);
    solve(1);

    return 0;
}