Submission #1257945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257945		xardkodych	Gap (APIO16_gap)	C++20	30 / 100	28 ms	1864 KiB

gap

// #pragma optimize("Ofast")
#include "bits/stdc++.h"
#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;

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) {
    vi a(n);
    int l = 0, r = n - 1;
    int L = 0, R = INF;
    while (l <= r) {
      auto [f, s] = query(L, R);
      a[l] = f;
      a[r] = s;
      L = f + 1;
      R = s - 1;
      l++;
      r--;
    }
    int res = 0;
    for (int i = 1; i < n; i++) {
      res = max(res, a[i] - a[i - 1]);
    }
    answer = res;
  }
};

int findGap(int32_t t, int32_t n) {
  solver sol(t, n);
  return sol.answer;
}

#undef int

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