Submission #384049

#	Time	Username	Problem	Language	Result	Execution time	Memory
384049		VodkaInTheJar	Building 4 (JOI20_building4)	C++14	100 / 100	322 ms	45544 KiB

building4

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define endl '\n'

using namespace std;

const int maxn = 5e5 + 3; 
const int inf = 1e9;

int n, a[maxn * 2], b[maxn * 2];
void read()
{
	cin >> n;
    for (int i = 1; i <= n * 2; i++)
        cin >> a[i];

    for (int i = 1; i <= n * 2; i++)
        cin >> b[i];
}

pair <int, int> dp[maxn * 2][2];
void solve()
{
    dp[1][0] ={1, 1};
    dp[1][1] = {0, 0};

    for (int i = 2; i <= n * 2; i++)
    {
        dp[i][0] = dp[i][1] = {inf, -inf};
        if (a[i] >= a[i-1] && dp[i-1][0].first <= dp[i-1][0].second)
        {
            dp[i][0].first = min(dp[i][0].first, dp[i-1][0].first + 1);
            dp[i][0].second = max(dp[i][0].second, dp[i-1][0].second + 1);
        }

        if (a[i] >= b[i-1] && dp[i-1][1].first <= dp[i-1][1].second)
        {
            dp[i][0].first = min(dp[i][0].first, dp[i-1][1].first + 1);
            dp[i][0].second = max(dp[i][0].second, dp[i-1][1].second + 1);
        }

        if (b[i] >= a[i-1] && dp[i-1][0].first <= dp[i-1][0].second)
        {
            dp[i][1].first = min(dp[i][1].first, dp[i-1][0].first);
            dp[i][1].second = max(dp[i][1].second, dp[i-1][0].second);
        }

        if (b[i] >= b[i-1] && dp[i-1][1].first <= dp[i-1][1].second)
        {
            dp[i][1].first = min(dp[i][1].first, dp[i-1][1].first);
            dp[i][1].second = max(dp[i][1].second, dp[i-1][1].second);
        }
    }

    int last = -1, left = n;
    vector <char> ans; 
    if (dp[2 * n][0].first <= n && dp[2 * n][0].second >= n)
    {
        ans.push_back('A');
        last = a[2 * n];
        left--;
    }

    else 
        if (dp[2 * n][1].first <= n && dp[2 * n][1].second >= n)
        {
            ans.push_back('B');
            last = b[2 * n];
        }

    if (last == -1)
    {
        cout << -1 << endl;
        return;
    }
    
    for (int i = 2 * n - 1; i >= 1; i--)
    {
        if (a[i] <= last && dp[i][0].first <= left && dp[i][0].second >= left)
        {
            last = a[i];
            left--;
            ans.push_back('A');
        }

        else 
        {
            last = b[i];
            ans.push_back('B');
        }
    }

    reverse(ans.begin(), ans.end());
    for (auto i: ans)
        cout << i;

    cout << endl; 
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	read();
	solve();
}

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