Submission #1297602

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

books

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

using namespace std;

using ll = long long;
using big = __int128_t;

#define mid ((l+r)>>1)

//
// --- 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.
//

void solve(int N, int K, long long A, int Ss) {
    vector<ll> F;
    for(int i=1; i<=K; i++) F.push_back(skim(i));
    big sum = 0;
    for(ll i : F) sum += i;
    if(sum > 2*A) return impossible();
    if(sum>=A) {
        vector<int> ans;
        for(int i=1; i<=K; i++) ans.push_back(i);
        return answer(ans);
    }
    int r=N+1, l=K;
    while(r-l>1)
        (skim(mid)>=A ? r : l) = mid;
    if(r<=N && sum-F.back()+skim(r)<=2*A) {
        vector<int> ans;
        for(int i=1; i<K; i++) ans.push_back(i);
        ans.push_back(r);
        return answer(ans);
    }
    vector<ll> S;
    for(int i=r-K; i<r; i++) S.push_back(skim(i));
    for(int i=1; i<=K; i++) {
        sum -= F.back();
        F.pop_back();
        sum += S.back();
        S.pop_back();
        if(A <= sum && sum <= 2*A) {
            vector<int> ans;
            for(int j=1; j<=K-i; j++)
                ans.push_back(j);
            for(int j=r-i; j<r; j++)
                ans.push_back(j);
            return 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