Submission #646320

#	Time	Username	Problem	Language	Result	Execution time	Memory
646320		alextodoran	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	1064 KiB

books

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll skim (int i);
void answer (vector <int> v);
void impossible ();

void solve (int N, int K, ll A, int S) {
    ll D[N + 1];
    int l = 1, r = N + 1;
    while (l < r) {
        int mid = (l + r) / 2;
        D[mid] = skim(mid);
        if (D[mid] > A) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    for (int i = 1; i <= min(l - 1, K); i++) {
        D[i] = skim(i);
    }
    for (int i = max(1, l - K); i <= min(N, l); i++) {
        D[i] = skim(i);
    }
    if (l < K) {
        impossible();
        return;
    }
    if (l <= N) {
        ll sum = D[l];
        for (int i = 1; i <= K - 1; i++) {
            sum += D[i];
        }
        if (sum <= A * 2) {
            vector <int> v(K);
            iota(v.begin(), v.end() - 1, 1);
            v.back() = l;
            answer(v);
            return;
        }
    }
    if (l - 1 < K) {
        impossible();
        return;
    }
    ll sum = 0;
    for (int i = 1; i <= K; i++) {
        sum += D[i];
    }
    vector <int> L(K), R;
    iota(L.begin(), L.end(), 1);
    for (int i = K; i >= 1 && sum < A; i--) {
        sum -= D[L.back()];
        L.pop_back();
        R.push_back(l - 1 + i - K);
        sum += D[R.back()];
    }
    if (sum < A || 2 * A < sum) {
        impossible();
        return;
    }
    vector <int> v = L;
    reverse(R.begin(), R.end());
    for (int i : R) {
        v.push_back(i);
    }
    answer(v);
}

• 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