Cod sursa(job #1020214)

Utilizator tudorv96Tudor Varan tudorv96 Data 1 noiembrie 2013 19:57:35
Problema Loto Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;

const int N = 101, MEM = N * N * N;
int num[MEM], n, s, L[MEM], M[MEM], R[MEM], nod, CMP[MEM];
map <int, int> ord;

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

bool cmp (int a, int b) {
    return num[a] < num[b];
}

int main() {
    fin >> n >> s;
    nod = n;
    int MAX = -1, MIN = 2e9;
    for (int i = 0; i < n; ++i) {
        fin >> num[i];
        MIN = min (MIN, num[i]);
        MAX = max (MAX, num[i]);
    }
    if (MAX * 6 < s || MIN * 6 > s) {
        fout << -1;
        return 0;
    }
    MAX = -1, MIN = 2e9;
    sort (num, num + n);
    fin.close();
    for (int i = 0; i < n; ++i)
        for (int j = i; j < n; ++j)
            for (int k = j; k < n; ++k) {
                CMP[nod - n] = nod;
                num[nod] = num[i] + num[j] + num[k];
                if (num[nod] > s)
                    continue;
                L[nod] = i;
                M[nod] = j;
                R[nod] = k;
                ord.insert (make_pair (num[nod], nod));
                nod++;
            }
    map <int, int> :: iterator it;
    sort (CMP, CMP + nod - n, cmp);
    for (int i = 0; i < nod - n; ++i) {
        int I = CMP[i];
        it = ord.find (s - num[I]);
        if (it != ord.end() && num[(*it).second] + num[I] == s) {
            int sol = (*it).second;
            fout << num[L[I]] << " " << num[M[I]] << " " << num[R[I]] << " " << num[L[sol]] << " " << num[M[sol]] << " " << num[R[sol]];
            return 0;
        }
    }
    fout << -1;
}