Submission #712021

#	Time	Username	Problem	Language	Result	Execution time	Memory
712021		nicky4321	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	71 ms	432 KiB

books

#include <bits/stdc++.h>
#include "books.h"
#define ll long long
#define ld long double
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
#define ALL(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector<ll>
#define SZ(x) (int)x.size()
#define CASE int t;cin>>t;for(int ca=1;ca<=t;ca++)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
const int MAX = 1 << 20, MOD = 1e9 + 7;
ll a[MAX], asked[MAX];

// int skim(int x){
//     cout << x << " ";
//     int res;
//     cin >> res;
//     return res;
// }

// void answer(vi v){
//     for(int i : v)
//         cout << i << " ";
//     cout << '\n';
// }

// void impossible(){
//     cout << "impossible\n";
// }

ll ask(int x){
    if(asked[x])
        return a[x];
    asked[x] = 1;
    a[x] = skim(x);
    return a[x];
}

void solve(int n, int k, ll A, int s){
    ll tmp = A;
    int l = 1, r = n;
    while(l < r){
        int mid = (r - l) / 2 + l;
        if(ask(mid) <= tmp)
            l = mid + 1;
        else
            r = mid;
    }
    if(ask(l) <= tmp)
        l++;
    vi v;
    ll sum = 0;
    for(int i = 1;i <= k;i++){
        v.PB(i);
        sum += ask(i);
    }
    if(l <= n){
        sum -= a[k];
        sum += a[l];
        if(A <= sum && sum <= 2 * A){
            v.pop_back();
            v.PB(l);
            answer(v);
            return;
        }
        sum += a[k];
        sum -= a[l];
    }
    for(int i = max(1, l - k);i <= l - 1;i++){
        if(v.back() < i)
            v.PB(i);
        ask(i);
    }
    int base = SZ(v);
    for(int i = 0;i < (1 << base);i++){
        int cnt = 0;
        sum = 0;
        for(int j = 0;j < base;j++){
            if(i >> j & 1){
                cnt++;
                sum += ask(v[j]);
            }
        }
        if(cnt != k)
            continue;
        if(A <= sum && sum <= 2 * A){
            vi ans;
            for(int j = 0;j < base;j++){
                if(i >> j & 1)
                    ans.PB(v[j]);
            }
            sort(ALL(ans));
            answer(ans);
            return;
        }
    }
    impossible();
}

// int main(){
//     IOS
//     // CASE
//         solve(15, 3, 8, 40);
//     return 0;
// }

• 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