Submission #1216095

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216095		ProtonDecay314	Gap (APIO16_gap)	C++20	30 / 100	38 ms	5932 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

void solve_t2(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);
    // cerr << mn << " " << mx << endl;

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

        solve_t2(nums, nl, nm, N);
        solve_t2(nums, nm + 1ll, nr, N);
    } 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);
    } 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: 0 / 70