Submission #1267296

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

books

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")
#include "books.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (ll)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 2e5 + 10,SQ=320,LOG=31;
const ll inf = 2e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}

ll n , k,s,a;
ll arr[N];
void solve(int n_,int k_,ll a_,int s_){
    n = n_,k=k_,a=a_,s=s_;
    fill(arr,arr+n+1,-1);
    for(ll i = 1 ;i <= k;i++) arr[i] = skim(i);
    ll l = 0,r=n+1;
    while(r-l>1){
        ll mid = (l+r)>>1;
        if(skim(mid) >= a) r = mid;
        else l = mid;
    }
    if(r <= n) {
        if(r <= k-1) impossible();
        arr[r] = skim(r);
        ll sum = arr[r];
        for(ll i =1 ;i <= k-1;i++) sum += arr[i];
        if(sum <= 2*a){
            vector<int> v;
            for(ll i=1 ;i <= k-1;i++) v.pb(i);
            v.pb(r);
            answer(v);
            return;
        }
    }
    
    for(ll i = r-1;i >= r - k;i--){
        if(arr[i] == -1) arr[i] = skim(i);
    }
    ll sum = 0;
    for(ll i = 1;i <= k;i++) sum += arr[i];
    ll pt = k;
    ll pt2 = r;
    while(pt >= 0){
        if(sum >= a && sum <= 2*a){
            vector<int> v;
            for(ll j =1 ;j <= pt;j++) v.pb(j);
            for(ll j = r - 1 ;j >= pt2;j--) v.pb(j);
            answer(v);
            return;
        }
        sum -= arr[pt];
        pt--;
        pt2--;
        sum += arr[pt2];
    }
    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