Submission #1368350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368350		LaMatematica14	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	0 ms	580 KiB

books

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

using namespace std;

void solve(int N, int K, long long A, int S) {
    vector<int> know(N, -1);
    auto ask = [&](int i) -> long long {
        if (i < 0 || i > N) return 0LL;
        if (know[i] == -1) {
            know[i] = skim(i+1);
        }
        return know[i];
    };
    
    long long sum = 0;
    for (int i = 0; i < K-1; i++) {
        sum += ask(i);
        if (sum > 2*A) {
            impossible(); return; 
        }
    }

    int l = K-2, r = N;
    while (l < r-1) {
        int m = (l+r)/2;
        if (sum + ask(m) <= 2*A) l = m;
        else r = m;
    }
    if (r == K-1) {
        impossible(); return;
    }
    sum += ask(l);

    vector<int> ans(K);
    iota(ans.begin(), ans.end(), 1);
    ans.back() = l+1;
    int j = 0;
    while (sum < A && j < K-1) {
        if (l == K-1) {
            impossible(); return;
        }
        sum -= ask(j);
        ans[j++] = l--;
        sum += ask(l);
    }
    if (sum < A) impossible();
    else answer(ans);
}

• Subtask 1: 0 / 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