Submission #1286710

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286710		user736482	A Difficult(y) Choice (BOI21_books)	C++20	100 / 100	2 ms	400 KiB

books

#include "books.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353LL
#define INF 1000000001LL
#define POT (1LL<<20)
#define INFL 1000000000000000099LL
#define pii pair<ll,ll>
#define ppi pair<pii,ll>
#define pip pair<ll,pii>
#define ppp pair<pii,pii>
#define vi vector<ll>
#define vii vector<pii>
#define al(x) x.begin(),x.end()
#define rev(x) reverse(al(x))
#define X 18
template<typename T, typename U>
pair<T, U> operator+(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first + b.first, a.second + b.second};
}
template<typename T, typename U>
pair<T, U> operator-(const pair<T, U>& a, const pair<T, U>& b) {
    return {a.first - b.first, a.second - b.second};
}
template<typename T, typename U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os<<"{"<<p.ff<<", "<<p.ss<<"}";
    return os;
}
template<typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    for (size_t i = 0; i < v.size(); ++i) {
        if (i) os << ", ";
        os << v[i];
    }
    os << "}";
    return os;
}
void solve(int N,int K,ll a,int S){
    ll n=N;
    ll k=K;
    ll s=S;
    vi v;
    ll b=0;
    for(ll i=1;i<k;i++){
        v.pb(skim(i));
        b+=v.back();
    }
    ll pocz=k;
    ll kon=n+1;
    ll x,y=INFL;
    while(pocz!=kon){
        ll md=(pocz+kon)/2;
        x=skim(md);
        if(b+x<a)pocz=md+1;
        else {kon=md;y=x;}
    }
    if(b+y<=2*a){
        vector<int>ans;
        for(ll i=1;i<k;i++)ans.pb(i);
        ans.pb(pocz);
        answer(ans);return;
    }
    x=pocz-1;
    if(x<k){
        impossible();return;
    }
    vector<int>ans;
    v.pb(0);
    for(ll i=1;i<=k;i++){
        ans.pb(x);
        b+=skim(x);
        b-=v[v.size()-i]; 
        x--;
        if(b>=a){
            for(ll j=1;j<=k-i;j++)ans.pb(j); 
            answer(ans);
        }
    }
    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