Submission #832661

#	Time	Username	Problem	Language	Result	Execution time	Memory
832661		erray	Gap (APIO16_gap)	C++17	100 / 100	39 ms	1176 KiB

gap

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

using namespace std;

#ifdef DEBUG 
  #include "/home/eagle/ioi22/d2/debug.h"
#else 
  #define debug(...) void(37)
#endif

long long findGap(int T, int N) {
  debug(T, N);
  long long first = -1;
  long long last = -1;
  const long long inf = (long long) 1e18;
  MinMax(0, inf, &first, &last);
  long long ans = (last - first + N - 2) / (N - 1);
  if (N == 1) {
    return 0;
  } else if (T == 1) {
    long long L = first, R = last;
    for (int i = 0; i < (N - 1) / 2; ++i) {
      long long next_L = -1, next_R = -1;
      MinMax(L + 1, R - 1, &next_L, &next_R);
      ans = max({ans, next_L - L, R - next_R});
      L = next_L, R = next_R;
    }
    ans = max(ans, R - L);
  } else {
    long long cur = first;
    while (cur != last) {
      long long mn = -1, mx = -1;
      long long ask = -1;
      while (mn == -1) {
        ask = (ask == -1 ? ans : min(ask * 2, last - cur));
        MinMax(cur + 1, cur + ask, &mn, &mx);
        debug(mn, mx);
      }
      ans = max(ans, mn - cur);
      cur = mx;
    }
  }
  return ans;
}

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