Submission #750902

#	Time	Username	Problem	Language	Result	Execution time	Memory
750902		M_W	Gap (APIO16_gap)	C++17	100 / 100	81 ms	5776 KiB

gap

#include <bits/stdc++.h>
// #include "grader.cpp"
#include "gap.h"
using namespace std;

long long findGap(int T, int N){
  set<long long> s;
  long long L, R;
  if(T == 1){
    MinMax(1, 1e18, &L, &R);
    s.insert(L); s.insert(R);
    for(int i = 1; i < (N + 1) >> 1; i++){
      long long qs, qt;
      MinMax(L + 1, R - 1, &qs, &qt);
      s.insert(qs); s.insert(qt);
      L = qs; R = qt;
    }
  }
  else{
    MinMax(1, 1e18, &L, &R);

    long long X = (R - L) / ((N * 1ll) - 1);
    X += (R - L) % ((N * 1ll) - 1) != 0;

    long long qs, qt;
    for(long long i = L + 1; i < R; i += X){
      MinMax(i, i + X - 1, &qs, &qt);
      s.insert(qs); s.insert(qt);
    }
    s.erase(-1ll);
  }

  long long ans = 0, old = L;
  for(auto x : s){
    ans = max(ans, x - old);
    old = x;
  }
  return ans;
}

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