Submission #404617

#	Time	Username	Problem	Language	Result	Execution time	Memory
404617		ritul_kr_singh	Gap (APIO16_gap)	C++17	100 / 100	66 ms	3160 KiB

gap

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "gap.h"

const ll INF = 1e18;
ll x, y;

ll findGap(int T, int n){
	ll ans = 0;
	if(T == 1){
		vector<ll> a, b;
		ll low = 0, high = INF;
		int done = 0;
		while(done < n){
			MinMax(low, high, &x, &y);
			a.push_back(x);
			++done;
			if(x < y) b.push_back(y), ++done;
			low = x + 1LL;
			high = y - 1LL;
		}
		while(!b.empty()) a.push_back(b.back()), b.pop_back();
		for(int i=1; i<n; ++i) ans = max(ans, a[i]-a[i-1]);
	}else{
		vector<pair<ll, ll>> a;
		ll low, high;
		MinMax(0, INF, &low, &high);
		a.emplace_back(-1, low);
		ll w = (high - low - 2LL) / ((ll)n - 1LL);
		for(ll s=low+1; s<high; s+=w+1){
			MinMax(s, s+w, &x, &y);
			if(x >= 0) a.emplace_back(x, y);
		}

		a.emplace_back(high, -1);

		for(int i=1; i<(int)a.size(); ++i) ans = max(ans, a[i].first - a[i-1].second);
	}
	return ans;
}

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