제출 #1122686

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

Main

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
const int MXN = 300000;

int N; 
vector<int> a, b, c, o;

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;

}

bool gr = false;
bool fl = false;

bool 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(gr && a[i] > b[j]) return fl;
            if(!gr && a[i] < b[j]) return fl;
            j++;
        }
    }
    return !fl;
};

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> N;
    a.resize(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());

    o.resize(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]; });

    b.resize(N);
    c.resize(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());

    auto find_range = [&] (int o, vector<int>& b) {
        fl = !fl;
        int l = check_lo(o, b) + fl - 1;
        fl = !fl;
        int r = bsmax(0, N, [&] (int x) {
            return check_lo(x + o, b);
        }) + fl;
        return make_pair(l, r);
    };

    auto check = [&] (int x) {

        gr = false;
        for(int& bi : b) bi -= x;
        for(int& ci : c) ci -= x;

        fl = false;
        auto [l1, r1] = find_range(0, b);
        auto [l5, r5] = find_range(0, c);
        fl = true;
        auto [l3, r3] = find_range(N, c);
        auto [l7, r7] = find_range(N, b);

        for(int& bi : b) bi += x;
        for(int& ci : c) ci += x;

        gr = true;
        for(int& bi : b) bi += x;
        for(int& ci : c) ci += x;
        fl = true;
        auto [l4, r4] = find_range(0, b);
        auto [l8, r8] = find_range(0, c);
        fl = false;
        auto [l2, r2] = find_range(N, c);
        auto [l6, r6] = find_range(N, b);
        for(int& bi : b) bi -= x;
        for(int& ci : c) ci -= x;

        bool good = false;
        {
            int l = max(l1, l2), r = min(r1, r2);
            int rl = min(l3, l4), rr = max(r3, r4);
            good = good || ((l <= r) && ((l <= rl) || (rr <= r)));
        }
        {
            int l = max(l5, l6), r = min(r5, r6);
            int rl = min(l7, l8), rr = max(r7, r8);
            good = good || ((l <= r) && ((l <= rl) || (rr <= r)));
        }
        return good;
    };

    int 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