Submission #488367

#	Time	Username	Problem	Language	Result	Execution time	Memory
488367		Jarif_Rahman	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	1100 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){
    v.resize(n, -1);

    ll s = 0;
    vector<int> ans;

    for(int i = 0; i < k-1; i++) s+=Skim(i);

    int a = k-1, b = n-1;
    while(a < b){
        int md = (a+b)/2;
        if(Skim(md) < A) a = md+1;
        else b = md;
    }

    if(Skim(a) < A) a = n;

    if(s <= 2*A && a != n && 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);
    }

    if(a == 0) impossible();
    n = a-1;
    if(n < k-1) impossible();

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

    for(int i = 0; i < min(k, n-k+1); i++){
        s-=Skim(i);
        s+=Skim(n-i);
        if(s >= A && s <= 2*A){
            for(int j = i+1; j < k; j++) ans.pb(j+1);
            for(int j = n-i; j <= n; j++) ans.pb(j+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: 20 / 20
• Subtask 7: 20 / 20