Submission #1042353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042353		erray	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++17	100 / 100	1717 ms	28156 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/contests/debug.h"
#else 
  #define debug(...) void(37)
#endif

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int N;
  cin >> N;
  vector<int> A(2 * N), C(N), B(N);
  for (int i = 0; i < 2 * N; ++i) {
    cin >> A[i];
  }
  for (int i = 0; i < N; ++i) {
    cin >> B[i];
  }
  for (int i = 0; i < N; ++i) {
    cin >> C[i];
  }
  sort(B.begin(), B.end());
  sort(C.begin(), C.end());
  auto F = [&](int mid) {
    vector<int> ra = A, rb = B, rc = C;
    auto Is_good = [&](vector<int> a, vector<int> x) -> vector<bool> {
      auto Get = [&](bool rev) {
        vector<int> good(N + 1);
        int l = -1, r = 0, p = 0;
        for (int i = 0; i < N; ++i) {
          while (l + 1 < N && a[i] - x[l + 1] > mid) ++l;
          while (r < N && x[r] - a[i] <= mid) ++r;
          if (p == i - 1) ++p;
          while (p > 0 && (!rev ? a[p + N - 1] < a[i] : a[p + N - 1] <= a[i])) --p;
          assert(p == i || (!rev ? a[p + N] < a[i] : a[p + N] <= a[i]));
          assert(p == 0 || (!rev ? a[p + N - 1] >= a[i] : a[p + N - 1] > a[i]));
          if (r - l - 1 < 1) {
            continue;
          }
          int start_good;
          if (i < r) {
            start_good = 0;
          } else if (i - p < r) {
            start_good = i - r + 1;
          } else {
            start_good = N + 1;
          }
          int end_good;
          if (i <= l) {
            end_good = -1;
          } else if (i - p <= l) {
            end_good = i - l - 1;
          } else {
            end_good = i;
          }
          debug(i, l, r, p, start_good, end_good);
          if (start_good <= end_good) {
            good[start_good]++;
            good[end_good + 1]--;
          }
        }
        for (int i = 1; i <= N; ++i) good[i] += good[i - 1];
        return good;
      };
      auto s = Get(false);
      reverse(a.begin(), a.end());
      auto r = Get(true);
      reverse(a.begin(), a.end());

      vector<bool> res(N);
      for (int i = 0; i < N; ++i) {
        res[i] = (s[i] + r[N - i]) == N;
      }
      debug(a, x, s, r, res);

      return res;
    };
    auto b = Is_good(A, B);
    auto c = Is_good(A, C);
    rotate(A.begin(), A.begin() + N, A.end());
    for (auto& x : A) x = -x;  
    for (auto& x : B) x = -x; 
    reverse(B.begin(), B.end());
    for (auto& x : C) x = -x; 
    reverse(C.begin(), C.end());
    auto cyc_b = Is_good(A, C);
    auto cyc_c = Is_good(A, B);
    debug(b, c);
    debug(cyc_b, cyc_c);
    bool good = false;
    for (int i = 0; i < N; ++i) {
      good |= (b[i] && cyc_b[i]) || (c[i] && cyc_c[i]);
    }
    swap(ra, A);
    swap(rb, B);
    swap(rc, C);
    return good;
  };
  int low = 0, high = int(1e9);
  while (low < high) {
    int mid = (low + high) >> 1;
    if (!F(mid)) {
      low = mid + 1;
    } else {
      high = mid;
    }
  }
  cout << low << '\n';
  debug(A, B, C);
  debug(F(2));
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 21 / 21
• Subtask 4: 37 / 37
• Subtask 5: 33 / 33