제출 #725543

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
725543		quiet_space	Gap (APIO16_gap)	C++14	100 / 100	58 ms	1864 KiB

gap

#include <bits/stdc++.h>
#include "gap.h"
#define FOR(i,j,k) for(int i=j; i<=k; ++i)
#define ROF(i,j,k) for(int i=j; i>=k; --i)
#define ll long long
const ll inf = 1e18;
ll findGap (int t, int n) {
  if(t == 1) {
    std::vector <ll> v(n+2);
    v[0] = -1, v[n+1] = inf + 1;
    for(int i=1; i<=n-i+1; ++i)
      MinMax (v[i-1]+1, v[n-i+2]-1, &v[i], &v[n-i+1]);
    ll ans = 0;
    FOR(i,2,n) ans = std::max(ans, v[i] - v[i-1]);
    return ans;
  } else {
    ll Mn, Mx, B, ans, lst, L, R;
    MinMax (0, inf, &Mn, &Mx);
    ans = B = (Mx - Mn + n - 2) / (n - 1);
    lst = Mn;
    for(ll i=Mn+1; i<Mx; i+=B) {
      MinMax (i, i+B-1, &L, &R);
      if(L == -1) continue;
      ans = std::max(ans, L - lst);
      lst = R;
    }
    return ans;
  }
}

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