제출 #947392

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
947392		weakweakweak	건물 4 (JOI20_building4)	C++17	100 / 100	184 ms	47596 KiB

building4

//joisc怎麼也有水題阿，雖然我不會，但有猜到梗
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

int n, a[1110000], b[1110000];
pii dp[1110000][2];
pii dead = {10000000, -10000000};

int main () {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n * 2; i++) cin >> a[i];
    for (int i = 1; i <= n * 2; i++) cin >> b[i];
    
    a[0] = b[0] = -1, dp[0][0] = dp[0][1] = {0, 0};
    for (int i = 1; i <= n * 2; i++) dp[i][0] = dp[i][1] = dead;

    for (int i = 1; i <= n * 2; i++) {
        {
            bool y0 = (a[i] >= a[i - 1]) and (dp[i - 1][0] != dead),    y1 = (a[i] >= b[i-1]) and (dp[i - 1][1] != dead); 
            if (y0 and y1) {
                dp[i][0] . fs = min(dp[i - 1][0].fs, dp[i - 1][1].fs) + 1;
                dp[i][0] . sc = max(dp[i - 1][0].sc, dp[i - 1][1].sc) + 1;
            }
            else if (y0) dp[i][0] = {dp[i - 1][0].fs + 1, dp[i - 1][0].sc + 1};
            else if (y1) dp[i][0] = {dp[i - 1][1].fs + 1, dp[i - 1][1].sc + 1};
        }
        {
            bool y0 = (b[i] >= a[i - 1]) and (dp[i - 1][0] != dead),    y1 = (b[i] >= b[i-1]) and (dp[i - 1][1] != dead); 
            if (y0 and y1) {
                dp[i][1] . fs = min(dp[i - 1][0].fs, dp[i - 1][1].fs);
                dp[i][1] . sc = max(dp[i - 1][0].sc, dp[i - 1][1].sc);
            }
            else if (y0) dp[i][1] = dp[i - 1][0];
            else if (y1) dp[i][1] = dp[i - 1][1];
        }
    }

    int now = 2;
    if (dp[n * 2][0] != dead and dp[n * 2][0].fs <= n and dp[n * 2][0].sc >= n) now = 0;
    if (dp[n * 2][1] != dead and dp[n * 2][1].fs <= n and dp[n * 2][1].sc >= n) now = 1;
    if (now == 2) {
        cout << "-1\n";
        return 0;
    }

    string ans;
    int used = 0;
    for (int i = n * 2; i >= 1; i--) {
        int me = a[i];
        if (now == 1) ans += "B", me = b[i];
        else ans += "A", used++;
        if (dp[i - 1][1] != dead and dp[i - 1][1].fs + used <= n and dp[i - 1][1].sc + used >= n and b[i -1] <= me) now = 1;
        else now = 0;
    }
    reverse(ans.begin(), ans.end());
    cout << ans << '\n';
return 0;}

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