Submission #875385

#	Time	Username	Problem	Language	Result	Execution time	Memory
875385		ZeroCool	Gap (APIO16_gap)	C++14	100 / 100	42 ms	3156 KiB

gap

#include <iostream>
#include "gap.h"
#define ll long long
using namespace std;
const ll M = 1e18;
ll l, r, z, p, a, b, sz, f;
 
long long findGap(int T, int N) {
  MinMax(0, M, &a, &b);
  if (T == 1) {
    if (N == 2) return b-a;
    l = a, r = b, f = -1e18;
    for (int i=0; i<(N-1)/2; ++i) {
      MinMax(l+1, r-1, &a, &b);
      f = max(f, a-l);
      f = max(f, r-b);
      l = a, r = b;
    }
    return f;
  }
  l = a+1, r = b, p = a, f = -1e18;
  sz = (b-a)/N;
  f = sz;
  while (l < r) {
    z = min(r, l+sz);
    MinMax(l, z, &a, &b);
    l = z+1;
    f = max(f, a-p);
    if (b != -1) p = b;
  }
  return f;
}

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