제출 #1344923

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1344923		MisterReaper	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	37 / 100	1462 ms	6308 KiB

Main

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

constexpr int inf = int(1E9);

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N;
    std::cin >> N;

    std::vector<int> A(2 * N), B(N), C(N);
    for (int i = 0; i < 2 * N; ++i) {
        std::cin >> A[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> B[i];
    }
    for (int i = 0; i < N; ++i) {
        std::cin >> C[i];
    }

    std::sort(B.begin(), B.end());
    std::sort(C.begin(), C.end());

    debug(B);
    debug(C);

    int ans = inf;
    for (int done = 0; done < 2; ++done) {
        auto check = [&](int x) -> bool {
            // debug("chk:", x);
            std::vector<int> ps(N + 1);
            auto mark_bad = [&](int l, int r) -> void {
                assert(0 <= l && l <= r && r <= N);
                ps[l] += 1;
                ps[r] -= 1;
            };
            for (int i = 0; i < N; ++i) {
                if (std::abs(A[2 * N - 1 - i] - B[i]) > x) {
                    // debug("bad", N - i);
                    mark_bad(N - i, N);
                }
                int l = [&] -> int {
                    int lo = 0, hi = N - i;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (A[i + mid] < B[i] - x) {
                            lo = mid + 1;
                        } else {
                            hi = mid;
                        }
                    }
                    return lo;
                }();
                mark_bad(0, l);
                int r = [&] -> int {
                    int lo = -1, hi = N - i - 1;
                    while (lo < hi) {
                        int mid = (lo + hi + 1) >> 1;
                        if (A[i + mid] > B[i] + x) {
                            hi = mid - 1;
                        } else {
                            lo = mid;
                        }
                    }
                    return lo;
                }();
                mark_bad(r + 1, N - i);
                // debug(i, l, r);
            }
            for (int i = 0; i < N; ++i) {
                if (std::abs(C[i] - A[i]) > x) {
                    // debug("bad", i + 1);
                    mark_bad(i + 1, N);
                }
                int l = [&] -> int {
                    int lo = 0, hi = i + 1;
                    while (lo < hi) {
                        int mid = (lo + hi) >> 1;
                        if (A[2 * N - i - 1 + mid] > C[i] + x) {
                            lo = mid + 1;
                        } else {
                            hi = mid;
                        }
                    }
                    return lo;
                }();
                mark_bad(0, l);
                int r = [&] -> int {
                    int lo = -1, hi = i;
                    while (lo < hi) {
                        int mid = (lo + hi + 1) >> 1;
                        if (A[2 * N - i - 1 + mid] < C[i] - x) {
                            hi = mid - 1;
                        } else {
                            lo = mid;
                        }
                    }
                    return lo;
                }();
                mark_bad(r + 1, i + 1);
                // debug(i, l, r);
            }
            for (int i = 1; i <= N; ++i) {
                ps[i] += ps[i - 1];
            }
            for (int i = 0; i < N; ++i) {
                if (ps[i] == 0) {
                    return true;
                }
            }
            return false;
        };
        int lo = 0, hi = inf;
        while (lo < hi) {
            int mid = (lo + hi) >> 1;
            if (check(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        debug(lo);
        ans = std::min(ans, lo);
        std::swap(B, C);
    }

    std::cout << ans << '\n';

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In lambda function:
Main.cpp:52:29: warning: parameter declaration before lambda trailing return type only optional with '-std=c++2b' or '-std=gnu++2b' [-Wc++23-extensions]
   52 |                 int l = [&] -> int {
      |                             ^~
Main.cpp:65:29: warning: parameter declaration before lambda trailing return type only optional with '-std=c++2b' or '-std=gnu++2b' [-Wc++23-extensions]
   65 |                 int r = [&] -> int {
      |                             ^~
Main.cpp:85:29: warning: parameter declaration before lambda trailing return type only optional with '-std=c++2b' or '-std=gnu++2b' [-Wc++23-extensions]
   85 |                 int l = [&] -> int {
      |                             ^~
Main.cpp:98:29: warning: parameter declaration before lambda trailing return type only optional with '-std=c++2b' or '-std=gnu++2b' [-Wc++23-extensions]
   98 |                 int r = [&] -> int {
      |                             ^~

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