제출 #1122664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122664		ksujay2	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	67 / 100	5092 ms	7460 KiB

Main

#include <bits/stdc++.h>
using namespace std;
const int MXN = 300000;

int bsmax(int lo, int hi, function<bool(int)> f)
{
    lo--;
    while (hi > lo)
    {
        int mid = (hi + lo + 1) / 2;
        if (f(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    return lo;
}

int main() {
    int N; cin >> N;
    vector<int> a(2 * N);
    for(int i = 0; i < 2 * N; i++) cin >> a[i];
    vector<int> o(2 * N);
    for(int i = 0; i < 2 * N; i++) o[i] = i;
    sort(o.begin(), o.end(), [&] (int x, int y) { return a[x] < a[y]; });

    vector<int> b(N), c(N);
    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());

    int k = 0;
    while(k < N && a[k] <= a[k + N]) k++;

    bool flipped = false;
    auto check_lo = [&] (int x, vector<int>& b) {
        int j = 0;
        for(int i : o) {
            if((x <= i && i < x + N) || (x - 2 * N <= i && i < x - N)) {
                if(a[i] < b[j]) {
                    return flipped;
                }
                j++;
            }
        }
        return !flipped;
    };

    auto find_range = [&] (int o, vector<int>& b) {
        flipped = !flipped;
        int l = bsmax(0, k, [&] (int x) { 
            return check_lo(x + o, b);
        }) + flipped;

        flipped = !flipped;
        int r = bsmax(k, N, [&] (int x) {
            return check_lo(x + o, b);
        }) + flipped;
        return make_pair(l, r);
    };

    auto range_lo = [&] (int x) {
        for(int& bi : b) bi -= x;
        auto [l1, r1] = find_range(0, b);
        for(int& bi : b) bi += x;

        for(int& ai : a) ai *= -1;
        reverse(o.begin(), o.end());
        for(int& ci : c) ci *= -1, ci -= x;
        reverse(c.begin(), c.end());
        auto [l2, r2] = find_range(N, c);
        for(int& ci : c) ci += x, ci *= -1;
        reverse(c.begin(), c.end());
        for(int& ai : a) ai *= -1;
        reverse(o.begin(), o.end());

        if(flipped)
            return make_pair(min(l1, l2), max(r1, r2));
        else 
            return make_pair(max(l1, l2), min(r1, r2));
    };

    auto check = [&] (int x) {
        auto [l, r] = range_lo(x);

        for(int& ai : a) ai *= -1;
        for(int& bi : b) bi *= -1;
        for(int& ci : c) ci *= -1;
        reverse(o.begin(), o.end());
        reverse(b.begin(), b.end());
        reverse(c.begin(), c.end());
        flipped = !flipped;
        auto [rl, rr] = range_lo(x);
        flipped = !flipped;
        for(int& bi : b) bi *= -1;
        for(int& ci : c) ci *= -1;
        for(int& ai : a) ai *= -1;
        reverse(o.begin(), o.end());
        reverse(b.begin(), b.end());
        reverse(c.begin(), c.end());

        return (l <= r) && ((l <= rl) || (rr <= r));
    };

    int ans = bsmax(0, 1e9, [&] (int x) {
        return !check(x);
    }) + 1;
    swap(b, c);
    ans = min(ans, bsmax(0, 1e9, [&] (int x) {
        return !check(x);
    }) + 1);
    cout << ans << endl;
}

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