Submission #228554

#	Time	Username	Problem	Language	Result	Execution time	Memory
228554		Nightlight	Gap (APIO16_gap)	C++14	89.04 / 100	80 ms	1320 KiB

gap

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

const long long maxa = 1e18;

long long diff, mn, mx, T, N;
long long mntp, mxtp, ans = 0, last;
  
void solve1() {
  MinMax(1, maxa, &mn, &mx);
  for(int i = 3; i <= N; i += 2) {
    MinMax(mn + 1, mx - 1, &mntp, &mxtp);
    ans = max(ans, mntp - mn);
    ans = max(ans, mx - mxtp);
    mn = mntp, mx = mxtp;
  }
  ans = max(ans, mx - mn);
}

void solve2() {
  MinMax(1, maxa, &mn, &mx);
  if(N == 2) {
    ans = mx - mn;
    return;
  }
  long long seg = (mx - mn - 1) / (N - 1);
  last = mn;
  for(long long i = mn + 1; i < mx; i += seg) {
    MinMax(i, min(i + seg - 1, mx - 1), &mntp, &mxtp);
    if(mntp != -1) {
      ans = max(ans, mntp - last);
      last = mxtp;
    }
  }
  ans = max(ans, mx - last);
}

long long findGap(int a0, int b1) {
  T = a0, N = b1;
  if(T == 1) {
    solve1();
  }else solve2();
  return ans;
}

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