Submission #875588

#	Time	Username	Problem	Language	Result	Execution time	Memory
875588		NeroZein	Gap (APIO16_gap)	C++17	0 / 100	720 ms	3868 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, -1);
  MinMax(0, LLONG_MAX, &a[1], &a[N]); 
  for (int i = 1; i < N - 1; ++i) {//find i + 1
    if (a[i] == a[N]) {
      break; 
    }
    long long s = (a[N] - a[i] + N - i - 1) / (N - i) - 1;
    if (s == 0) {
      break; 
    }
    long long z = 0; 
    MinMax(a[i] + 1, a[i] + s, &z, &z); 
    if (z == -1) {
      long long t = 0; 
      for (int j = 60; j >= 0; --j) {
        if ((1LL << j) > a[N]) {
          continue; 
        }
        MinMax(a[i] + 1, a[i] + t + (1LL << j), &z, &z);
        if (z == -1) {
          t += (1LL << j); 
        }
      }
      ret = max(ret, t + 1); 
      a[i + 1] = a[i] + t + 1; 
    } else {
      a[i + 1] = z;  
    }
  }
  if (a[N - 1] != -1) {
    ret = max(ret, a[N] - a[N - 1]);     
  }
  return ret; 
}

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