Submission #943875

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

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
//
// --- 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.
//
#define ll long long
ll arr[100005];
void solve(int N, int K, long long A, int S) {
    // TODO implement this function
    ll l=0,r=N+1,m;
    while (l!=r-1){
        m=(l+r)>>1;
        arr[m]=skim(m);
        if (arr[m]>=A) r=m;
        else l=m;
    }
    for (int i=1;i<=K;i++) arr[i]=skim(i);
    for (int i=max(1LL,r-K);i<=min<ll>(r,N);i++) arr[i]=skim(i);
    ll tot=0;
    vector<int> out;
    if (r!=N+1){
        for (int i=1;i<K;i++){
            tot+=arr[i];
            out.emplace_back(i);
        }
        tot+=arr[r];
        out.emplace_back(r);
        if (tot>=A && tot<=2*A){
            answer(out);
            return;
        }
        out.clear();
    }
    ll lptr=K,rptr=0;
    while (lptr!=-1){
        tot=0;
        for (int i=1;i<=lptr;i++){
            tot+=arr[i];
            out.emplace_back(i);
        }
        for (int i=r-rptr;i<r;i++){
            tot+=arr[i];
            out.emplace_back(i);
        }
        if (tot>=A && tot<=2*A){
            answer(out);
            return;
        }
        out.clear();
        lptr--,rptr++;
    }
    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