Submission #1071099

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071099		manhlinh1501	Building 4 (JOI20_building4)	C++17	11 / 100	1859 ms	372544 KiB

building4

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;
const int MAXN = 4e3 + 5;
#define prev ___prev

int N;
int a[MAXN];
int b[MAXN];
bool dp[MAXN][MAXN][2];
array<int, 3> prev[MAXN][MAXN][2];
int ans[MAXN];

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i = 1; i <= 2 * N; i++) cin >> a[i];
    for(int i = 1; i <= 2 * N; i++) cin >> b[i];
    dp[0][0][0] = dp[0][0][1] = true;
    for(int i = 1; i <= 2 * N; i++) {
        if(a[i - 1] <= a[i]) {
            for(int j = 0; j <= N; j++) {
                if(dp[i - 1][j][0]) {
                    dp[i][j][0] = true;
                    prev[i][j][0] = {i - 1, j, 0};
                }
            }
        }
        if(b[i - 1] <= a[i]) {
            for(int j = 0; j <= N; j++) {
                if(dp[i - 1][j][1]) {
                    dp[i][j][0] = true;
                    prev[i][j][0] = {i - 1, j, 1};
                }
            }
        }
        if(a[i - 1] <= b[i]) {
            for(int j = 1; j <= N; j++) {
                if(dp[i - 1][j - 1][0]) {
                    dp[i][j][1] = true;
                    prev[i][j][1] = {i - 1, j - 1, 0};
                }
            }
        }
        if(b[i - 1] <= b[i]) {
            for(int j = 1; j <= N; j++) {
                if(dp[i - 1][j - 1][1]) {
                    dp[i][j][1] = true;
                    prev[i][j][1] = {i - 1, j - 1, 1};
                }
            }
        }
    }

//    for(int i = 1; i <= 2 * N; i++) {
//        for(int j = 0; j <= N; j++)
//            printf("%d %d %d %d\n", i, j, dp[i][j][0], dp[i][j][1]);
//    }
//
//    for(int i = 1; i <= 2 * N; i++) {
//        for(int j = 0; j <= N; j++)
//            printf("%d %d :\n %d %d %d \n %d %d %d\n", i, j, prev[i][j][0][0], prev[i][j][0][1], prev[i][j][0][2], prev[i][j][1][0], prev[i][j][1][1], prev[i][j][1][2]);
//    }
    if(dp[2 * N][N][0]) {
        array<int, 3> cur = {2 * N, N, 0};
        while(cur[0]) {
            ans[cur[0]] = cur[2];
            cur = prev[cur[0]][cur[1]][cur[2]];
        }
        for(int i = 1; i <= 2 * N; i++)
            cout << (ans[i] ? 'B' : 'A');
    } else if(dp[2 * N][N][1]) {
        array<int, 3> cur = {2 * N, N, 1};
        while(cur[0]) {
            ans[cur[0]] = cur[2];
            cur = prev[cur[0]][cur[1]][cur[2]];
        }
        for(int i = 1; i <= 2 * N; i++)
            cout << (ans[i] ? 'B' : 'A');
    } else cout << -1;
    return (0 ^ 0);
}

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