Submission #262377

#	Time	Username	Problem	Language	Result	Execution time	Memory
262377		my99n	Gap (APIO16_gap)	C++14	30 / 100	68 ms	1976 KiB

gap

#include "gap.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<long long> a;
void findarr (long long low, long long high) {
  long long mnl, mxl, mnr, mxr;
  int mid = (low+high)/2;
  MinMax(low, mid, &mnl, &mxl);
  MinMax(mid+1, high, &mnr, &mxr);
  if (mnl != -1) {
    a.push_back(mnl);
    if (mxl != mnl) a.push_back(mxl);
  }
  if (mnr != -1) {
    a.push_back(mnr);
    if (mxr != mnr) a.push_back(mxr);
  }
  if (mnl != mxl) findarr(mnl+1, mxl-1);
  if (mnr != mxr) findarr(mnr+1, mxr-1);
}
 
long long findGap(int T, int N) {
  long long ans = 0;
  if (T == 1) {
    a.resize(N);
    long long mn, mx;
    long long l = 0, r = 1e18;
    int indl = 0, indr = N-1;
    while (indl <= indr) {
      MinMax(l, r, &mn, &mx);
      if (mn != -1) {
        a[indl++] = mn;
        a[indr--] = mx;
      }
      l = mn+1; r = mx-1;
    }
    for (int i = 1; i < N; i++) {
      ans = max(ans, a[i]-a[i-1]);
    }
  }
  else {
    findarr(0, 1e18);
    sort(a.begin(), a.end());
    for (int i = 1; i < N; i++) {
      ans = max(ans, a[i]-a[i-1]);
    }
  }
	return ans;
}

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