Submission #252662

#	Time	Username	Problem	Language	Result	Execution time	Memory
252662		ChrisT	Gap (APIO16_gap)	C++17	48.54 / 100	77 ms	1968 KiB

gap

    #include<bits/stdc++.h>
    using namespace std;
    #include "gap.h"
    long long findGap (int t, int n) {
    	if (t == 1) {
    		vector<long long> arr(n+1);
    		long long low = -1, high = 1e18+1;
    		for (int i = 1; i <= (n+1)/2; i++) {
    			MinMax(low+1,high-1,&low,&high);
    			arr[i] = low; arr[n-i+1] = high;
    		}
    		long long mx = 0;
    		for (int i = 1; i < n; i++) {
    			mx = max(mx,arr[i+1] - arr[i]);
    		}
    		return mx;
    	} else {
    		long long mx,mn;
    		MinMax(0,1e18,&mn,&mx);
    		long long go = max(1LL,(mx - mn) / n - 1), ret = 0, lstmx = -1;
    		for (long long cur = mn; cur <= mx; cur += go) {
    			long long ed = min(cur + go-1,mx);
    			long long low,high;
    			MinMax(cur,ed,&low,&high);
    			if (low != -1) {
    				if (~lstmx) ret = max(ret,low - lstmx);
    				lstmx = high;
    			}
    		}
    		return ret;
    	}
    }

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