Submission #1192973

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192973		lambd47	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	1 ms	412 KiB

books

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

#define ll long long
using namespace std;

#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define sz(a) ((int) (a).size())

std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());

void solve(int n, int k, long long a, int s){
    int l=1;
    int r=n;

    int ans=0;
    while(l<=r){
        int m=(l+r)/2;
        if(skim(m)<a){
            l=m+1;
            ans=m;
        }else{
            r=m-1;
        }
    }

    vector<int> at;
    vector<ll> arr(k+1);
    ll smin=0;
    L(i,1,k){
        at.push_back(i);
        arr[i]=skim(i);
        smin+=arr[i];
    }

    if(smin>= a && smin<=2*a){
        answer(at);
        return;
    }
    if(ans+1<=n && ans+1>k){
        ll x=skim(ans+1);
        if(x+smin-arr[k]<=2*a){
            at.pop_back();
            at.push_back(ans+1);
            answer(at);
            return;
        }
    }
    if(ans<=k){
        impossible();
        return;
    }
    if(smin>2*a){
        impossible();
        return;
    }

    L(i,0,k-1){
        smin-=arr[at.back()];
        at.pop_back();
        smin+=skim(ans-i);
        if(smin>=a){
            L(j,0,i){
                at.push_back(ans-j);
            }
            answer(at);return;
        }
    }
    impossible();
    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