Submission #1090742

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090742		lovrot	Gap (APIO16_gap)	C++17	48.77 / 100	69 ms	12124 KiB

gap

#include "gap.h"
#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define PB push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll OO = 1e18;

int cnt = 0;

pll query(ll a, ll b) { 
	if(a > b) { return {-1, -1}; }
	ll ret, ret_;
	++cnt;
	MinMax(a, b, &ret, &ret_);
	return {ret, ret_};
}

ll solve(ll lst, ll l, ll r, int n) { 
	if(n == 1) { return 0; }
	pll res = query(l, l + (r - l) / (n - 1)); 
	pll res2 = query(res.X + 1, res.Y - 1);
	ll ret = res.X - lst;
	if(res2.X == -1) { 
		ret = max(ret, res.Y - res.X);
	}
	return ret = max(ret, solve(max(lst, res.Y), l + (r - l) / (n - 1) + 1, r, n - 1));
}

ll findGap(int T, int n) {
	cnt = 0;
	pll res = query(0, OO);
	ll ret = solve(res.X, res.X + 1, res.Y, n);
	if(cnt > 3 * n) { return -1; }
	return ret;
}

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