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

Compiler report

input/code.cpp: In function 'll findGap(int, ll)':
input/code.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (v.size() == N || mn == mx) break;
           ~~~~~~~~~^~~~
input/code.cpp:4:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, a, b) for (int i=a; i<(b); i++)
                                     ^
input/code.cpp:28:5: note: in expansion of macro 'FOR'
     FOR(i,0,v.size()-1) res = max(res, v[i+1] - v[i]);
     ^~~
output/ccJNEtuX.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 l = 0, r = 1e18 + 1;
    vector<ll> v;

    while (true) {
      ll mn, mx;
      MinMax(l + 1, r - 1, &mn, &mx); // l < x, y < r
      v.pb(mn);
      v.pb(mx);
      if (v.size() == N || mn == mx) break;
      l = mn, r = mx;
    }

    sort(v.begin(), v.end());

    ll res = 0;
    FOR(i,0,v.size()-1) res = max(res, v[i+1] - v[i]);
    return res;
  } else {
    ll l = 0, r = 1e18+1;
    ll mn, mx;
    MinMax(l + 1LL, r - 1LL, &mn, &mx);

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

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

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

      // jump after last group
      // (X X) jump
      //      r
      l = r + 1;
    }

    return res;
  }
}