Cod sursa(job #2915796)

Utilizator alin.gabrielAlin Gabriel Arhip alin.gabriel Data 25 iulie 2022 05:14:04
Problema Loto Scor 5
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.96 kb
#include <fstream>
#include <vector>
using namespace std;

ofstream fout("loto.out");

vector<int> sol, v;
long long ts = 0, s;
int n;

vector<int> qsort(vector<int> v, int ll, int hh) {
    if (hh - ll < 1)
        return v;

    int p = -1, l = ll, h = hh;
    int piv = v[l + (h - l) / 2];

    while (l < h) {
        while (v[l] < piv)
            l++;
        while (v[h] > piv)
            h--;

        if (l >= h) {
            p = h;
            break;
        }

        int tmp = v[l];
        v[l] = v[h];
        v[h] = tmp;
        l++;
        h--;
    }
    if (p == -1)
        p = h;

    v = qsort(v, ll, p);
    v = qsort(v, p + 1, hh);
    return v;
}

void print_sol() {
    sol = qsort(sol, 0, 5);
    for (int i = 0; i < 5 ; i++)
        fout << sol[i] << " ";
    fout << sol[sol.size() - 1];
    fout.close();
    exit(0);
}

bool found_sol() {
    return ts == s && sol.size() == 6;
}

void backtrack() {
    ts -= sol[sol.size() - 1];
    sol.pop_back();
}

void btk(int l, int h) {
    if (found_sol())
        print_sol();

    if (sol.size() >= 6)
        return;

    while(l <= h) {
        int m = l + (h - l) / 2;
        int csum = ts + v[m];
        int rest = 5 - (int)sol.size();
        if (csum + v[n - 1] * rest < s) {
            l = m + 1;
            continue;
        }
        if (csum + v[0] * rest > s) {
            h = m - 1;
            continue;
        }
        if (csum <= s) {
            sol.push_back(v[m]);
            ts += v[m];
            btk(0, n - 1);
            backtrack();
            l = m + 1;
        } else
            h = m - 1;
    }
}

int main() {
    ifstream fin("loto.in");

    fin >> n;
    fin >> s;
    int tmp;
    for (int i = 0 ; i < n; i++) {
        fin >> tmp;
        v.push_back(tmp);
    }
    fin.close();

    v = qsort(v, 0, n - 1);
    btk(0, n - 1);

    fout << -1;
    fout.close();
    return 0;
}