Submission #1017669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1017669		toast12	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	1 ms	436 KiB

books

#include "books.h"
#include <vector>
#include <iostream>
using namespace std;

using ll = long long;
//
// --- Sample implementation for the task books ---
//
// To compile this program with the sample grader, place:
//     books.h books_sample.cpp sample_grader.cpp
// in a single folder and run:
//     g++ books_sample.cpp sample_grader.cpp
// in this folder.
//

void solve(int N, int K, long long A, int S) {
    int lo = 1, hi = N+1;
    // find the first book larger than A
    while (hi-lo > 1) {
        int mid = (lo+hi)/2;
        ll x = skim(mid);
        if (x > A)
            hi = mid;
        else
            lo = mid;
    }
    if (hi < K)
        impossible();
    int idx = hi;
    vector<int> a(K+1);
    vector<ll> books(K+1);
    ll sum = 0;
    for (int i = 1; i <= K; i++) {
        a[i] = i;
        books[i] = skim(i);
        sum += books[i];
    }
    if (sum > 2*A) {
        impossible();
        return;
    }
    if (idx <= N) {
        ll temp = skim(idx);
        if (temp+sum-books[K] >= A && temp+sum-books[K] <= 2*A) {
            books[K] = idx;
            vector<int> ans;
            a[K] = idx;
            for (int i = 1; i <= K; i++)
                ans.push_back(a[i]);
            answer(ans);
        }
    }
    ll sum2 = 0;
    vector<ll> b;
    for (int i = idx-K; i < idx; i++) {
        b.push_back(skim(i));
        sum2 += b.back();
    }
    if (sum2 < A)
        impossible();
    if (sum >= A && sum <= 2*A) {
        vector<int> ans;
        for (int i = 1; i <= K; i++)
            ans.push_back(a[i]);
        answer(ans);
        return;
    }
    for (int i = K; i >= 1; i--) {
        // move the ith book to the end
        sum -= books[i];
        ll x = b[K-i];
        sum += x;
        a[i] = idx-K+i-1;
        if (sum >= A && sum <= 2*A)
            break;
    }
    vector<int> ans;
    for (int i = 1; i <= K; i++) {
        ans.push_back(a[i]);
    }
    answer(ans);
}

• 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