Submission #1122672

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122672		ksujay2	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	67 / 100	5090 ms	7488 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() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int N; cin >> N;
    vector<int> a(2 * N);
    for(int i = 0; i < 2 * N; i++) cin >> a[i];

    int k = 0;
    while(k < N && a[k] <= a[k + N]) k++;
    rotate(a.begin(), a.begin() + k, a.end());

    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());


    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 = check_lo(o, b) + flipped - 1;
        flipped = !flipped;
        int r = bsmax(0, N, [&] (int x) {
            return check_lo(x + o, b);
        }) + flipped;
        return make_pair(l, r);
    };

    auto check = [&] (int x) {

        for(int& bi : b) bi -= x;
        for(int& ci : c) ci -= x;
        auto [l1, r1] = find_range(0, b);
        flipped = !flipped;
        auto [l3, r3] = find_range(N, c);
        flipped = !flipped;
        for(int& bi : b) bi += x;
        for(int& ci : c) ci += 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());

        for(int& bi : b) bi -= x;
        for(int& ci : c) ci -= x;
        flipped = !flipped;
        auto [l4, r4] = find_range(0, b);
        flipped = !flipped;
        auto [l2, r2] = find_range(N, c);
        for(int& bi : b) bi += x;
        for(int& ci : c) ci += x;

        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());

        int l = max(l1, l2), r = min(r1, r2);
        int rl = min(l3, l4), rr = max(r3, r4);

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

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

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