Submission #1258170

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258170		xardkodych	Gap (APIO16_gap)	C++20	70 / 100	42 ms	3260 KiB

gap

// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define int long long
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define em emplace_back
#define mp make_pair
#define F first
#define S second

using namespace std;
template<class C>
using vec = vector<C>;
using vi = vector<int>;
using vpi = vector<pair<int, int> >;
using pii = pair<int, int>;

void MinMax(long long s, long long t, long long *mn, long long *mx);
const int INF = 1e18;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());

class solver {
public:
  pii query(int a, int b) {
    int u, v;
    MinMax(a, b, &u, &v);
    return {u,v};
  }
  int answer;
  solver(int t, int n) {
    auto [L, R] = query(0, INF); // + n
    int len = R - L + 1;
    int lb = (len - 1 + n - 2) / (n - 1);
    int res = 0;
    vi a;
    for (int i = L; i <= R; i += lb + 1) {
      auto [l,r] = query(i, i + lb);
      a.pb(l);
      a.pb(r);
    }
    sort(all(a));
    FOR(i, 1, a.size()) {
      if (a[i - 1] != -1 && a[i - 1] != a[i]) {
        res = max(res, a[i] - a[i - 1]);
      }
    }
    answer = res;
  }
};

int findGap(int32_t t, int32_t n) {
  if (t == 1) {

  }
  if (t == 2) {
    solver sol(t, n);
    return sol.answer;
  }
}

#undef int

Compilation message (stderr)

gap.cpp: In function 'long long int findGap(int32_t, int32_t)':
gap.cpp:60:1: warning: control reaches end of non-void function [-Wreturn-type]
   60 | }
      | ^

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