Submission #1025264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025264		_8_8_	Gap (APIO16_gap)	C++17	100 / 100	50 ms	3292 KiB

gap

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

typedef long long ll;
ll findGap(int tc, int n){
	if(tc == 1){
		ll L =0 ,R = 1e18;
		MinMax(L,R,&L,&R);
		ll ret = 0;
		int col = 2;
		while(L < R){
			ll l,r;
			if(col < n)MinMax(L + 1,R -1 ,&l,&r);
			else l = r = -1;
			if(l == -1){
				ret = max(ret,R - L);
			}else{
				ret = max({ret,l - L,R - r});
			}
			col += 2;
			L = l;
			R = r;
		}
		return ret;
	}
	ll L,R;
	MinMax(0,(ll)1e18,&L,&R);
	if(R - L + 1 == n) return 1;
	ll s = (R - L + n - 1) / (n - 1);
	vector<ll> vals;
	for(ll i = L;i <= R;i += s){
		ll nx = min(R,i + s -1);	
		ll _l,_r;
		MinMax(i,nx,&_l,&_r);
		if(_l!=-1 && _l <= nx){
			vals.push_back(_l);
			vals.push_back(_r);
		}
	}
	assert((int)vals.size() >= 2);
	ll ret = 0;
	// for(ll o:vals){
	// 	cout << o << ' ';
	// }
	// cout << '\n';
	for(int i = 1;i < (int)vals.size();i++){
		ret = max(ret,vals[i] - vals[i  - 1]);
	}
	return ret;
}

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