Submission #305085

#	Time	Username	Problem	Language	Result	Execution time	Memory
305085		thuanqvbn03	Building 4 (JOI20_building4)	C++17	100 / 100	367 ms	105336 KiB

building4

//thuanqvbn03
#include <bits/stdc++.h>

using namespace std;

const int MaxN = 1000005;

int n;
int a[MaxN][2];
bool Color[MaxN][2];
pair<int, int> dp[MaxN][2];

void DFS(int i, int j)
{
    if (Color[i][j])
    {
        return;
    }
    Color[i][j] = true;
    int Min = 1e9, Max = -1e9;
    if (a[i][j] <= a[i + 1][0])
    {
        DFS(i + 1, 0);
        Min = min(Min, dp[i + 1][0].first + 1);
        Max = max(Max, dp[i + 1][0].second + 1);
    }
    if (a[i][j] <= a[i + 1][1])
    {
        DFS(i + 1, 1);
        Min = min(Min, dp[i + 1][1].first);
        Max = max(Max, dp[i + 1][1].second);
    }
    dp[i][j] = make_pair(Min, Max);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    n *= 2;
    for (int j = 0; j < 2; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i][j];
        }
    }
    Color[n][0] = Color[n][1] = 1;
    DFS(0, 0);
    if (dp[0][0].first > n / 2 || dp[0][0].first > dp[0][0].second)
    {
        cout << -1;
        return 0;
    }
    int pre = 0, cnt = n / 2;
    for (int i = 1; i <= n; i++)
    {
        if (a[i][0] >= a[i - 1][pre] && cnt - 1 >= dp[i][0].first && cnt - 1 <= dp[i][0].second)
        {
            cnt--;
            cout << 'A';
            pre = 0;
        }
        else
        {
            cout << 'B';
            pre = 1;
        }
    }
    return 0;
}

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