Submission #722539

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

books

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

#define X first
#define Y second
#define pb push_back

using namespace std;

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

//     g++ books_sample.cpp sample_grader.cpp


void solve(int n, int k, long long a, int s) {
    int cnt = 0; 

    vector<int> ans; 
    vector<pair<int, ll>> v1, v2;
    int lo = 1, hi = n + 1;

    while(hi - lo > 1) {
        int mi = (lo + hi) / 2; cnt++; 
        if(skim(mi) >= a) hi = mi;
        else lo = mi; 
    }
    ll sum = skim(hi); cnt++; 
    if(hi != n + 1 && sum <= 2 * a) {
        ans.pb(hi); 
        for(int i = 1; i < k; i++) {
            ll res = skim(i); cnt++;
            sum += res; 
            ans.pb(i);
            v1.pb({i,res});
        }     
        assert(cnt <= s);
        if(sum <= 2 * a) {
            answer(ans); 
            return;
        } 
    }
    sum = 0;
    ans.clear();  
    v1.pb({k, skim(k)}); cnt++;
    for(int i = hi - 1; i && k; i--, k--) {
        v2.pb({i, skim(i)}); cnt++;
        sum += v2.back().Y; 
        ans.pb(i);
    }

    assert(cnt <= s);

    if(sum >= a && sum <= 2 * a) {
        answer(ans); 
        return;   
    }
    for(pair<int, ll> p : v1) {
        sum -= v2.back().Y; 
        sum += p.Y; 
        ans.pop_back(); 
        ans.pb(p.X); 
        if(sum >= a && sum <= 2 * a) {
            answer(ans);
            return; 
        }
    }
    impossible(); 
}

• 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