Submission #1289119

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289119		edo	A Difficult(y) Choice (BOI21_books)	C++20	0 / 100	2 ms	412 KiB

books

#include <bits/stdc++.h>

using namespace std;
using ll   = long long;
using vi   = vector<int>;
using vll  = vector<ll>;
using vvi  = vector<vi>;
using vvll = vector<vll>;
using pii  = pair<int,int>;
using pll  = pair<ll,ll>;
using ui    = unsigned int;
using ull   = unsigned long long;
using pui   = pair<ui,ui>;
using pull  = pair<ull,ull>;

template<typename T>
using vc = std::vector<T>;


#define YES cout << "YES\n"
#define NO  cout << "NO\n"
#define yes cout << "yes\n"
#define no  cout << "no\n"
#define Yes cout << "Yes\n"
#define No  cout << "No\n"

template<typename T> void sc(T &x) { cin >> x; }
template<typename T, typename U> void sc(pair<T,U> &p) { sc(p.first), sc(p.second); }
template<typename T> void sc(vector<T> &v) { for (auto &x : v) sc(x); }
template<typename... A> void sc(A&... a) { (sc(a), ...); }


template<typename T> void _pt(const T &x){cout << x;}
template<typename T, typename U> void _pt(const pair<T,U> &p){_pt(p.first); cout << ' '; _pt(p.second);}
template<typename T> void _pt(const vector<T> &v){bool f=1; for(auto &x:v){if(!f) cout<<' '; _pt(x); f=0;}}
template<typename... A> void pt(const A&... a){(_pt(a), ...);}


template<typename T, typename U> bool umin(T &a, const U &b) { return b < a ? (a = b, true) : false; }
template<typename T, typename U> bool umax(T &a, const U &b) { return b > a ? (a = b, true) : false; }
template<typename T> T maxel(const vector<T>& v){ return *max_element(v.begin(), v.end()); }
template<typename T> T minel(const vector<T>& v){ return *min_element(v.begin(), v.end()); }
template<typename T> int lb(const vector<T>& v, const T& x){ return lower_bound(v.begin(), v.end(), x) - v.begin(); }
template<typename T> int ub(const vector<T>& v, const T& x){ return upper_bound(v.begin(), v.end(), x) - v.begin(); }
template<typename T> auto lbid(vector<T>& v, const T& x){ return lower_bound(v.begin(), v.end(), x); }
template<typename T> auto ubid(vector<T>& v, const T& x){ return upper_bound(v.begin(), v.end(), x); }

#define GET_MACRO(_1,_2,_3,_4,NAME,...) NAME
#define FOR1(n)            for (int i=0; i<(n); ++i)
#define FOR2(i,n)          for (int i=0; i<(n); ++i)
#define FOR3(i,l,r)        for (int i=(l); i<(r); ++i)
#define FOR4(i,l,r,k)      for (int i=(l); i<(r); i+=(k))
#define FOR(...)           GET_MACRO(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define ROF1(n)            for (int i=(n)-1; i>=0; --i)
#define ROF2(i,n)          for (int i=(n)-1; i>=0; --i)
#define ROF3(i,l,r)        for (int i=(r)-1; i>=(l); --i)
#define ROF4(i,l,r,k)      for (int i=(r)-1; i>=(l); i-=(k))
#define ROF(...)           GET_MACRO(__VA_ARGS__, ROF4, ROF3, ROF2, ROF1)(__VA_ARGS__)
#define all(c)   (c).begin(), (c).end()
#define allr(c)  (c).rbegin(), (c).rend()
#define eb       emplace_back
#define mp       make_pair
#define mt       make_tuple
#define fi       first
#define se       second
#define pb       push_back
#define trav(x,a) for (auto &x : (a))
#define sz(a) ((int)(a).size())
#define mem(a,v) memset(a, v, sizeof(a))
#define nl pt("\n")

#include "books.h"

void solve(int n, int k, ll A, int S) {
    ll limA = 2 * A;
    //1 5 7 8 11
    // 4 2 1 3
    map<int, ll> memo;
    auto ask = [&](int i) {
        if(memo.count(i)) return memo[i];
        return memo[i] = skim(i);
    };
    
    vi x;
    // x[0] = skim(1);
    // x.back() = skim(n);

    ll tot = 0;
    FOR(i, 1, k + 1) {
        tot += ask(i);
        x.pb(i);
    }

    // ll diff = ((x.back() - x[0] + n - 3) / (n - 2));

    if(A <= tot && tot <= limA) {
        answer(x);
        return;
    }
    if(limA < tot) {
        impossible();
        return;
    }

    ll l = 0, h = n - 1;
    while(h - l > 1) {
        ll m = (h + l) / 2;
        // x[m] = skim(m);
        // ll left = x[m] - x[l];
        // ll right = x[h] - x[m];
        // ll razLeft = (left + m - l) / (m - l + 1);
        // ll razRight = (right + h - m) / (h - m + 1);
        if(ask(m) <= A) l = m;
        else h = m;
    }

    if(l != n) {
        ll t = tot - ask(k) + ask(l);
        if(A <= t && t <= limA) {
            x.back() = l;
            answer(x);
            return;
        }
    }
    FOR(k) {
        x[k - 1 - i] = l - i;
        tot -= ask(k - i);
        tot += ask(l - i);
        if(A <= tot && tot <= limA) {
            answer(x);
            return;
        }
    }
    impossible();
}

// int32_t main() {
//     ios::sync_with_stdio(false);
//     cin.tie(nullptr);

//     int t = 1;
//     sc(t);
//     while (t--) solve();
//     return 0;
// }

• 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