Cod sursa(job #1474404)

Utilizator depevladVlad Dumitru-Popescu depevlad Data 21 august 2015 22:05:52
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <fstream>
#include <algorithm>
#include <tuple>

using namespace std;

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

const int MAX_N_POW3 = 1000000;
const int MAX_N = 100;

int V[MAX_N + 5];
tuple < int, int, int, int > C[MAX_N_POW3 + 1];

int main() {
    int n, i, j, k, s, nC = 0, left, right, mid;

    in >> n >> s;
    for(i = 1; i <= n; i++) in >> V[i];
    sort(V+1, V+n+1);
    for(i = 1; i <= n; i++) {
        for(j = 1; j <= n; j++) {
            for(k = 1; k <= n; k++) {
                C[++nC] = make_tuple(V[i] + V[j] + V[k], i, j, k);
            }
        }
    }
    for(i = 1; i <= nC; i++) {
        left = i;
        right = nC;
        while(left <= right) {
            mid = (left + right) / 2;
            if(get<0>(C[i]) + get<0>(C[mid]) == s) {
                out << get<1>(C[i]) << " " << get<2>(C[i]) << " " << get<3>(C[i]) << " ";
                out << get<1>(C[mid]) << " " << get<2>(C[mid]) << " " << get<3>(C[mid]) << "\n";
                return 0;
            }
            else if(get<0>(C[i]) + get<0>(C[mid]) < s) left = mid + 1;
            else right = mid - 1;
        }
    }
    out << "-1\n";
    return 0;
}