Submission #549696

#	Time	Username	Problem	Language	Result	Execution time	Memory
549696		ivan24	A Difficult(y) Choice (BOI21_books)	C++14	100 / 100	2 ms	1920 KiB

books

#include <bits/stdc++.h>

#include "books.h"

using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;

ll min(ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}
class Solver{
private:
    ll n,k,a,s;
    vi memo;
    ll query (ll i){
        if (memo[i] == -1) memo[i] = skim(i+1);
        return memo[i];
    }
    ll find_crit (){
        // returns largest idx i
        // query(i) < a
        ll l = 0, r = n-1;
        ll m;
        while (r >= l){
            m = (l+r+1)/2;
            if (l == r && l == m) return m;
            if (query(m) >= a){
                r = m-1;
            }else{
                l = m;
            }
        }
        if (query(0) >= a) return -1;
        return m;
    }
public:
    Solver(int n, int k, ll a, int s): n(n), k(k), a(a), s(s){
        memo.assign(2e5,-1);
    }
    void solve(){
        ll crt = find_crit();
        ll crt_val = -1;
        if (n > crt+1) crt_val = query(crt+1);
        if (crt >= k-1){
            vi inc,idx;
            for (ll i = 0; k > i; i++){
                inc.push_back(query(i));
                idx.push_back(i);
            }
            for (ll i = max(k,crt-k+1); crt >= i; i++){
                inc.push_back(query(i));
                idx.push_back(i);
            }
            for (ll i = k; inc.size() >= i; i++){
                ll sum = 0;
                for (ll j = i-k; i > j; j++) sum += inc[j];
                if (2*a >= sum && sum >= a){
                    vector<int> res;
                    for (ll j = i-k; i > j; j++)
                        res.push_back(idx[j]+1);
                    answer(res);
                    return;
                }
            }
        }
        if (crt_val != -1){
            vi sml;
            ll sum = 0;
            for (ll i = 0; k-1 > i; i++)
                sum += query(i);
            sum += crt_val;
            if (2*a >= sum && sum >= a){
                vector<int> res;
                for (ll i = 0; k-1 > i; i++) res.push_back(i+1);
                res.push_back(crt+1+1);
                answer(res);
                return;
            }
        }
        impossible();
    }
};

void solve(int n, int k, long long a, int s) {
    // TODO implement this function
    Solver mySolver(n,k,a,s);
    mySolver.solve();
}

Compilation message (stderr)

books.cpp: In member function 'void Solver::solve()':
books.cpp:62:39: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   62 |             for (ll i = k; inc.size() >= i; i++){
      |                            ~~~~~~~~~~~^~~~
books.cpp:51:20: warning: 'm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   51 |         if (n > crt+1) crt_val = query(crt+1);
      |                 ~~~^~

• 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