Submission #1029888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029888		Muhammet	Gap (APIO16_gap)	C++17	30 / 100	42 ms	3716 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

#define ll long long
#define sz(s) (int)s.size()

ll findGap(int T, int n){
	if(T == 1){
		vector <ll> v, v1;
		ll ans = 0;
		ll k = 0;
		for(int i = 1; i <= (n+1)/2; i++){
			ll s, t, mn, mx;
			if(i == 1) s = 0, t = 1e18;
			else s = v.back()+1, t = v1.back()-1;
			if(s > t) break;
			MinMax(s, t, &mn, &mx);
			if(mn != -1) v.push_back(mn);
			if(mx != -1) v1.push_back(mx);
			k += (t-s+1);
			if(sz(v) > 1) ans = max(ans, (v.back()-v[sz(v)-2]));
			if(sz(v1) > 1) ans = max(ans, (v1[sz(v1)-2]-v1.back()));
			if(i == (n+1)/2) ans = max(ans, v1.back()-v.back());
		}
		return ans;
	}
	else {
		ll s = 0, t = 1e18, mn, mx;
		MinMax(s, t, &mn, &mx);
		ll d = ((mx - mn + n - 2) / (n - 1)), k = mn, ans = d, m = mx, ind = 0;
		for(ll i = mn+1; i + d < m; i += (d + 1)){
			MinMax(i, i + d, &mn, &mx);
			if(mn != -1){
				ans = max(ans, mn-k);
			}
			if(mx != -1){
				k = mx;
			}
			ind = i;
		}

		ll x;
		MinMax(ind,m-1,&mn,&x);
		if(x == -1){
			ans = max(ans,m-k);
		}
		else {
			ans = max(ans,m-x);
		}

		return ans;
	}
}

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