Submission #1015889

#	Time	Username	Problem	Language	Result	Execution time	Memory
1015889		gyg	A Difficult(y) Choice (BOI21_books)	C++17	20 / 100	148 ms	1252 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;
array<lint, MAX_N> a;

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

    lint max_sum = 0;
    for (int i = n - k + 1; i <= n; i++) max_sum += a[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 <= n; i++) a[i] = skim(i);

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

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

            vector<int> ans = {j};
            for (int x : fixed) ans.push_back(x);
            answer(ans);
            return;
        }
        sum += a[f - i + 1], sum -= a[fixed.back()];
        fixed.push_front(f - i + 1), fixed.pop_back();
    }
    impossible();
}

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