Submission #1138049

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138049		ConquerConquerer	A Difficult(y) Choice (BOI21_books)	C++20	10 / 100	1 ms	428 KiB

books

#include <bits/stdc++.h>
#include "books.h"
using namespace std;

long long value[100005], b[21];
int pos[21];

void solve(int N, int K, long long A, int S) {
    for (int i = 1; i <= K; i++)
        value[i] = skim(i);

    int low = 1, high = N, ans = N + 1;
    while (low <= high) {
        int mid = (low + high) >> 1;

        if (!value[mid]) value[mid] = skim(mid);
        if (value[mid] <= A) low = mid + 1;
            else {
                ans = mid;
                high = mid - 1;
            }
    }

    if (ans < K) {
        impossible();
        return ;
    }

    if (ans != N + 1) {
        long long total = value[ans];
        for (int i = 1; i < N; i++)
            total += value[i];
        if (total <= A + A) {
            vector<int> v;
            v.push_back(ans);
            for (int i = 1; i < N; i++)
                v.push_back(i);
            answer(v);
            return ;
        }
    }

    for (int i = 1; i <= K; i++) {
        pos[i] = i;
        b[i] = value[i];
    }

    int idx = K;
    if (K < ans - K) {
        for (int i = ans - K; i < ans; i++) {
            if (!value[i]) value[i] = skim(i);
            b[++idx] = value[i];
            pos[idx] = i;
        }
    }
    else  {
        idx = ans - 1;
        for (int i = K + 1; i < ans; i++) {
            if (!value[i]) value[i] = skim(i);
            b[i] = value[i];
            pos[i] = i;
        }
    }

    for (int i = K; i <= idx; i++) {
        long long total = 0;
        for (int j = i - K + 1; j <= i; j++)
            total += b[j];
        if (A <= total && total <= A + A) {
            vector<int> v;
            for (int j = i - K + 1; j <= i; j++)
                v.push_back(pos[j]);
            answer(v);
            return ;
        }
    }

    impossible();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 10 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20