Submission #557934

#	Time	Username	Problem	Language	Result	Execution time	Memory
557934		Ai7081	Gap (APIO16_gap)	C++17	70 / 100	76 ms	7376 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const ll inf = 1e18;

set<ll> s;

long long findGap(int T, int N)
{
    ll ans = 0;
    if (T==1) {
        ll *mi = new ll, *ma = new ll;
        MinMax((ll)1, inf, mi, ma);
        s.insert(*mi);
        s.insert(*ma);
        while (*mi+1 <= *ma-1) {
            MinMax(*mi+1, *ma-1, mi, ma);
            if (*mi==-1) break;
            s.insert(*mi), s.insert(*ma);
        }
        ll pre = inf;
        for (auto it : s) {
            ans = max(ans, it - pre);
            pre = it;
        }
    }
    else if (T==2) {
        ll *allmin = new ll, *allmax = new ll;
        MinMax((ll)1, inf, allmin, allmax);
        ll gap = (*allmax - *allmin + N-2) / (N-1);
        ll now = *allmin+1, last = *allmin;
        while (now < *allmax) {
            ll *mi = new ll, *ma = new ll;
            MinMax(now, now+gap, mi, ma);
            if (*mi != -1) ans = max(ans, *mi - last);
            if (*ma != -1) last = *ma;
            now = now+gap+1;
        }
    }
    return ans;
}

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