Cod sursa(job #1656067)

Utilizator TimitocArdelean Andrei Timotei Timitoc Data 18 martie 2016 18:04:59
Problema Loto Scor 45
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define MAXN 110
#define HASH 1000003

using namespace std;

int a[MAXN], n, s, nq;
struct elem
{
    int val, ind;
    elem(int val = 0, int ind = 0) : val(val), ind(ind) { }
    bool operator()(elem x, elem y) { return x.val < y.val; }
}part[MAXN*MAXN*MAXN];
vector<elem> table[HASH+5];

void citire()
{
    scanf("%d %d\n", &n, &s);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
}

void put(int nr, int ind)
{
    table[nr%HASH].push_back(elem(nr, ind));
}

int get(int nr)
{
    int h = nr%HASH;
    for (int i = 0, t = table[h].size(); i < t; i++)
        if (table[h][i].val == nr)
            return table[h][i].ind;
    return 0;
}

void solvePart()
{
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            for (int k = 1; k <= n; k++) {
                put(a[i]+a[j]+a[k], ++nq);
                part[nq] = elem(a[i]+a[j]+a[k], nq);
            }
}

void print(int ind)
{
    ind--;
    printf("%d %d %d ", a[ind/(n*n)+1], a[(ind/n)%n+1], a[ind%n+1]);
}

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

    citire();
    solvePart();
    //sort(part+1, part+1+nq, elem());
    for (int i = 1; i <= nq; i++) {
        int must = s - part[i].val;
        int ind = get(must);
        if (ind) {
            print(part[i].ind);
            print(ind);
            return 0;
        }
    }
    printf("-1");

    return 0;
}