Submission #1218508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218508		tapilyoca	Gap (APIO16_gap)	C++20	70 / 100	41 ms	2356 KiB

gap

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

template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using pll = pair<ll,ll>;
#define pb push_back


long long findGap(int T, int N) {
    if(T == 1) {
        vll a;
        ll lp = 1, rp = 1e18;
        ll mn = -1, mx = 1e18;

        while(a.size() != N) {
            MinMax(lp,rp,&mn,&mx);
            a.pb(mn);
            a.pb(mx);
            lp = mn + 1;
            rp = mx - 1;
        }

        sort(a.begin(),a.end());
        ll ans = -1;
        for(int i = 1; i < N; i++) {
            ans = max(ans, a[i] - a[i-1]);
        }
        return ans;
    }
    
    else {
        vll a;
        ll mn = -1, mx = 1e18;

        MinMax(1,1e18,&mn,&mx);
        ll largest = mx;
        ll smallest = mn;
        a.pb(mn);
        a.pb(mx);
        ll L = (mx - mn + N - 2)/(N - 1);

        // cerr << "Gap size: " << L << endl;
        
        for(ll i = smallest; i <= largest; i += L+1) {
            MinMax(i,i+L,&mn,&mx);
            // cerr << "Querah " << i << " " << i+L << endl;
            if(mn != -1) {
                a.pb(mn);
                if(mn != mx) a.pb(mx);
            }
        }

        sort(a.begin(),a.end());
        ll ans = 0;
        for(int i = 1; i < a.size(); i++) {
            ans = max(ans, a[i] - a[i-1]);
        }
        return ans;
    }
}

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