Submission #619534

#	Time	Username	Problem	Language	Result	Execution time	Memory
619534		yuto1115	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	1 ms	344 KiB

books

#include "books.h"
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < ll(n); ++i)
#define rep2(i, s, n) for(ll i = ll(s); i < ll(n); ++i)
#define rrep(i, n) for(ll i = ll(n) - 1; i >= 0; --i)
#define rrep2(i, n, t) for(ll i = ll(n) - 1; i >= ll(t); --i)
#define pb push_back
#define eb emplace_back
#define all(a) a.begin(), a.end()
#define SZ(a) int(a.size())
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vp = vector<P>;
using vvp = vector<vp>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vs = vector<string>;
const int inf = 1001001001;
const ll linf = 1001001001001001001;

template<class T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

void solve(int n, int k, ll a, int s) {
    vl head(k);
    rep(i, k) head[i] = skim(i + 1);
    ll sum = accumulate(all(head), 0LL);
    if (sum > 2 * a) impossible();
    if (sum >= a) {
        vi ans(k);
        iota(all(ans), 1);
        answer(ans);
    }
    auto LB = [&](ll key) -> int {
        int ok = n, ng = -1;
        while (ok - ng > 1) {
            int mid = (ok + ng) / 2;
            if (skim(mid + 1) >= key) ok = mid;
            else ng = mid;
        }
        return ok;
    };
    int r = LB(a);
    assert(r >= k);
    if (r < n) {
        sum += skim(r + 1) - head.back();
        assert(sum >= a);
        if (sum <= 2 * a) {
            vi ans(k);
            iota(all(ans), 1);
            ans.back() = r + 1;
            answer(ans);
        }
        sum -= skim(r + 1) - head.back();
    }
    vl tail(k);
    rep(i, k) tail[i] = skim(r - k + i + 1);
    rrep(i, k) {
        sum += tail[i] - head[i];
        if (sum >= a) {
            assert(sum <= 2 * a);
            vi ans(k);
            iota(all(ans), 1);
            rrep2(j, k, i) ans[j] = r - k + j + 1;
            answer(ans);
        }
    }
    impossible();
}

• 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