Submission #875582

#	Time	Username	Problem	Language	Result	Execution time	Memory
875582		NeroZein	Gap (APIO16_gap)	C++17	0 / 100	57 ms	3628 KiB

gap

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

using namespace std; 

long long findGap(int T, int N) {
  long long ret = 0; 
  vector<long long> a(N + 1);
  MinMax(0, LLONG_MAX, &a[1], &a[N]); 
  for (int i = 1; i < N - 1; ++i) {//find i + 1
    long long s = (a[N] - a[i] + N - i - 1) / (N - i) - 1;
    long long z = 0; 
    MinMax(a[i] + 1, a[i] + s, &z, &z); 
    if (z == -1) {
      long long t = 0; 
      for (int j = 60; (1LL << j) >= ret; --j) {
        if ((1LL << j) > a[N]) {
          continue; 
        }
        MinMax(a[i] + 1, a[i] + t + (1LL << j), &z, &z);
        if (z == -1) {
          t += (1 << j); 
        }
      }
      ret = max(ret, t + 1); 
      a[i + 1] = a[i] + t + 1; 
    } else {
      a[i + 1] = z; 
      if (z == a[N]) {
        break; 
      }
    }
  }
  ret = max(ret, a[N] - a[N - 1]); 
  return ret; 
}

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