Cod sursa(job #1093592)

Utilizator MoneaVladMonea Vlad MoneaVlad Data 28 ianuarie 2014 12:19:30
Problema Loto Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <iostream>
#include <algorithm>

using namespace std;

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

int a[101], I[1000001], J[1000001], K[1000001];
long long S[10000001];
int l;

int cautbin (int x, int st, int dr){
    while (dr - 1 > st){
        int mid = st + (dr - st) / 2;
        if (S[mid] == x)
            return mid;
        if (S[mid] < x)
            st = mid + 1;
        else
            dr = mid - 1;
    }
    if (S[dr] == x)
        return dr;
    if (S[st] == x)
        return st;
    else
        return -1;
}


int main()
{
    int N, Suma, i, j, k, poz, ok;
    in >> N >> Suma;
    for (i = 1; i <= N; i++)
        in >> a[i];
    for (i = 1; i <= N; i++)
        for (j = i; j <= N; j++)
            for (k = j; k <= N; k++)
            {
                l++;
                S[l] = a[i] + a[j] + a[k];
                I[l] = i;
                J[l] = j;
                K[l] = k;
            }
    ok = 1;
    sort(S + 1, S + l + 1);
    for (i = 1; i <= l; i++) out << S[i] << " "; out << '\n';
    /*while (ok) {
        ok = 0;
        for(i = 1; i < l; i++)
            if (S[i] > S[i+1]) {
                aux = S[i];
                S[i] = S[i+1];
                S[i+1] = aux;
                aux = I[i];
                I[i] = I[i+1];
                I[i+1] = aux;
                aux = J[i];
                J[i] = J[i+1];
                J[i+1] = aux;
                aux = K[i];
                K[i] = K[i+1];
                K[i+1] = aux;
                ok = 1;
            }
    }*/
    ok = 0;
    for (i = 1; i <= l; i++){
        poz = cautbin (Suma - S[i], 1, l);
        if (poz > 0){
            ok = 1;
            out << I[i] << " " << J[i] << " " << K[i] << " " << I[poz] << " " << J[poz] << " " << K[poz];
            break;
        }
    }
    if(ok == 0)
        out << -1 << "\n";
    in.close();
    out.close();
    return 0;
}