Submission #1260592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1260592		julia_08	Gap (APIO16_gap)	C++20	12.89 / 100	47 ms	3852 KiB

gap

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

using namespace std;

using ll = long long;

vector<ll> compute(ll l, ll r){

  if(l == -1) return {};
  if(l == r) return {l};

  ll m = (l + r) / 2;

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

  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);

  vector<ll> v_l = compute(n_l1, n_r1);
  vector<ll> v_r = compute(n_l2, n_r2);

  vector<ll> res;

  res.push_back(l);

  for(auto x : v_l) res.push_back(x);
  for(auto x : v_r) res.push_back(x);

  res.push_back(r);
    
  return res;

}

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

  ll mn, mx;

  MinMax(cur_s, cur_t, &mn, &mx);
  
  vector<ll> a = compute(mn, mx);

  ll ans = 0;

  for(int i=0; i<(n - 1); i++) ans = max(ans, a[i + 1] - a[i]);

  return ans;

}

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