Submission #946090

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

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;

void solve(int n, int k, long long A, int s)
{
    vector<long long> a(n + 2, -1);
    long long sum = 0;
    for (int i = 1; i <= k; i++) {
        a[i] = skim(i);
        sum += a[i];
    }
    if (sum > 2ll * A) impossible();
    if (sum >= A) {
        vector<int> ans;
        for (int i = 1; i <= k; i++) ans.push_back(i);
        answer(ans);
    }
    int l = 1, r = n, oe = n + 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        a[mid] = skim(mid);
        if (a[mid] >= A) {
            oe = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    if (oe != n + 1) {
        if (sum - a[k] + a[oe] <= 2ll * A) {
            vector<int> ans;
            for (int i = 1; i < k; i++) {
                ans.push_back(i);
            }
            ans.push_back(oe);
            answer(ans);
        }
    }
    oe--;
    long long dak = 0;
    for (int i = oe; i > oe - k; i--) {
        a[i] = skim(i);
        dak += a[i];
    }
    if (dak < A) impossible();
    for (int i = oe; i > oe - k; i--) {
        vector<int> ans;
        int lef = k - (oe - i + 1);
        long long sum = 0;
        for (int j = 1; j <= lef; j++) {
            ans.push_back(j);
            sum += a[j];
        }
        for (int j = i; j <= oe; j++) {
            ans.push_back(j);
            sum += a[j];
        }
        if (A <= sum && sum <= 2ll * A) {
            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