Submission #827830

#	Time	Username	Problem	Language	Result	Execution time	Memory
827830		QwertyPi	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	1 ms	296 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.
//

long long _skim(int i){
    return skim(i + 1);
}

void _answer(vector<int> v){
    for(auto& i : v) i++;
    answer(v);
}

void solve(int N, int K, long long A, int S) {
    vector<long long> a(K);
    for(int i = 0; i < K; i++){
        a[i] = _skim(i);
    }
    long long s = accumulate(a.begin(), a.end(), 0LL);
    if(s > A * 2) impossible();
    if(A <= s && s <= A * 2){
        vector<int> v; for(int i = 0; i < K; i++) v.push_back(i);
        _answer(v);
    }
    
    long long upper = A * 2; for(int i = 0; i < K - 1; i++) upper -= a[i];
    int lo = K - 1, hi = N - 1;
    while(lo != hi){
        int mid = (lo + hi + 1) / 2;
        long long val = _skim(mid);
        if(val <= upper){
            lo = mid;
        }else{
            hi = mid - 1;
        }
    }

    for(int i = 0; i < K; i++){
        a[K - 1 - i] = _skim(lo - i);
        long long s = accumulate(a.begin(), a.end(), 0LL);
        if(s > A * 2) impossible();
        if(A <= s && s <= A * 2){
            vector<int> v;
            for(int j = 0; j < K - i - 1; j++) v.push_back(j);
            for(int j = K - i - 1; j < K; j++) v.push_back(lo - (K - 1 - j));
            _answer(v);
        }
    }
    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