Submission #1348429

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

books

#include <bits/stdc++.h>

#include "books.h"

#define int long long

using namespace std; 
void solve(int32_t n, int32_t k, long long A, int32_t S) { 
    vector<int> arr(n+1,-1);

    auto get = [&](int p){
        if(arr[p] != -1) return arr[p];
        arr[p] = skim(p);
        return arr[p];
    };

    int cur = 0;
    set<int> chosen;
    for(int i = 1; i <= k; i++){
        cur += get(i);
        chosen.insert(i);
    }
    
    if(cur >= A && cur <= 2*A){
        vector<int32_t> res(chosen.begin(),chosen.end());
        answer(res);
        return;
    }

    int last = n;
    int fp = 0;
    for(int p = k; p >= 1; p--){
        int l = 0;
        if(p == k){
            l = p;
        }else{
            l = max(p,fp-k-1LL);
        }
        int r = last;
        if(r < l) break;
        while(l < r){
            int mid = (l+r+1)/2;
            if(cur-get(p)+get(mid) <= 2*A){
                l = mid;
            }else{
                r = mid-1;
            }
        }

        if(p == k){
            fp = l;
        }
        cur -= get(p);
        cur += get(l);
        chosen.erase(p);
        chosen.insert(l);  
        last = l-1;

        if(cur >= A && cur <= 2*A){
            vector<int32_t> res(chosen.begin(),chosen.end());
            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