Submission #1022550

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

books

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

using namespace std;

const int N = 100100;

long long x[N];

long long value(int pos) {
    if (!x[pos]) x[pos] = skim(pos);
    return x[pos];
}

void solve(int N, int K, long long A, int S) {
    int l = 0, r = N + 1; 
    while (r - l > 1) {
        int m = (l + r) / 2;
        if (value(m) > A) r = m;
        else l = m;
    }
    auto f = [&](long long v) {return (A <= v && v <= 2 * A); };
    
    long long pre[K + 1] = {};
    long long suf[K + 1] = {};

    for (int i = 1; i <= K; i++) 
        pre[i] = value(i) + pre[i - 1];

    if (r <= N && f(value(r) + pre[K - 1])) {
        vector<int> res;
        for (int i = 1; i < K; i++) res.push_back(i);
        res.push_back(r);
        answer(res);
        return;
    } 
    if (r <= K) {
        impossible();
        return;
    }
    for (int i = 1; i <= K; i++) 
        suf[i] = value(r - i) + suf[i - 1];
    
    for (int i = 0; i <= K; i++) {
        if (f(pre[i] + suf[K - i])) {
            vector<int> res;
            for (int j = 1; j <= i; j++) 
                res.push_back(j);
            for (int j = 1; j <= K - i; j++) 
                res.push_back(r - j);
            answer(res);
            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