Submission #1133243

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133243		Math4Life2020	Gap (APIO16_gap)	C++20	100 / 100	47 ms	3260 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
using ui = __int128;

ll findGap(int T, int N) {
	if (T==1) {
		vector<ll> v1;
		ll x=0; ll y=1e18; ll a=-1; ll b=-1;
		while (x <= y && v1.size()<N) {
			MinMax(x,y,&a,&b);
			if (a==-1) {
				break;
			}
			if (a==b) {
				v1.push_back(a); break;
			} else {
				v1.push_back(a);
				v1.push_back(b);
			}
			x=a+1; y=b-1;
		}
		sort(v1.begin(),v1.end());
		assert(v1.size()==N);
		ll ans = 0;
		for (ll i=0;i<(N-1);i++) {
			ans = max(ans,v1[i+1]-v1[i]);
		}
		return ans;
	} else {
		vector<ll> v1;
		ll x=0; ll y=1e18; ll a=-1; ll b=-1;
		MinMax(x,y,&a,&b);
		x=a;y=b;
		v1.push_back(x); v1.push_back(y);
		for (ll t=0;t<N;t++) {
			ll ql = x + ((ui)t*(ui)(y-x-N+1))/(ui)N + t;
			if (ql==x) {
				ql++;
			}
			ll qr = x + ((ui)(t+1)*(ui)(y-x-N+1))/(ui)N + t;
			if (qr==y) {
				qr--;
			}
			if (ql>qr) {
				continue;
			}
			MinMax(ql,qr,&a,&b);
			if (a!=-1) {
				v1.push_back(a);
				v1.push_back(b);
			}
		}
		sort(v1.begin(),v1.end());
		ll ans = 0;
		for (ll i=0;i<(v1.size()-1);i++) {
			ans = max(ans,v1[i+1]-v1[i]);
		}
		return ans;
	}
}

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