Submission #735694

#	Time	Username	Problem	Language	Result	Execution time	Memory
735694		Charizard2021	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	288 KiB

books

#include "books.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> seq;
bool IsInRange(long long A, long long Sum){
    return Sum >= A && Sum <= (long long)2 * A;
}
void solve(int N, int K, long long A, int S){
    long long low = (long long)0;
    long long high = (long long)N;
    high++;
    while(low + 1 < high){
        long long mid = (low + high)/(long long)2;
        if(skim(mid) > A){
            high = mid;
        }
        else{
            low = mid;
        }
    }
    long long GreaterVal = high;
    if(GreaterVal < K){
        impossible();
    }
    vector<long long> minimum;
    long long SumMinimum = 0;
    for(long long i = 1; i <= K; i++){
        minimum.push_back(skim(i));
        SumMinimum += minimum[i - 1];
    }
    if(GreaterVal <= N){
        long long first_large_val = skim(GreaterVal);
        if(IsInRange(A, SumMinimum - minimum.back() + first_large_val)){
            vector<int> ans(K, GreaterVal);
            for(int i = 0; i < K - 1; i++){
                ans[i] = i + 1;
            }
            answer(ans);
        }
    }
    if(GreaterVal <= K){
        impossible();
    }
    if(SumMinimum > (long long)2 * A){
        impossible();
    }
    vector<long long> Inbetween;
    long long SumInBetween = 0;
    for(long long i = GreaterVal - K; i < GreaterVal; ++i){
        Inbetween.push_back(skim(i));
        SumInBetween += Inbetween[i - GreaterVal + K];
    }
    if(SumInBetween < A){
        impossible();
    }
    vector<int> ans(K);
    for(long long i = 0; i < K; i++){
        ans[i] = i + 1;
    }
    for(long long i = K - 1; ; i--){
        if(IsInRange(A, SumMinimum)){
            answer(ans);
        }
        SumMinimum -= minimum[i];
        SumMinimum += Inbetween[i];
        ans[i] = GreaterVal - K + i;
    }
}

• 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