제출 #1310005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310005		nekolie	Building 4 (JOI20_building4)	C++20	100 / 100	178 ms	46008 KiB

building4

// So that's how you want it, womanizer?!
// That's rude. It's pure love.
// Then I fight for justice!
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n; cin >> n, n *= 2; string odp;
    int a[n+1], b[n+1], dp[n+1][3][2];
    dp[0][2][0] = dp[0][2][1] = a[0] = b[0] = 0;
    bool czy[n+1][2];
    for (int i = 1; i <= n; i++)
        cin >> a[i], odp += 'x', czy[i][0] = czy[i][1] = false;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        if (a[i] >= max(a[i-1],b[i-1]))
            dp[i][0][0] = dp[i-1][2][0]+1, dp[i][0][1] = dp[i-1][2][1]+1;
        else if (a[i] >= a[i-1])
            czy[i][0] = czy[i-1][0], dp[i][0][0] = dp[i-1][0][0]+1, dp[i][0][1] = dp[i-1][0][1]+1;
        else if (a[i] >= b[i-1])
            czy[i][0] = czy[i-1][1], dp[i][0][0] = dp[i-1][1][0]+1, dp[i][0][1] = dp[i-1][1][1]+1;
        else
            czy[i][0] = true;
        if (b[i] >= max(a[i-1],b[i-1]))
            dp[i][1][0] = dp[i-1][2][0]-1, dp[i][1][1] = dp[i-1][2][1]-1;
        else if (b[i] >= a[i-1])
            czy[i][1] = czy[i-1][0], dp[i][1][0] = dp[i-1][0][0]-1, dp[i][1][1] = dp[i-1][0][1]-1;
        else if (b[i] >= b[i-1])
            czy[i][1] = czy[i-1][1], dp[i][1][0] = dp[i-1][1][0]-1, dp[i][1][1] = dp[i-1][1][1]-1;
        else
            czy[i][1] = true;
        if (czy[i][0] && czy[i][1]) {
            cout << -1 << endl;
            return 0;
        }
        if (czy[i][0] && !czy[i][1])
            dp[i][2][0] = dp[i][1][0], dp[i][2][1] = dp[i][1][1];
        else if (!czy[i][0] && czy[i][1])
            dp[i][2][0] = dp[i][0][0], dp[i][2][1] = dp[i][0][1];
        else
            dp[i][2][0] = min(dp[i][0][0],dp[i][1][0]), dp[i][2][1] = max(dp[i][0][1],dp[i][1][1]);
        //cerr << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << " " << dp[i][2][0] << " " << dp[i][2][1] << endl;
    }
    int j = -1, v = 0;
    if (!czy[n][0] && dp[n][0][0] <= v && dp[n][0][1] >= v)
        j = 0, odp[n-1] = 'A';
    else if (!czy[n][1] && dp[n][1][0] <= v && dp[n][1][1] >= v)
        j = 1, odp[n-1] = 'B';
    if (j == -1)
        cout << -1 << endl;
    else {
        for (int i = n-1; i > 0; i--) {
            if (j == 0) {
                v--;
                if (!czy[i][0] && a[i] <= a[i+1] && dp[i][0][0] <= v && dp[i][0][1] >= v)
                    odp[i-1] = 'A';
                else
                    odp[i-1] = 'B', j = 1;
            }
            else {
                v++;
                if (!czy[i][0] && a[i] <= b[i+1] && dp[i][0][0] <= v && dp[i][0][1] >= v)
                    odp[i-1] = 'A', j = 0;
                else
                    odp[i-1] = 'B';
            }
        }
        cout << odp << endl;
    }
    return 0;
}
/*
zbiór możliwych bilansów zawsze tworzy przedział

A     B       A+B
              [0,0]
[1,1] [-1,-1] [-1,1]
[2,2] [-2,0]  [-2,2]
x     [1,1]   [1,1]
[2,2] [0,0]   [0,2]
[1,3] [-1,1]  [-1,3]
x     [-2,0]  [-2,0]
*/

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