Submission #1155588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155588		vladilius	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	0 ms	408 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second

void solve(int n, int k, ll A, int S){
    int l = 1, r = n + 1;
    while (l + 1 < r){
        int m = (l + r) / 2;
        if (skim(m) >= A){
            r = m;
        }
        else {
            l = m + 1;
        }
    }
    
    if (l != r && skim(l) >= A) r = l;
    
    if (r < k){
        impossible();
        return;
    }
    
    vector<ll> f = {0};
    for (int i = 1; i <= k; i++) f.pb(skim(i));
    
    if (r != (n + 1)){
        ll sum = skim(r);
        for (int i = 1; i < k; i++){
            sum += f[i];
        }
        if (A <= sum && sum <= 2 * A){
            vector<int> out = {r};
            for (int i = 1; i < k; i++){
                out.pb(i);
            }
            answer(out);
            return;
        }
    }
    
    if (r == k){
        impossible();
        return;
    }
    
    vector<ll> g = {0};
    for (int i = r - 1; i >= r - k; i--) g.pb(skim(i));
    
    for (int i = 0; i <= k; i++){
        ll sum = 0;
        for (int j = 1; j <= i; j++){
            sum += f[j];
        }
        for (int j = 1; j <= (k - i); j++){
            sum += g[j];
        }
        if (A <= sum && sum <= 2 * A){
            vector<int> out;
            for (int j = 1; j <= i; j++){
                out.pb(j);
            }
            for (int j = 1; j <= k - i; j++){
                out.pb(r - j);
            }
            answer(out);
            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