Submission #577289

#	Time	Username	Problem	Language	Result	Execution time	Memory
577289		two_sides	Building 4 (JOI20_building4)	C++17	100 / 100	325 ms	49148 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int N = 1000005;

int a[N], b[N]; bool inq[N];
queue<int> que;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin >> n; int m = n; n <<= 1;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    for (int i = 0; i + 1 < n; i++) {
        inq[i] = 1; que.push(i);
    }
    while (que.size()) {
        int i = que.front(), mn, mx;
        inq[i] = 0; que.pop();
        if (a[i] < 0 && b[i] < 0)
            return cout << -1, 0;
        if (a[i + 1] < 0 && b[i + 1] < 0)
            return cout << -1, 0;
        if (a[i] < 0) mn = b[i];
        else if (b[i] < 0) mn = a[i];
        else mn = min(a[i], b[i]);
        mx = max(a[i + 1], b[i + 1]);
        bool flag = 0;
        if (a[i] > mx) {
            a[i] = -1; flag = 1;
        }
        if (b[i] > mx) {
            b[i] = -1; flag = 1;
        }
        if (a[i + 1] > 0 && a[i + 1] < mn) {
            a[i + 1] = -1; flag = 1;
        }
        if (b[i + 1] > 0 && b[i + 1] < mn) {
            b[i + 1] = -1; flag = 1;
        }
        if (flag) {
            que.push(i); inq[i] = 1;
            if (i > 0 && !inq[i - 1]) {
                que.push(i - 1); inq[i - 1] = 1;
            }
            if (i + 2 < n && !inq[i + 1]) {
                que.push(i + 1); inq[i + 1] = 1;
            }
        }
    }
    int curl = 0, curr = 0;
    vector<tuple<int, int, int, int>> vec;
    for (int i = 0; i < n; i++) {
        if (a[i] < 0 || b[i] < 0) {
            if (a[i] > 0) {
                curl++; curr++;
                vec.emplace_back(i, i, 1, 1);
            } else vec.emplace_back(i, i, 0, 0);
            continue;
        }
        int j = i;
        while (j + 1 < n && a[j + 1] > 0
        && b[j + 1] > 0 && min(a[j + 1],
        b[j + 1]) < max(a[j], b[j])) j++;
        int cnt = 0;
        for (int k = i; k <= j; k++)
            if (a[k] > b[k]) cnt++;
        int tmpl = cnt, tmpr = cnt;
        for (int k = i; k <= j; k++) {
            if (a[k] > b[k]) cnt--;
            else cnt++;
            tmpl = min(tmpl, cnt);
            tmpr = max(tmpr, cnt);
        }
        vec.emplace_back(i, j, tmpl, tmpr);
        curl += tmpl; curr += tmpr; i = j;
    }
    if (curl > m || curr < m)
        return cout << -1, 0;
    for (auto pp : vec)
        m -= get<2> (pp);
    for (auto pp : vec) {
        int i, j, l, r;
        tie(i, j, l, r) = pp;
        if (a[i] < 0 || b[i] < 0) {
            cout << (a[i] > 0 ? 'A' : 'B');
            continue;
        }
        int need = l + min(m, r - l);
        
        m -= min(m, r - l);
        for (int k = i; k <= j; k++)
            if (a[k] > b[k]) need--;
        if (!need) {
            for (int k = i; k <= j; k++)
                cout << (a[k] > b[k] ? 'A' : 'B');
            goto gg;
        }
        for (int k = i; k <= j; k++) {
            if (a[k] > b[k]) need++;
            else need--;
            if (need == 0) {
                for (int q = i; q <= k; q++)
                    cout << (a[q] > b[q] ? 'B' : 'A');
                for (int q = k + 1; q <= j; q++)
                    cout << (a[q] > b[q] ? 'A' : 'B');
                goto gg;
            }
        }
        gg:;
    }
    assert(m == 0);
}

• Subtask 1: 11 / 11
• Subtask 2: 89 / 89