Submission #575317

#	Time	Username	Problem	Language	Result	Execution time	Memory
575317		timreizin	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	3 ms	1104 KiB

books

#include <vector>
#include <deque>
#include "books.h"

using namespace std;

using ll = long long;

void solve(int n, int k, long long a, int s)
{
    vector<ll> x(n + 1);
    ll sum = 0;
    for (int i = 1; i < k; ++i)
    {
        x[i] = skim(i);
        sum += x[i];
    }
    if (sum > 2 * a)
    {
        impossible();
        return;
    }
    if (sum >= a)
    {
        sum += skim(k);
        if (sum > 2 * a) impossible();
        else
        {
            vector<int> res;
            for (int i = 1; i <= k; ++i) res.push_back(i);
            answer(res);
        }
        return;
    }
    //sum of first k - 1 - < a
    ll d = a - sum;
    ll i = 0;
    for (int j = 19; j >= 0; --j)
    {
        if (i + (1 << j) <= n)
        {
            x[i + (1 << j)] = skim(i + (1 << j));
            if (x[i + (1 << j)] <= d + a) i += (1 << j);
        }
    }
    //i = last <= d + a
    if (i < k)
    {
        impossible();
        return;
    }
    if (x[i] >= d)
    {
        vector<int> res;
        for (int i = 1; i < k; ++i) res.push_back(i);
        res.push_back(i);
        answer(res);
        return;
    }
    sum += x[i];
    deque<int> res;
    for (int i = 1; i < k; ++i) res.push_back(i);
    res.push_back(i);
    for (int j = 1, w = i - 1; j < k; ++j, --w)
    {
        if (w == k - 1) break;
        ll val = skim(w);
        sum -= x[j];
        sum += val;
        res.pop_front();
        res.push_back(w);
        if (sum >= a)
        {
            vector<int> res2;
            for (int i : res) res2.push_back(i);
            answer(res2);
        }
    }
    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