oj.uz

답안 #1042351

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1042351 2024-08-02T22:25:45 Z erray Growing Vegetables is Fun 5 (JOI24_vegetables5) C++17
0 / 100
 1280 ms 16024 KB 
#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;
          } else {
            end_good = i;
          }
          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);
      vector<bool> res(N);
      for (int i = 0; i < N; ++i) {
        res[i] = (s[i] + r[N - i]) == N;
      }
      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);
    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';
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1280 ms 15828 KB Output is correct
2 Incorrect 1103 ms 16024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -