Submission #81651

#	Time	Username	Problem	Language	Result	Execution time	Memory
81651		xiaowuc1	Gap (APIO16_gap)	C++14	0 / 100	41 ms	1736 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"

using namespace std;

typedef long long ll;

ll onesolve(int n) {
	return 0;
}

ll twosolve(int n) {
	ll lhs, rhs;
	MinMax(1, 1000000000000000000LL, &lhs, &rhs);
	ll ret = (rhs-lhs+n-2)/(n-1);
	set<ll> all;
	all.insert(lhs);
	all.insert(rhs);
	ll last = lhs+1;
	while(last <= rhs) {
		MinMax(last, last + ret, &lhs, &rhs);
		if(lhs >= 0) {
			all.insert(lhs);
			all.insert(rhs);
		}
		last += ret;
	}
	ll lowest = *all.begin();
	for(ll out: all) {
		ret = max(ret, out - lowest);
		lowest = out;
	}
	return ret;
}

ll findGap(int t, int n) {
	if(t==1) return onesolve(n);
	else return twosolve(n);
}

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