Submission #1204952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204952		LucaIlie	Growing Vegetables is Fun 5 (JOI24_vegetables5)	C++20	9 / 100	5096 ms	14356 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5;
const int MAX_VAL = 1e9;
int n;
int a[2 * MAX_N + 1], b[MAX_N + 1], c[MAX_N + 1];
int leftPos[2 * MAX_N + 1], rightPos[2 * MAX_N + 1];
int greaterSide[2 * MAX_N + 1];
int mars[2 * MAX_N + 1];
bool startB[2 * MAX_N + 1], startC[2 * MAX_N + 1];

bool checkMatch() {
    bool isMatch = false;
    for (int s = 1; s <= 2 * n; s++) {
        int t = s + n;
        if (t > 2 * n)
            t -= 2 * n;
        // printf("%d %d %d %d\n", s, t, startB[s], startC[t]);
        isMatch |= (startB[s] & startC[t]);
        
    }
    // printf("%d\n", isMatch);
    return isMatch;
}

void checkPositionsForColor(int d, int b[], bool start[]) {
    // printf("\n\nFAC %d\n", d);
    int j;
    j = 0;
    for (int i = 1; i <= n; i++) {
        while (j + 1 <= n && b[j + 1] <= a[i] + d)
            j++;
        rightPos[i] = j;
    }
    j = 0;
    for (int i = 2 * n; i >= n + 1; i--) {
        while (j + 1 <= n && b[j + 1] <= a[i] + d)
            j++;
        rightPos[i] = j;
    }

    j = 1;
    for (int i = 1; i <= n; i++) {
        while (j <= n && b[j] < a[i] - d)
            j++;
        leftPos[i] = j;
    }
    j = 1;
    for (int i = 2 * n; i >= n + 1; i--) {
        while (j <= n && b[j] < a[i] - d)
            j++;
        leftPos[i] = j;
    }

    j = n + 1;
    for (int i = n; i >= 1; i--) {
        while (j + 1 <= 2 * n && a[j + 1] >= a[i])
            j++;
        greaterSide[i] = j;
    }

    j = n + 1;
    for (int i = n + 1; i <= 2 * n; i++) {
        while (j - 1 >= 1 && a[j - 1] > a[i])
            j--;
        greaterSide[i] = j;
    }

    // for (int i = 1; i <= 2 * n; i++)
        // printf("%d %d %d\n", leftPos[i], rightPos[i], greaterSide[i]);
    // printf("\n");

    for (int i = 0; i <= 2 * n; i++)
        mars[i] = 0;

    for (int i = 1; i <= n; i++) {
        int l = n + 1, r = 0;
        for (int s = 1; s <= i; s++) {
            int p = i - s + 1 + max(0, s + n - greaterSide[i]);
            p = i - s + 1;
            for (int j = n + 1; j <= s + n - 1; j++)
                p += (a[j] < a[i]); 
            // printf("%d %d->%d\n", i, s, p);
            if (leftPos[i] <= p && p <= rightPos[i]) {
                l = min(l, s);
                r = max(r, s);
            }
        }
        if (l > r)
            continue;
        // printf("DECI %d %d %d\n", i, l, r);
        mars[l]++;
        mars[r + 1]--;
    }
    for (int i = n + 1; i <= 2 * n; i++) {
        int l = n + 1, r = 0;
        for (int s = i + 1 - n; s <= n; s++) {
            int p = s + n - i + max(0, greaterSide[i] - s);
            p = s + n - i;
            for (int j = s; j <= n; j++)
                p += (a[j] <= a[i]); 
            // printf("%d %d->%d\n", i, s, p);
            if (leftPos[i] <= p && p <= rightPos[i]) {
                l = min(l, s);
                r = max(r, s);
            }
        }
        if (l > r)
            continue;
        // printf("DECI %d %d %d\n", i, l, r);
        mars[l]++;
         mars[r + 1]--;
    }

    for (int i = 1; i <= n; i++) {
        // printf("TIMP %d %d\n", i, mars[i]);
        mars[i] += mars[i - 1];
        start[i] = (mars[i] == n);
    }

    for (int s = n + 1; s <= 2 * n; s++) {
        vector<int> pos;
        for (int i = 0; i < n; i++) 
            pos.push_back((s + i - 1) % (2 * n) + 1);
        sort(pos.begin(), pos.end(), [](int i, int j) {return a[i] < a[j];});

        start[s] = true;
        for (int i = 0; i < n; i++)
            start[s] &= (leftPos[pos[i]] <= i + 1 && i + 1 <= rightPos[pos[i]]);
    }

    // for (int s = 1; s <= 2 * n; s++)
        // printf("%d ", start[s]);
    // printf("\n");
}

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

    int maxval = 0;

    cin >> n;
    for (int i = 1; i <= 2 * n; i++) {
        cin >> a[i];
        maxval = max(maxval, a[i]);
    }
    b[0] = -MAX_VAL;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        maxval = max(maxval, b[i]);
    }
    sort(b + 1, b + 1 + n);
    c[0] = -MAX_VAL;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        maxval = max(maxval, c[i]);
    }
    sort(c + 1, c + 1 + n);

    int l = -1, r = maxval;
    while (r - l > 1) {
        int d = (l + r) / 2;

        checkPositionsForColor(d, b, startB);
        int p = 0;
        for (int i = 1; i <= 2 * n; i++)
            p += startB[i];
        if (p > 0)
            checkPositionsForColor(d, c, startC);
        if (checkMatch())
            r = d;
        else
            l = d;
    }
    
    cout << r << "\n";

    return 0;
}

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