Submission #81800

#	Time	Username	Problem	Language	Result	Execution time	Memory
81800		xiaowuc1	Gap (APIO16_gap)	C++14	100 / 100	113 ms	19964 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
 
using namespace std;
 
typedef long long ll;
 
ll onesolve(int n) {
  ll lhs, rhs;
  MinMax(0, 1000000000000000000LL, &lhs, &rhs);
  set<ll> all;
  all.insert(lhs);
  all.insert(rhs);
  n -= 2;
  while(n > 0) {
    MinMax(lhs+1, rhs-1, &lhs, &rhs);
      all.insert(lhs);
  all.insert(rhs);
    n -= 2;
  }
  ll ret = 0;
  ll lowest = *all.begin();
	for(ll out: all) {
		ret = max(ret, out - lowest);
		lowest = out;
	}
	return ret;
}
 
ll twosolve(int n) {
	ll lhs, rhs;
	MinMax(0, 1000000000000000000LL, &lhs, &rhs);
	ll ret = (rhs-lhs+n-2)/(n-1);
	ll endend = rhs;
	// printf("initial guess %lld\n", ret);
	set<ll> all;
	all.insert(lhs);
	all.insert(rhs);
	ll last = lhs+1;
	while(last <= endend) {
		MinMax(last, last + ret, &lhs, &rhs);
		// printf("%lld %lld %lld %lld\n", last, last+ret, lhs, rhs);
		if(lhs >= 0) {
			all.insert(lhs);
			all.insert(rhs);
		}
		last += ret+1;
	}
	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: 30 / 30
• Subtask 2: 70 / 70