Submission #594523

#	Time	Username	Problem	Language	Result	Execution time	Memory
594523		MohammadAghil	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	1 ms	592 KiB

books

#include <iostream>
#include <algorithm>
#include <functional>
#include <random>
#include <cmath>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <queue>
#include <cassert>
#include <string>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <limits.h>
#include <tuple>
#include "books.h"
//   #pragma GCC optimization ("unroll-loops")
//  #pragma GCC optimization ("O3")
// #pragma GCC target ("avx2")
using namespace std;
typedef long long ll;
typedef pair<ll, int> pp;
#define per(i,r,l) for(int i = (r); i >= (l); i--)
  #define rep(i,l,r) for(int i = (l); i < (r); i++)
     #define all(x) begin(x), end(x)
        #define sz(x) (int)(x).size()
            #define pb push_back
                #define ss second
                     #define ff first
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod = ll(1e9) + 7, maxn = 1e5 + 5, maxg = 15, lg = 22, inf = ll(1e18) + 5;
ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;}

// 4 3 7 0

//int A[4] = {1, 2, 3, 4};
//int skim(int i){
//    return A[i-1];
//}
//void answer(vector<int> v){
//    for(int c: v) cout << c << ' '; cout << endl;
//}
//void impossible(){
//    cout << "IMP\n";
//}

vector<int> his;
int stor[maxn], n, cnt, s;
int ask(int i){
    if(!stor[i]) his.pb(i), cnt++, assert(cnt <= s), stor[i] = skim(i+1);
    return stor[i];
}

int upper(int x){
    int lx = -1, rx = n;
    while(lx + 1 < rx){
        int mid = (lx + rx)>>1;
        if(ask(mid) > x) rx = mid;
        else lx = mid;
    }
    return rx;
}
void solve(int n, int k, ll a, int s) { ::n = n, ::s = s;
    rep(i,0,n) stor[i] = 0;
    his.clear();
    int trg = upper(2ll*a/k);
    vector<int> ans;
    if(trg == n) {
        ll sum = 0;
        rep(i,n-k,n) sum += ask(i), ans.pb(i+1);
        if(sum >= a && sum <= 2*a) answer(ans);
        else impossible();
        return;
    }
    rep(i,max(0,trg-k),trg+1){
        if(i + k - 1 >= n) break;
        ll sum = 0;
        rep(j,i,i+k) sum += ask(j);
        if(sum >= a && sum <= 2*a){
            rep(j,i,i+k) ans.pb(j+1);
            answer(ans);
            return;
        }
    }
    pp mn = {inf, -1};
    for(int p: his) if(ask(p) >= a) mn = min(mn, {ask(p), p});
    if(mn.ff == inf) {
        impossible();
        return;
    }
    ll sum = mn.ff;
    rep(i,0,k-1) {
        sum += ask(i);
        if(sum > 2*a) {
            impossible();
            return;
        }
        ans.pb(i+1);
    } ans.pb(mn.ss+1);
    answer(ans);
    return;
}


//int main(){
//    cin.tie(0) -> sync_with_stdio(0);
//    int k, s; ll a; cin >> n >> k >> a >> s;
//    int trg = upper(2ll*a/k);
//    vector<int> ans;
//    if(trg == n) {
//        ll sum = 0;
//        rep(i,n-k,n) sum += ask(i), ans.pb(i+1);
//        if(sum >= a && sum <= 2*a) answer(ans);
//        else impossible();
//        return 0;
//    }
//    rep(i,trg-k,trg+1){
//        if(i + k - 1 >= n) break;
//        ll sum = 0;
//        rep(j,i,i+k) sum += ask(j);
//        if(sum >= a && sum <= 2*a){
//            rep(j,i,i+k) ans.pb(j+1);
//            answer(ans);
//            return 0;
//        }
//    }
//    pp mn = {inf, -1};
//    for(int p: his) if(ask(p) >= a) mn = min(mn, {ask(p), p});
//    if(mn.ff == inf) return impossible(), 0;
//    ll sum = mn.ff;
//    rep(i,0,k-1) {
//        sum += ask(i);
//        if(sum > 2*a) return impossible(), 0;
//        ans.pb(i+1);
//    } ans.pb(mn.ss+1);
//    answer(ans);
//    return 0;
//}

• 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