Submission #646343

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

books

#include "bits/stdc++.h"
#include "books.h"
 
using namespace std;
 
using ll = long long;
 
map<int, ll> skimmed;
 
void solve(int n, int k, ll A, int s) {
    ll total = 0;
    vector<int> answ;
    for (int i = 1; i <= k; i++) {
        ll ans = skim(i);
        skimmed[i] = ans;
        total += ans;
        answ.push_back(i);
    }
 
    if (total >= A && total <= 2*A) {
        answer(answ);
    }
 
    if (total > 2*A) impossible();
 
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (skimmed[mid] == 0) {
            skimmed[mid] = skim(mid);
        }
        if (skimmed[mid] < A) {
            l = mid + 1;
        } else {
            r = mid - 1;
        }
    }
 
    if (l <= n && l > k) {
        total = 0;
        for (int i = 1; i < k; i++) {
            total += skimmed[i];
        }
        if (skimmed[l] == 0) skimmed[l] = skim(l);
        total += skimmed[l];
 
        answ.clear();
        if (total >= A and total <= 2 * A) {
            for (int i = 1; i < k; i++) {
                answ.push_back(i);
            }
            answ.push_back(l);
            answer(answ);
        }
    }
    l--;
    for (int i = l; i >= l-k+1; i--) {
        if (skimmed[i] == 0) {
            skimmed[i] = skim(i);
        }
    }
    if (l > k) {
        for (int start = 0; start < k; start++) {
            total = 0;
            answ.clear();
            for (int i = 1; i <= start; i++) {
                total += skimmed[i];
                answ.push_back(i);
            }
            for (int j = l; j >= l - k + start + 1; j--) {
                total += skimmed[j];
                answ.push_back(j);
            }
 
            if (total >=A and total <= 2*A) {
                answer(answ);
            }
        }
    }
    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