Submission #1192607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192607		lambd47	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	0 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, ll a, int s){
    vector<int> arr(k+1);
    ll smin=(ll)s;
    smin=0;
    for(int i=1;i<=k;i++){
        arr[i]=skim(i);
        smin+=arr[i];
    }
    if(smin>2*a){
        impossible();
        return;
    }
    if(smin>=a){
        vector<int> x(k);
        iota(x.begin(),x.end(),1);
        answer(x);return;
    }
    smin-=arr[k];
    int l=1;
    int r=n;
    int ans=-1;
    while(l<=r){
        int m=(l+r)/2;
        if(a>skim(m)){
            l=m+1;
            ans=m;
        }
        else r=m-1;
    }

    if(ans!=r){
        ll x=skim(ans+1);
        if(x+smin<= 2*a &&  x+smin>=a){
            vector<int> rr(k-1);
            iota(rr.begin(),rr.end(),1);
            rr.push_back(ans+1);
            answer(rr);
            return;
        }

    }
    if(ans<=k){
        impossible();
        return;
    }
    ll somat=skim(ans)+smin;

    vector<int> resp;
    resp.push_back(ans);
    if(somat >= a){
        for(int i=1;i<k;i++){
            resp.push_back(i);
        }
        answer(resp);
    }
    else{
        for(int i=1;i<k;i++){
            ll val=skim(ans-i);
            resp.push_back(ans-i);
            somat+=val;
            somat-=arr[k-i];
            if(somat >= a && somat<=2*a){
                for(int j=1;j<k-i;j++){
                    resp.push_back(j);
                }
                answer(resp);
                return;
            }

        }

    }
    impossible();
    return;





}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 15
• Subtask 3: 0 / 10
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20