Submission #1303883

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303883		nathlol2	Gap (APIO16_gap)	C++20	100 / 100	41 ms	3236 KiB

gap

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

ll findGap(int T, int N){
	if(T == 1){
		ll a[N + 1];
		for(int i = 0;i<(N + 1) / 2;i++){
			ll mn, mx;
			if(i == 0){
				MinMax(0, (ll)1e18, &mn, &mx);
			}else{
				MinMax(a[i] + 1, a[N - i + 1] - 1, &mn, &mx);
			}
			a[i + 1] = mn;
			a[N - i] = mx;
		}
		ll ans = 0;
		for(int i = 1;i<N;i++){
			ans = max(ans, a[i + 1] - a[i]);
		}
		return ans;
	}else{
		vector<ll> a;
		ll fi, ls;
		MinMax(0, (ll)1e18, &fi, &ls);
		a.push_back(fi);
		ll l = fi + 1, r = fi + 1, df, op = 0;
		if((ls - fi) % (N - 1) == 0){
			df = (ls - fi) / (N - 1);
		}else{
			df = (ls - fi) / (N - 1) + 1;
		}
		r += df;
		while(l <= ls){
			ll mn, mx;
			MinMax(l, r, &mn, &mx);
			if(mn != -1){
				a.push_back(mn);
				a.push_back(mx);
			}
			l += df + 1;
			r += df + 1;
		}
		ll ans = 0;
		for(int i = 0;i<a.size() - 1;i++){
			ans = max(ans, a[i + 1] - a[i]);
		}
		return ans;
	}
}

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