Submission #1133237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133237		Math4Life2020	Gap (APIO16_gap)	C++20	30 / 100	43 ms	3256 KiB

gap

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

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;
		for (ll t=0;t<N;t++) {
			ll ql = x + (t*(y-x-N+1))/N + t;
			ll qr = x + ((t+1)*(y-x-N+1))/N + t;
			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: 0 / 70