Submission #573686

#	Time	Username	Problem	Language	Result	Execution time	Memory
573686		talant117408	A Difficult(y) Choice (BOI21_books)	C++17	0 / 100	10 ms	312 KiB

books

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

#ifndef EVAL
#include "grader.cpp"
#endif
 
using namespace std;
 
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
 
#define pb                  push_back
#define mp                  make_pair
#define all(v)              (v).begin(),(v).end()
#define sz(v)               int((v).size())
#define do_not_disturb      ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl                '\n'
 
int mod = 1e9+7;
 
ll modulo(ll a) {
    return ((a % mod) + mod) % mod;
}
 
ll add(ll a, ll b) {
    return modulo(a + b);
}
 
ll mult(ll a, ll b) {
    return modulo(a * b);
}
 
ll binpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b&1) {
            res = mult(res, a);
        }
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int MX = 1e5+7;
ll val[MX];

ll ask(int i) {
    if (val[i] > 0) return val[i];
    val[i] = skim(i);
    return val[i];
}

void solve(int n, int k, long long a, int s) {
    //~ int l = 1, r = n;
    //~ while (l < r) {
        //~ int mid = (l+r) >> 1;
        //~ if (a < ask(mid)) {
            //~ r = mid;
        //~ }
        //~ else {
            //~ l = mid+1;
        //~ }
    //~ }
    //~ int ind = l;
    //~ if (ask(ind) > 2*a) ind--;
    //~ if (ind < k) {
        //~ impossible();
        //~ return;
    //~ }
    
    //~ ll sum = 0;
    //~ for (int i = 1; i <= k; i++) {
        //~ sum += ask(i);
    //~ }
    //~ if (sum > a * 2) {
        //~ impossible();
        //~ return;
    //~ }
    //~ sum = 0;
    //~ for (int i = ind-k+1; i <= ind; i++) {
        //~ sum += ask(i);
    //~ }
    //~ if (sum < a) {
        //~ impossible();
        //~ return;
    //~ }
    
    //~ sum = ask(ind);
    //~ for (int i = 1; i < k; i++) sum += ask(i);
    //~ if (a <= sum && sum <= 2*a) {
        //~ vector <int> ans(k-1);
        //~ iota(all(ans), 1);
        //~ ans.pb(ind);
        //~ answer(ans);
        //~ return;
    //~ }
    //~ l = 1, r = ind-k;
    //~ while (l <= r) {
        //~ sum = 0;
        //~ int mid = (l+r) >> 1;
        //~ for (int i = mid; i < mid+k; i++) {
            //~ sum += ask(i);
        //~ }
        //~ if (a <= sum && sum <= a*2) {
            //~ vector <int> ans(k);
            //~ iota(all(ans), mid);
            //~ answer(ans);
            //~ return;
        //~ }
        //~ if (sum > 2*a) {
            //~ r = mid-1;
        //~ }
        //~ else {
            //~ l = mid+1;
        //~ }
    //~ }
    //~ impossible();
    for (int i = 1; i <= n-k; i++) {
        ll sum = 0;
        for (int j = i; j < i+k; j++) {
            sum += ask(j);
        }
        if (sum >= a && sum <= 2*a) {
            vector <int> ans(k);
            iota(all(ans), i);
            answer(ans);
            return;
        }
    }
    ll sum = 0;
    for (int i = 1; i < k; i++) {
        sum += ask(i);
    }
    for (int i = k; i <= n; i++) {
        if (ask(i) > a) {
            if (a <= ask(i)+sum && ask(i)+sum <= 2*a) {
                vector <int> ans(k);
                iota(all(ans), 1);
                ans.back() = i;
                answer(ans);
                return;
            }
        }
    }
    impossible();
    
}
/*
15 3 42 170
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
*/

• 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