Submission #400919

#	Time	Username	Problem	Language	Result	Execution time	Memory
400919		534351	A Difficult(y) Choice (BOI21_books)	C++17	100 / 100	2 ms	332 KiB

books

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

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
    if (a > b) a = b;
}

template<class T, class U>
void ckmax(T &a, U b)
{
    if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define SZ(x) ((int) (x).size())
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)

const int MAXN = 100013;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K, S;
ll A;
vi ans;
ll arr[MAXN];

ll ask(int i)
{
    if (arr[i] != 0)
    {
        return arr[i];
    }
    ll res = skim(i + 1);
    arr[i] = res;
    return res;
}
ll getsum()
{
    ll res = 0;
    for (int x : ans)
    {
        res += ask(x);
    }
    if (A <= res && res <= 2 * A)
    {
        for (int &x : ans)
        {
            x++;
        }
        answer(ans);
    }
    return res;
}
void solve(int n, int k, ll a, int s)
{
    N = n; K = k; A = a; S = s;
    ans.resize(K);
    iota(ALL(ans), 0);
    if (getsum() > 2 * A)
    {
        impossible();
    }
    int lo = K - 1, hi = N - 1;
    while(hi > lo)
    {
        int mid = (hi + lo + 1) >> 1;
        ans[K - 1] = mid;
        if (getsum() > 2 * A) hi = mid - 1;
        else lo = mid;
    }
    ans[K - 1] = lo;
    getsum();
    FORD(i, K - 1, 0)
    {
        ans[i] = ans[i + 1] - 1;
        if (getsum() < A)
        {
            continue;
        }
        lo = i; hi = ans[i];
        while(hi > lo)
        {
            int mid = (hi + lo + 1) >> 1;
            ans[i] = mid;
            if (getsum() > 2 * A) hi = mid - 1;
            else lo = mid;
        }
        ans[i] = lo;
        getsum();
        //ok, now we do a binary search, and i thnk we're guaranteed tow in.
    }
    impossible();
    //send the last guy as far as possible.
    // TODO implement this function
    // if (skim(2) == 42) {
    //     impossible();
    // } else {
    //     answer({1, 3});
    // }
}

• 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