Submission #717184

#	Time	Username	Problem	Language	Result	Execution time	Memory
717184		four_specks	Building 4 (JOI20_building4)	C++17	100 / 100	312 ms	65744 KiB

building4

#include <bits/stdc++.h>

using namespace std;

namespace
{
} // namespace

void solve()
{
    int n;
    cin >> n;

    vector<int> a(2 * n), b(2 * n);
    for (int &x : a)
        cin >> x;
    for (int &x : b)
        cin >> x;

    vector dp(2 * n, vector<array<int, 2>>(2, {-1, -1}));

    dp[0][0] = {1, 1};
    dp[0][1] = {0, 0};
    for (int i = 1; i < 2 * n; i++)
    {
        {
            int lo = INT_MAX, hi = -1;
            if (dp[i - 1][0][0] != -1 && a[i] >= a[i - 1])
            {
                lo = min(lo, dp[i - 1][0][0] + 1);
                hi = max(hi, dp[i - 1][0][1] + 1);
            }
            if (dp[i - 1][1][0] != -1 && a[i] >= b[i - 1])
            {
                lo = min(lo, dp[i - 1][1][0] + 1);
                hi = max(hi, dp[i - 1][1][1] + 1);
            }

            if (lo <= hi)
                dp[i][0] = {lo, hi};
        }
        {
            int lo = INT_MAX, hi = -1;
            if (dp[i - 1][0][0] != -1 && b[i] >= a[i - 1])
            {
                lo = min(lo, dp[i - 1][0][0]);
                hi = max(hi, dp[i - 1][0][1]);
            }
            if (dp[i - 1][1][0] != -1 && b[i] >= b[i - 1])
            {
                lo = min(lo, dp[i - 1][1][0]);
                hi = max(hi, dp[i - 1][1][1]);
            }

            if (lo <= hi)
                dp[i][1] = {lo, hi};
        }
    }

    if ((dp[2 * n - 1][0][0] <= n && n <= dp[2 * n - 1][0][1]) || (dp[2 * n - 1][1][0] <= n && n <= dp[2 * n - 1][1][1]))
    {
        string res = "";

        int m = n;
        int last = INT_MAX;
        for (int i = 2 * n - 1; i >= 0; i--)
        {
            if (dp[i][0][0] != -1 && dp[i][0][0] <= m && m <= dp[i][0][1] && a[i] <= last)
            {
                res += 'A';
                m--;
                last = a[i];
            }
            else
            {
                res += 'B';
                last = b[i];
            }
        }
        reverse(res.begin(), res.end());

        cout << res << '\n';
    }
    else
        cout << -1 << '\n';
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);

    solve();

    return 0;
}

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