Submission #619661

#	Time	Username	Problem	Language	Result	Execution time	Memory
619661		NicolaAbusaad2014	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	1128 KiB

books

#include<vector>
#include<cstdio>
#include<set>
#include<cstdlib>
#include<cstdarg>
#include<cassert>
#include"books.h"

using namespace std;
void solve(int N, int K, long long A, int S) {
    if(skim(1)>=A){
        impossible();
        return;
    }
    long long idx=0,jump=N,sum=0;
    while(jump&(jump-1)){
        jump=jump&(jump-1);
    }
    while(jump){
        if(idx+jump<N&&skim(idx+jump+1)<=A){
            idx+=jump;
        }
        jump/=2;
    }
    vector<long long>v(N);
    vector<int>ans;
    for(int i=0;i<K;i++){
        v[i]=skim(i+1);
        ans.push_back(i+1);
        sum+=v[i];
    }
    if(sum>2*A){
        impossible();
        return;
    }
    if(A<=sum){
        answer(ans);
        return;
    }
    for(int i=max(0ll,idx-K+1);i<=min((long long)N-1,idx+1);i++){
        v[i]=skim(i+1);
    }
    if(A<=sum-v[K-1]+v[min((long long)N-1,idx+1)]&&sum-v[K-1]+v[min((long long)N-1,idx+1)]<=2*A){
        ans.pop_back();
        ans.push_back(min((long long)N-1,idx+1)+1);
        answer(ans);
        return;
    }
    int x=0;
    for(int i=min((long long)N-1,idx);i>=max(idx-K+1,(long long)K);i--){
        sum-=v[x];
        sum+=v[i];
        x++;
        ans.erase(ans.begin());
        ans.push_back(i+1);
        if(A<=sum&&sum<=2*A){
            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