Submission #1204110

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204110		Unforgettablepl	A Difficult(y) Choice (BOI21_books)	C++20	10 / 100	1 ms	1176 KiB

books

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

void solve(int N,int K,long long A,int S){
    vector<long long> 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){
        long long sum = 0;
        {
            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 = K-1;
    // 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;
    }
    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: 10 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20