Submission #668386

#	Time	Username	Problem	Language	Result	Execution time	Memory
668386		mychecksedad	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	296 KiB

books

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define pb push_back

long long skim(int);
void answer(vector<int>);
void impossible();

void solve(int n, int k, ll A, int S){
    ll min_sum = 0;
    vector<int> v;
    for(int i = 1; i < k; ++i){
        min_sum += skim(i);
        v.pb(i);
    }
    if(min_sum > 2*A){
        return impossible();
    }
    int l = k, r = n, last_big = 0;
    while(l <= r){
        int m = (l+r)>>1;
        ll val = skim(m);
        if(val + min_sum >= A && val + min_sum <= 2*A){
            v.pb(m);
            return answer(v);
        }
        if(val + min_sum < A){
            l = m + 1;
            last_big = m + 1;
        }else{
            r = m - 1;
            last_big = m;
        }
    }
    if(last_big == 0){
        return impossible();
    }
    ll max_sum = 0;
    v.clear();
    for(int i = last_big - 1; i >= last_big - k; --i){
        max_sum += skim(i);
        v.pb(i);
    }
    if(max_sum <= 2*A && max_sum >= A) return answer(v);
    return 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