CSES - APIO 2016 - Results
Submission details
Task:Gap
Sender:Yytsi
Submission time:2019-04-14 15:39:57 +0300
Language:C++
Status:COMPILE ERROR

Compiler report

output/ccPqcnJI.o: In function `main':
code.cpp:(.text.startup+0xbd): undefined reference to `findGap(int, int)'
collect2: error: ld returned 1 exit status

Code

#include "gap.h" // oopsie
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;

ll findGap(int T, ll N) {
  if (T == 1) {
    ll v[N];
    int a = 0, b = N - 1;
    ll s = 0, t = 1e18, mn, mx;
    while (a <= b) {
      MinMax(s, t, &mn, &mx);
      v[a] = mn;
      v[b] = mx;
      // a . . . . b  N = 6
      // ) a . . b (  N = 6
      // ) ) a b ( (  N = 6
      s = mn + 1; // s > mn
      t = mx - 1; // t < mx
      a++;
      b--;
    }
    ll res = 0;
    FOR(i,0,N-1) res = max(res, v[i+1] - v[i]);
    return res;
  } else {
    ll s = 0, t = 1e18;
    ll mn, mx;
    MinMax(s, t, &mn, &mx);

    if (N == 2) return mx - mn;

    ll len = mx - mn + 1;
    s = mn + 1;
    ll pr = mn, res = 0;
    // iterate over the array in (i+1, i) pairs
    FOR(i,0,N-1) {
      //  s
      // (X X) jump 
      //    t
      t = s + len / (N - 1);
      MinMax(s, t, &mn, &mx);

      if (mn != -1) {
        res = max(res, mn - pr);
        pr = mx;
      }

      // jump after prev group
      // (X X) jump
      //    t
      s = t + 1;
    }

    return res;
  }
}