Submission #574549

#	Time	Username	Problem	Language	Result	Execution time	Memory
574549		snokes	Building 4 (JOI20_building4)	C++17	0 / 100	546 ms	524288 KiB

building4

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N;
    cin >> N;
    vt<int> A(2 * N + 1), B(2 * N + 1);
    for(int i = 1; i <= 2 * N; i++) cin >> A[i];
    for(int i = 1; i <= 2 * N; i++) cin >> B[i];

    vt<vt<vt<bool>>> dp(2 * N + 1, vt<vt<bool>>(N + 1, vt<bool>(2)));
    dp[0][0] = {true, true};

    for(int i = 1; i <= 2 * N; i++)
    {
        int curA = A[i], curB = B[i];
        int prevA = A[i - 1], prevB = B[i - 1];
        for(int j = 0; j <= N; j++)
        {
            if(j > 0) dp[i][j][0] = (curA >= prevA && dp[i - 1][j - 1][0]) || (curA >= prevB && dp[i - 1][j - 1][1]);
            dp[i][j][1] = (curB >= prevA && dp[i - 1][j][0]) || (curB >= prevB && dp[i - 1][j][1]);
        }
    }

    int curIdx = 0;
    while(curIdx < 2 && !dp[2 * N][N][curIdx]) curIdx++;

    if(curIdx >= 2)
    {
        cout << -1 << "\n";
        return 0;
    }

    string ans(2 * N, '?');
    for(int i = 2 * N, j = N; i > 0; i--)
    {
        assert(dp[i][j][curIdx]);
        int me = curIdx ? B[i] : A[i];
        ans[i - 1] = curIdx ? 'B' : 'A';
        j -= curIdx ^ 1;
        if(dp[i - 1][j][0] && me >= A[i - 1]) curIdx = 0;
        else if(dp[i - 1][j][1] && me >= B[i - 1]) curIdx = 1;
        else assert(false);
    }
    cout << ans << "\n";
}

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