Submission #1320706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320706		crispxx	Gap (APIO16_gap)	C++20	70 / 100	40 ms	1200 KiB

gap

#include "gap.h"

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

bool chmax(ll &a, const ll &b) {
	return a < b ? a = b, true : false;
}

long long findGap(int T, int n) {
	if(T == 1) {
		ll lmn = -1, lmx = 1e18 + 1;
		
		ll ans = 0;
		
		for(int i = 0; i < (n + 1) / 2; i++) {
			ll cmn, cmx;
			
			// assert(lmn + 1 <= lmx - 1);
			
			MinMax(lmn + 1, lmx - 1, &cmn, &cmx);
			
			if(i > 0) {
				// assert(cmn != -1 && cmx != -1 && lmn != -1 && lmx != -1);
				chmax(ans, cmn - lmn);
				chmax(ans, lmx - cmx);
			}
			if(cmn == -1 && cmx == -1) ans = max(ans, lmx - lmn);
			lmn = cmn, lmx = cmx;
		}
		
		assert(lmn != -1);
		
		chmax(ans, lmx - lmn);
		
		return ans;
	} else {
		ll L, R;
		
		MinMax(0, 1e18, &L, &R);
		
		ll lmn = L, lmx = L;
		
		ll B = (R-L+n-2) / (n-1);
		L ++ ;
		ll ans = B;
		
		
		for(int i = 0; 1; i++) {
			ll cl = i * B + L, cr = min(L + (i + 1) * B - 1, R);
			if(cl>R)break;
			
			ll mn, mx;
			
			MinMax(cl, cr, &mn, &mx);
			
			// cout << cl << ' ' << cr << ' ' << mn << ' ' << mx << '\n';
			
			if(lmn != -1 && mn != -1) {
				chmax(ans, mn - lmx);
			}
			
			if(mn != -1) {
				lmn = mn, lmx = mx;
			}
		}
		
		return ans;
	}
}

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