Submission #1025261

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025261		_8_8_	Gap (APIO16_gap)	C++17	70 / 100	45 ms	4804 KiB

gap

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

typedef long long ll;
ll findGap(int tc, int n){
	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: 0 / 30
• Subtask 2: 70 / 70