Submission #1263898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263898		m_bezrutchka	Gap (APIO16_gap)	C++20	19.72 / 100	35 ms	1196 KiB

gap

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

using namespace std;

using ll = long long;
long long largest_gap;

void compute(ll l, ll r) {
	if (largest_gap >= r - l) {
		return;
	}
	if (r - l == 1LL) {
		largest_gap = max({largest_gap, 1LL});
		return;
	}

  ll m = (l + r) / 2;

  ll n_l1 = -1, n_r1 = -1, n_l2 = -1, n_r2 = -1;

  if (r - l == 2LL) {
  	MinMax(l + 1, l + 1, &n_l1, &n_r1);
  	if (n_l1 == -1) {
  		largest_gap = max({largest_gap, 2LL});
  	} else {
  		largest_gap = max({largest_gap, 1LL});
  	}
  	return;
  }

  if(l + 1 <= m) MinMax(l + 1, m, &n_l1, &n_r1);
  if(m + 1 <= r - 1) MinMax(m + 1, r - 1, &n_l2, &n_r2);

  if (n_l1 != -1 && n_l2 != -1) {
  	largest_gap = max({largest_gap, n_l1 - l, n_l2 - n_r1, r - n_r2});
  	compute(n_l1, n_r1);
  	compute(n_l2, n_r2);
  } else if (n_l1 != -1) {
  	largest_gap = max({largest_gap, n_l1 - l, r - n_r1});
  	compute(n_l1, n_r1);
  } else if (n_l2 != -1) {
  	largest_gap = max({largest_gap, n_l2 - l, r - n_r2});
  	compute(n_l2, n_r2);
  } else {
  	largest_gap = max({largest_gap, r - l});
  }
}

ll findGap(int t, int n){
  
  ll cur_s = 0, cur_t = 1e18;

  ll mn, mx;

  MinMax(cur_s, cur_t, &mn, &mx);
  
 	largest_gap = max(0LL, (mx - mn + n - 1) / (n - 1) - 1);

  compute(mn, mx);

  return largest_gap;

}

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