Submission #571727

#	Time	Username	Problem	Language	Result	Execution time	Memory
571727		Cyanmond	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	1100 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
using i64 = long long;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

i64 skim2(int v) { return skim(v + 1); }

void solve(int N, int K, long long A, int S) {
    vector<i64> data(N, -1);
    REP(i, K) data[i] = skim2(i);
    if (accumulate(data.begin(), data.begin() + K, 0ll) > 2 * A) {
        impossible();
        return;
    }

    vector<int> ked(K);
    REP(i, K) ked[i] = N - (K - i);

    auto eval = [&](int i, int m) {
        i64 res = 0;
        REP(x, i) res += data[x];
        REP3(x, i + 1, K) res += data[ked[x]];
        return res + data[m];
    };

    auto rtrn = [&](int i, int m) {
        vector<int> ans;
        REP(x, i) ans.push_back(x);
        REP3(x, i + 1, K) ans.push_back(ked[x]);
        ans.push_back(m);
        sort(ALL(ans));
        for (auto &e : ans) ++e;
        answer(ans);
        return;
    };

    if (A <= eval(K - 1, K - 1) and eval(K - 1, K - 1) <= 2 * A) {
        rtrn(K - 1, K - 1);
        return;
    }

    RVP(i, K) {
        const int j = min(i == K - 1 ? N - 1 : (ked[i + 1] - 1), ked[i]);
        if (data[j] == -1) data[j] = skim2(j);
        const auto res = eval(i, j);
        if (A <= res and res <= 2 * A) {
            rtrn(i, j);
            return;
        } else {
            if (res < A) {
                ked[i] = j;
                continue;
            }
            int ok = i, ng = j;
            while (ng - ok > 1) {
                const int mid = (ok + ng) / 2;
                if (data[mid] == -1) data[mid] = skim2(mid);
                const auto r = eval(i, mid);
                if (r <= A)
                    ok = mid;
                else
                    ng = mid;
            }
            if (A <= eval(i, ng) and eval(i, ng) <= 2 * A) {
                rtrn(i, ng);
                return;
            }
            ked[i] = ok;
        }
    }
    impossible();
}

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