Submission #1236631

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236631		Double_Slash	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	408 KiB

books

#include "books.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define all(x) x.begin(), x.end()

void solve(int N, int K, ll A, int) {
    int i = N;
    for (int k = 17; k--;) {
        if ((1 << k) >= i) continue;
        if (skim(i - (1 << k)) >= A) i -= 1 << k;
    }
    vector<pair<int, ll>> v;
    for (int j = i; j >= max(1, i - K); --j) v.emplace_back(j, skim(j));
    ll sum = 0;
    for (int j = 0; ++j <= K;) {
        v.emplace_back(j, skim(j));
        sum += v.back().second;
    }
    if (sum > (A << 1)) impossible();
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    vector<int> ans;
    auto check = [&] (int l, int r) {
        if (sum >= A) {
            for (int j = l; j <= r; ++j) ans.emplace_back(v[j].first);
            answer(ans);
        }
    };
    check(0, K - 1);
    for (int i = K; i < v.size(); ++i) {
        sum += v[i].second - v[i - K].second;
        if (sum > (A << 1)) break;
        check(i - K + 1, i);
    }
    if (K == 1) impossible();
    sum = v.back().second;
    ans = {v.back().first};
    for (int i = K - 1; i--;) sum += v[i].second;
    if (sum > (A << 1)) impossible();
    check(0, K - 2);
    for (int i = K - 1; i < v.size() - 1; ++i) {
        sum += v[i].second - v[i - K + 1].second;
        if (sum > (A << 1)) impossible();
        check(i - K + 2, i);
    }
    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