Submission #1204065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204065		Unforgettablepl	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	0 ms	664 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

void solve(int N,int K,long long A,int S){
    vector<int> memo(N+1);
    auto optSkim = [&](int x){
        if(memo[x]==0)return memo[x]=skim(x);
        else return memo[x];
    };
    auto test = [&](int x,bool strict){
        int sum = 0;
        if(optSkim(x)>=A){
            for(int i=1;i<K;i++)sum+=optSkim(i);
            sum+=optSkim(x);
        } else {
            for(int i=x-K+1;i<=x;i++)sum+=optSkim(i);
        }
        if(strict)return A<=sum and sum<=2ll*A;
        return A<=sum;
    };
    int ans = K-1;
    for(int jump=(1<<16);jump;jump/=2){
        if(ans+jump>N)continue;
        if(!test(ans+jump,false))ans+=jump;
    }
    ans++;
    int ans2 = 0;
    for(int i=1;i<=N;i++)if(memo[i]!=0 and memo[i]<A)ans2=i;
    for(int jump=(1<<16);jump;jump/=2){
        if(ans2+jump>N)continue;
        if(optSkim(ans2+jump)<A)ans2+=jump;
    }
    ans2++;
    if(ans==N+1 or !test(ans,true)){
        impossible();
        return;
    }
    swap(ans2,ans);
    if(ans==N+1 or !test(ans,true)){
        impossible();
        return;
    }
    vector<int> anss;
    if(optSkim(ans)>=A){
        for(int i=1;i<K;i++)anss.emplace_back(i);
        anss.emplace_back(ans);
    } else {
        for(int i=ans-K+1;i<=ans;i++)anss.emplace_back(i);
    }
    answer(anss);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20