Submission #682034

#	Time	Username	Problem	Language	Result	Execution time	Memory
682034		ParsaS	Building 4 (JOI20_building4)	C++17	100 / 100	213 ms	45508 KiB

building4

// In the name of God
//-MILY-
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
const int N = 1e6 + 5;
int n, a[N], b[N];
pair<int, int> P[N][2];
bool mark[N];

pair<int, int> unite(pair<int, int> x, pair<int, int> y) {
    if (x.fi == -1)
        return y;
    if (y.fi == -1)
        return x;
    return mp(min(x.fi, y.fi), max(x.se, y.se));
}

void solve() {
    cin >> n;
    int m = n;
    n *= 2;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    for (int i = 0; i < n; i++)
        cin >> b[i];
    P[0][0] = mp(1, 1);
    P[0][1] = mp(0, 0);
    for (int i = 1; i < n; i++) {
        int x = a[i], y = b[i];
        int xp = a[i - 1], yp = b[i - 1];
        P[i][0] = P[i][1] = mp(-1, -1);
        if (P[i - 1][0].fi != -1) {
            if (x >= xp) {
                P[i][0] = P[i - 1][0];
            }
            if (y >= xp)
                P[i][1] = P[i - 1][0];
        }
        if (P[i - 1][1].fi != -1) {
            if (x >= yp) {
                P[i][0] = unite(P[i][0], P[i - 1][1]);
            }
            if (y >= yp)
                P[i][1] = unite(P[i][1], P[i - 1][1]);
        }
        if (P[i][0].fi != -1) {
            P[i][0].fi++;
            P[i][0].se++;
        }
    }
    pair<int, int> res = unite(P[n - 1][0], P[n - 1][1]);
    if (m < res.fi || m > res.se) {
        cout << -1 << '\n';
        return;
    }
    string ans;
    bool x = false;
    if (m >= P[n - 1][1].fi && m <= P[n - 1][1].se) {
        x = true;
    }
    int i = n - 1;
    while (i > 0) {
        ans += char(x + 'A');
        m -= !x;
        int val = x ? b[i] : a[i];
        if (a[i - 1] <= val && m >= P[i - 1][0].fi && m <= P[i - 1][0].se)
            x = false;
        else if (b[i - 1] <= val && m >= P[i - 1][1].fi && m <= P[i - 1][1].se)
            x = true;
        i--;
    }
    ans += char(x + 'A');
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
}
int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

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