Submission #502481

#	Time	Username	Problem	Language	Result	Execution time	Memory
502481		Gurban	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	404 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+5;
ll arr[maxn];
int now[20];

ll f(int idx){
    if(!arr[idx]) arr[idx] = skim(idx);
    return arr[idx];
}

void solve(int N, int K, long long A, int S) {
    ll sum = 0;
    for(int i = 1;i <= K;i++) sum += f(i),now[i] = i;
    if(sum > 2 * A){
        impossible();
        return;
    }
    if(sum >= A){
        vector<int>ans;
        for(int i = 1;i <= K;i++) ans.push_back(i);
        answer(ans);
        return;
    }

    int l = K + 1,r = N,md,jog=-1;
    while(l <= r){
        md = (l + r) / 2;
        if(sum - f(K) + f(md) <= 2*A) jog=md,l=md+1;
        else r = md - 1;
    }
    if(jog == -1){
        impossible();
        return;
    }
    now[K] = jog;
    sum -= f(K);
    sum += f(jog);
    if(sum >= A){
        vector<int>ans;
        for(int i = 1;i < K;i++) ans.push_back(i);
        ans.push_back(jog);
        answer(ans);
        return;
    }
    int nw = jog-1;
    for(int i = K-1;i >= 1;i--){
        if(sum - f(i) + f(nw) <= 2*A){
            now[i] = nw;
            sum -= f(i);
            sum += f(nw);
            nw--;
        }
        else {
            l = i + 1,r = nw - 1,jog=-1;
            while(l <= r){
                md = (l + r) / 2;
                if(sum - f(i) + f(md) <= 2*A) jog=md,l=md+1;
                else r=md-1;
            }
            now[i] = jog;
            sum -= f(i);
            sum += f(jog);
        }
        if(sum >= A){
            vector<int>ans;
            for(int i = 1;i <= K;i++) ans.push_back(now[i]);
            answer(ans);
            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