Submission #401402

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

books

#include <bits/stdc++.h>

#include "books.h"

#define ll long long

using namespace std;
//
// --- 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, ll A, int S)
{
    int l = -1;
    int r = N;

    ll lb = 1e18;
    while (l + 1 < r)
    {
        int m = (l + r) / 2;
        ll v = skim(m + 1);
        if (v >= A) { r = m; lb = min(lb, v); }
        else l = m;
    }

    vector<int> qs;
    for (int i = 0; i < K; i++) qs.push_back(i);
    for (int i = 0; i < K && l - i >= 0; i++) qs.push_back(l - i);
    
    sort(qs.begin(), qs.end());
    qs.erase(unique(qs.begin(), qs.end()), qs.end());

    int m = qs.size();
    vector<ll> vs(m);
    for (int i = 0; i < m; i++) vs[i] = skim(qs[i] + 1);

    for (int i = 0; i < K - 1; i++) lb += vs[i];
    if (A <= lb && lb <= 2*A)
    {
        vector<int> res(K);
        iota(res.begin(), res.end(), 1);
        res[K - 1] = r + 1;
        if (res[K - 1] > res[K - 2])
        {
            answer(res);
            return;
        }
    }

    ll cr = 0;
    vector<signed> taken;
    for (int i = 0; i < K; i++)
    {
        taken.push_back(qs[i] + 1);
        cr += vs[i];
    }

    auto check = [&](ll v, vector<int> ind)
    {
        if (v < A || 2*A < v) return false;

        vector<int> res(ind.end() - K, ind.end());
        answer(res);

        return true;
    };

    if (check(cr, taken)) return;

    for (int i = K; i < m; i++)
    {
        cr -= vs[i - K];
        cr += vs[i];
        taken.push_back(qs[i] + 1);
        if (check(cr, taken)) 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