Submission #1015892

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015892		gyg	A Difficult(y) Choice (BOI21_books)	C++17	45 / 100	1 ms	512 KiB

books

#include "books.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const int MAX_N = 1e5 + 5;

int n, k;
lint tar;
unordered_map<int, lint> val;

bool check() {
    lint min_sum = 0;
    for (int i = 1; i <= k; i++) min_sum += val[i];
    if (min_sum > 2 * tar) return false;

    lint max_sum = 0;
    for (int i = n - k + 1; i <= n; i++) max_sum += val[i];
    if (max_sum < tar) return false;

    return true;
}

void solve(int _n, int _k, lint _tar, int _) {
    n = _n, k = _k, tar = _tar;
    for (int i = 1; i <= k; i++) val[i] = skim(i);
    for (int i = n - k + 1; i <= n; i++) val[i] = skim(i);

    if (!check()) { impossible(); return; }

    deque<int> fixed;
    lint sum = 0;
    for (int i = 1; i <= k - 1; i++) fixed.push_back(i), sum += val[i];

    for (int i = 1; i <= k; i++) {
        lint new_sum = sum + val[n - i + 1];
        if (tar <= new_sum && new_sum <= 2 * tar) {
            vector<int> ans = {n - i + 1};
            for (int x : fixed) ans.push_back(x);
            answer(ans);
            return;
        } else if (new_sum < tar) {
            sum += val[n - i + 1], sum -= val[fixed.back()];
            fixed.push_front(n - i + 1), fixed.pop_back();
            continue;
        }

        int lo = k - i + 1, hi = n - i + 1;
        while (lo != hi) {
            int mid = (lo + hi) / 2;
            if (sum + skim(mid) >= tar) hi = mid;
            else lo = mid + 1;
        }
        // assert(tar <= sum + skim(lo) && sum + skim(lo) <= 2 * tar);
        
        vector<int> ans = {lo};
        for (int x : fixed) ans.push_back(x);
        answer(ans);
        return;
    }
    impossible();
}

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