Submission #846864

#	Time	Username	Problem	Language	Result	Execution time	Memory
846864		MinaRagy06	A Difficult(y) Choice (BOI21_books)	C++17	5 / 100	135 ms	1216 KiB

books

#include <bits/stdc++.h>
#ifdef MINA
#include "grader.cpp"
#endif
#include "books.h"
#define ll long long
using namespace std;

void solve(int n, int k, ll a, int Q) {
    ll b[n];
    for (int i = 0; i < n; i++) {
        b[i] = skim(i + 1);
    }
    if (b[0] > 2 * a) {
        impossible();
    }
    vector<int> rem;
    for (int i = 0; i < n; i++) {
        rem.push_back(i);
    }
    ll s = 0;
    vector<int> ans;
    while (k--) {
        bool done = 0;
        int prv = -1;
        for (auto i : rem) {
            if (a - s <= b[i]) {
                if (b[i] > 2 * a - s) {
                    if (prv == -1) {
                        impossible();
                    }
                    s += b[prv];
                    ans.push_back(prv + 1);
                    done = 1;
                    break;
                }
                s += b[i];
                ans.push_back(i + 1);
                done = 1;
                break;
            }
            prv = i;
        }
        if (!done) {
            s += b[rem.back()];
            ans.push_back(rem.back() + 1);
        }
        vector<int> New;
        for (auto i : rem) {
            if (i == ans.back() - 1) continue;
            New.push_back(i);
        }
        rem = New;
    }
    if (!(a <= s && s <= 2 * a)) {
        impossible();
    }
    answer(ans);
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20