Submission #529076

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

books

#include <bits/stdc++.h>
#include "books.h"

using namespace std;
typedef long long ll;
ll a[100100];
vector<int> ans;

void solve(int N, int K, long long D, int S) {
    ll S1 = 0;
    for (int i=1;i<=K;i++){
        a[i] = skim(i);
        S1 += a[i];
        if (S1 > D*2){
            impossible();
            return;
        }
    }

    int l = 2, r = N, idx = 1;
    while(l<=r){
        int m = (l+r)>>1;
        if (!a[m]) a[m] = skim(m);
        if (a[m] > a[1] + D) r = m-1;
        else l = m+1, idx = m;
    }

    assert(idx>=K-1);
    if (idx<N && S1 - a[K] + a[idx+1] <= D*2){
        for (int i=1;i<=K-1;i++) ans.push_back(i);
        ans.push_back(idx+1);
        answer(ans);
        return;
    }

    assert(idx>=K);

    ll S2 = 0;
    for (int i=idx;i>idx-K;i--){
        if (!a[i]) a[i] = skim(i);
        S2 += a[i];
    }
    if (S2<D) {impossible(); return;}

    for (int i=1;i<=K;i++) ans.push_back(i);
    if (S1>=D && S1<=D*2) {answer(ans); return;}

    for (int i=K;i>=1;i--){
        ans[i-1] = idx - K + i;
        S1 -= a[i];
        S1 += a[idx - K + i];
        if (S1>=D && S1<=D*2) {answer(ans); return;}
    }


}

• 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