Submission #723502

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

books

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

using namespace std;

vector<long long> seq;

void solve(int N, int K, long long A, int S)
{
    auto okay = [A](__int128 sum)
    {
        return sum >= (__int128) A and sum <= (__int128) 2 * A;
    };

    // invariant: seq[low] <= A, seq[high] > A
    int low = 0, high = N + 1;

    while(high - low >= 2)
    {
        int mid = (high + low) / 2;
        if(skim(mid) > A) high = mid;
        else                low = mid;
    }

    int first_large = high;
    fprintf(stderr, "%d\n", first_large);
    if(first_large < K) impossible();

    vector<long long> small;
    for(int i = 1; i <= K; ++i) small.push_back(skim(i));

    if(first_large <= N)
    {
        long long first_large_val = skim(first_large);

        if(okay(accumulate(small.begin(), small.end() - 1, first_large_val)))
        {
            vector<int> sol(K, first_large);
            iota(sol.begin(), sol.end() - 1, 1);
            answer(sol);
        }
    }

    if(first_large <= K) impossible();
    if(accumulate(small.begin(), small.end(), (__int128) 0) > (__int128) 2 * A)
        impossible();

    vector<long long> medium;
    for(int i = first_large - K; i < first_large; ++i) medium.push_back(skim(i));
    if(accumulate(medium.begin(), medium.end(), (__int128) 0) < (__int128) A)
        impossible();

    vector<int> sol(K); iota(sol.begin(), sol.end(), 1);
    __int128 sum = accumulate(small.begin(), small.end(), (__int128) 0);

    for(int curr = K - 1; ; --curr)
    {
        if(okay(sum)) answer(sol);

        assert(curr >= 0);
        sum -= small[curr]; sum += medium[curr];
        sol[curr] = first_large - K + curr;
    }
}

• 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