Submission #1303021

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303021		yuichiro17	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	2 ms	1080 KiB

books

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

vector<ll>memo;
int n,k,s;
ll a;
ll ask(int i){
    if(memo[i]==-1)return memo[i]=skim(i+1);
    else return memo[i];
}
int bs(ll x,int l,int r){
    if(l==r)return l;
    int m=(l+r)/2;
    ll y=ask(m);
    if(x==y)return m;
    else if(x<y)return bs(x,l,m);
    else return bs(x,m+1,r);
}

void solve(int N, int K, long long A, int S) {
    n=N,k=K,a=A,s=S;
    memo=vector<ll>(n,-1);
    int x=bs(a,0,n-1);
    vector<pair<ll,int>>v;
    for(int i=0;i<10;i++){
        v.push_back({ask(i),i+1});
    }
    for(int i=max(10,x-10);i<x;i++){
        v.push_back({ask(i),i+1});
    }
    {
        ll sum=ask(x);
        vector<int>ans={x+1};
        for(int i=0;i<k-1;i++){
            ans.push_back(v[i].second);
            sum+=v[i].first;
        }
        if(sum>=a&&sum<=2*a){
            answer(ans);
            return;
        }
    }
    for(int i=0;i+k<=v.size();i++){
        ll sum=0;
        vector<int>ans;
        for(int j=i;j<i+k;j++){
            ans.push_back(v[j].second);
            sum+=v[j].first;
        }
        if(sum>=a&&sum<=2*a){
            answer(ans);
            return;
        }
    }
    impossible();
}

• 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