Submission #753489

#	Time	Username	Problem	Language	Result	Execution time	Memory
753489		KN200711	Gap (APIO16_gap)	C++14	100 / 100	46 ms	2632 KiB

gap

#include "gap.h"
# include <bits/stdc++.h>
# define ll long long
using namespace std;
ll solve2(int N) {
	ll lw = 0ll, hg = 0ll;
	MinMax(0ll, 1ll * 1e18, &lw, &hg);
	ll diff = hg - lw;
	diff = (diff + 1ll * N - 2ll) / (N - 1ll);
	
	ll ls = -1;
	while(lw < hg) {
		ll mn, mx;
		MinMax(lw, min(1ll * lw + 1ll * diff, (ll) 1e18), &mn, &mx);
		lw += diff + 1ll;
		if(mn == mx && mn == -1) continue;
		
		if(ls == -1) ls = mx;
		else {
			diff = max(diff, mn - ls);
			ls = mx;
		}
	}
	return diff;
}

long long findGap(int T, int N) {
	if(T == 2) return solve2(N);
	vector<ll> arr, arr1;
	arr.clear();
	arr1.clear();
	
	ll lw = 0ll, hg = 1e18;
	for(; (int) arr.size() + (int) arr1.size() < (int) N ;) {
		MinMax(lw, hg, &lw, &hg);
		if(lw != hg) {
			arr.push_back(lw);
			arr1.push_back(hg);
			lw++;
			hg--;
		} else {
			arr.push_back(lw);
		}
	}
	ll diff = 0ll;
	for(int c=arr1.size() - 1;c>=0;c--) {
		arr.push_back(arr1[c]);
	}
	for(int c=0;c + 1<(int) arr.size();c++) {
		diff = max(diff, arr[c + 1] - arr[c]);
	}
	return diff;
}

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