Submission #1172527

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172527		perchuts	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	1 ms	416 KiB

books

#include <bits/stdc++.h>

#include "books.h"

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 SequalsN(int n, int k, long long a, int s) {
    vector<int> v(n);
    for (int i = 0; i < n; ++i) v[i] = skim(i+1);
    int smol = 0, large = 0;
    for (int i = 0; i < k; ++i) smol += v[i], large += v[n-1-i];
    if (2*a < smol or large < a) impossible();
    if (a <= smol) {
        vector<int> ans(k);
        iota(begin(ans), end(ans), 1);
        answer(ans);
    }
    if (large <= 2*a) {
        vector<int> ans(k);
        iota(begin(ans), end(ans), n-k+1);
        answer(ans);
    }
    for (int i = k; i < n; ++i) {
        int x = smol - v[k-1] + v[i];
        if (a <= x and x <= 2*a) {
            vector<int> ans(k);
            iota(begin(ans), end(ans), 1);
            ans.back() = i+1;
            answer(ans);
        }
    }
    int lim = 0; 
    for (int i = 0; i < n; ++i) if (v[i] < a) lim = i;
    if (lim < k) impossible();
    int smax = 0, cur = smol;
    set<int> ans;
    for (int i = 0; i < k; ++i) smax += v[lim-i], ans.insert(i+1);
    if (smax < a) impossible();
    auto go = [&] () {
        vector<int> resp;
        for (auto x : ans) resp.push_back(x);
        answer(resp);
    };
    for (int i = k-1; ~i; --i) {
        for (int j = i+1; j <= lim-i; ++j) {
            cur += v[j] - v[j-1];
            ans.insert(j+1);
            ans.erase(j);
            if (a <= cur) go();
        }
    }
    assert(false);
}

void solve(int n, int k, long long a, int s) {
    // TODO implement this function
    if (s >= n) {
        SequalsN(n, k, a, s);    
        return;
    }
    assert(false);
}

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