Submission #734252

#	Time	Username	Problem	Language	Result	Execution time	Memory
734252		Stickfish	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	336 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

const int MAXN = 1e5 + 123;
ll a[MAXN];
bitset<MAXN> bs;

ll get(int i) {
    if (bs[i])
        return a[i];
    bs[i] = 1;
    return a[i] = skim(i);
}

void solve(int n, int k, ll anssm, int s) {
    ll sm = 0;
    for (int i = 1; i <= k; ++i)
        sm += get(i);
    if (sm > anssm * 2) {
        impossible();
        return;
    }
    vector<int> els(k);
    for (int i = 0; i < k; ++i)
        els[i] = k - i;
    if (sm >= anssm) {
        answer(els);
        return;
    }
    int lb = k, ub = n + 1;
    while (ub - lb > 1) {
        int mb = (lb + ub) / 2;
        if (sm + get(mb) - get(k) > anssm * 2)
            ub = mb;
        else
            lb = mb;
    }
    for (int i = 0; i < k; ++i) {
        sm += get(lb - i) - get(k - i);
        els[i] = lb - i;
        if (sm >= anssm) {
            answer(els);
            return;
        }
    }
    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