Submission #1012184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012184		asdasdqwer	Gap (APIO16_gap)	C++14	43.01 / 100	63 ms	8708 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;

set<long long> a;
vector<long long> b;

void recur(long long l, long long r) {
  if (r-l <= 1) {
    long long tmpl, tmpr;
    MinMax(l, r, &tmpl, &tmpr);
    if (tmpl == -1) return;
    a.insert(tmpl);a.insert(tmpr);
    return;
  }

  long long m = l + (r-l)/2;

  long long tmpl, tmpr;
  MinMax(l, m-1, &tmpl, &tmpr);
  if (tmpl != -1) {
    a.insert(tmpl);a.insert(tmpr);
    if (tmpl + 1 < tmpr) {
      recur(tmpl+1, tmpr-1);
    }
  }

  MinMax(m, r, &tmpl, &tmpr);
  if (tmpl != -1) {
    a.insert(tmpl);a.insert(tmpr);
    if (tmpl + 1 < tmpr) {
      recur(tmpl+1, tmpr-1);
    }
  }
}

long long findGap(int T, int N) {
  if (T == 1) {
    long long mn = 0, mx = 1e18;
    for (int i=0;i<(N+1)/2;i++) {
      long long tmn, tmx;
      MinMax(mn, mx, &tmn, &tmx);
      if (tmn == -1) break;
      a.insert(tmn);
      a.insert(tmx);
      mn = tmn+1;mx = tmx-1;
    }
  }

  else recur(0, (long long)1e18);
  for (long long x:a)b.push_back(x);

  long long dif = 0;
  for (int i=1;i<N;i++) {
    dif = max(dif, b[i] - b[i-1]);
  }
  return dif;
}

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