Submission #1216107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216107		ProtonDecay314	Gap (APIO16_gap)	C++20	52.13 / 100	68 ms	5904 KiB

gap

#include<bits/stdc++.h>
#include "gap.h"
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

// const ll NUM_BUCKETS = 10ll;

vll div_buckets(ll w, ll k) {
    ll base_bucket_size = w / k;
    ll num_buckets_increase = w % k;

    vll res(k, base_bucket_size);

    for(ll i = 0ll; i < num_buckets_increase; i++) {
        res[i]++;
    }

    return res;
}

void solve_t2(vll& nums, ll l, ll r, ll N, ll NUM_BUCKETS) {
    if(((ll)nums.size()) >= N) return;

    if(r - l + 1ll <= 0ll) return;

    ll mn, mx;
    MinMax(l, r, &mn, &mx);

    if(mn == -1ll) return;

    if(mx > mn) {
        nums.pb(mn);
        nums.pb(mx);
        ll nl = mn + 1ll, nr = mx - 1ll;
        ll w = nr - nl + 1ll;

        if(w <= 0ll) return;
        vll buckets = div_buckets(w, NUM_BUCKETS);

        ll cur_l = nl;
        for(ll i = 0ll; i < NUM_BUCKETS; i++) {
            solve_t2(nums, cur_l, cur_l + buckets[i] - 1ll, N, NUM_BUCKETS);
            cur_l += buckets[i];
        }
    } else {
        nums.pb(mn);
        return;
    }
}

void solve_t1(vll& nums, ll l, ll r, ll N) {
    if(((ll)nums.size()) >= N) return;

    if(r - l + 1ll <= 0ll) return;

    ll mn, mx;
    MinMax(l, r, &mn, &mx);

    if(mn == -1ll) return;

    if(mx > mn) {
        nums.pb(mn);
        nums.pb(mx);
        solve_t1(nums, mn + 1ll, mx - 1ll, N);
    } else {
        nums.pb(mn);
        return;
    }
}

ll findGap(int T, int N)
{
    vll ans;

    if(T == 2) {
        solve_t2(ans, 0ll, 1000000000000000000ll, N, (N <= 100ll ? 2ll : 10ll));
    } else {
        solve_t1(ans, 0ll, 1000000000000000000ll, N);
    }

    sort(ans.begin(), ans.end());

    // for(int i = 0; i < N; i++) {
    //     cerr << ans[i] << " ";
    // }
    // cerr << endl;

    ll maxgap = 0ll;

    for(int i = 0; i < N - 1; i++) {
        maxgap = max(maxgap, ans[i + 1] - ans[i]);
    }

	return maxgap;
}

• Subtask 1: 30 / 30
• Subtask 2: 22.1324 / 70