Submission #488003

#	Time	Username	Problem	Language	Result	Execution time	Memory
488003		Jarif_Rahman	A Difficult(y) Choice (BOI21_books)	C++17	60 / 100	3 ms	1096 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

vector<ll> v;
ll Skim(int in){
    if(v[in] == -1) v[in] = skim(in+1);
    return v[in];
}


void solve(int n, int k, ll A, int S){
    if(S < 200) exit(-1);
    if(k > n) impossible();
    v.resize(n, -1);

    ll s = 0;
    for(int i = 0; i < k-1; i++) s+=Skim(i);
    vector<int> ans;

    if(s <= 2*A){
        int a = k-1, b = n-1;
        while(a < b){
            int md = (a+b)/2;
            if(Skim(md) >= A) b = md;
            else a = md+1;
        }
        if(s+Skim(a) >= A && s+Skim(a) <= 2*A){
            for(int i = 0; i < k-1; i++) ans.pb(i+1);
            ans.pb(a+1);
            answer(ans);
        }
    }

    auto segment_skim = [&](int in){
        ll s = 0;
        for(int i = in; i < in+k; i++) s+=Skim(i);
        return s;
    };

    int a = 0, b = n-k;
    while(a <= b){
        int md = (a+b)/2;
        ll cur = segment_skim(md);
        if(cur < A) a = md+1;
        else if(cur > 2*A) b = md-1;
        else{
            for(int i = md; i < md+k; i++) ans.pb(i+1);
            answer(ans);
        }
    }
    impossible();
}

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