Submission #1341957

#TimeUsernameProblemLanguageResultExecution timeMemory
1341957iamhereforfunBuilding 4 (JOI20_building4)C++20
0 / 100
1 ms344 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 1e6 + 5;
const int K = 1e2 + 5;
const int M = 2e5 + 5;
const int LG = 20;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;

int n, a[N], b[N], cur, type, num;
pair<int, int> dp[N][2]; // range for the number of a[x] in there .-.
string s = "";

inline void solve()
{
    cin >> n;
    for (int x = 1; x <= 2 * n; x++)
    {
        cin >> a[x];
        dp[x][0] = {-1, -1};
        dp[x][1] = {-1, -1};
    }
    for (int x = 1; x <= 2 * n; x++)
    {
        cin >> b[x];
    }
    dp[1][0] = {1, 1};
    dp[1][1] = {0, 0};
    for (int x = 2; x <= 2 * n; x++)
    {
        if (a[x] > a[x - 1] && a[x] > b[x - 1])
        {
            if (dp[x - 1][0] == pair<int, int>{-1, -1})
                dp[x][0] = dp[x - 1][1];
            else if (dp[x - 1][1] == pair<int, int>{-1, -1})
                dp[x][0] = dp[x - 1][0];
            else
                dp[x][0] = {min(dp[x - 1][0].first, dp[x - 1][1].first), max(dp[x - 1][0].second, dp[x - 1][1].second)};
            if (dp[x][0].first != -1)
            {
                dp[x][0].first++;
                dp[x][0].second++;
            }
        }
        else if (a[x] > a[x - 1])
        {
            dp[x][0] = dp[x - 1][0];
            if (dp[x][0].first != -1)
            {
                dp[x][0].first++;
                dp[x][0].second++;
            }
        }
        else if (a[x] > b[x - 1])
        {
            dp[x][0] = dp[x - 1][1];
            if (dp[x][0].first != -1)
            {
                dp[x][0].first++;
                dp[x][0].second++;
            }
        }
        if (b[x] > a[x - 1] && b[x] > b[x - 1])
        {
            if (dp[x - 1][0] == pair<int, int>{-1, -1})
                dp[x][1] = dp[x - 1][1];
            else if (dp[x - 1][1] == pair<int, int>{-1, -1})
                dp[x][1] = dp[x - 1][0];
            else
                dp[x][1] = {min(dp[x - 1][0].first, dp[x - 1][1].first), max(dp[x - 1][0].second, dp[x - 1][1].second)};
        }
        else if (b[x] > a[x - 1])
        {
            dp[x][1] = dp[x - 1][0];
        }
        else if (b[x] > b[x - 1])
        {
            dp[x][1] = dp[x - 1][1];
        }
        // cout << x << "\n";
        // cout << dp[x][0].first << "|" << dp[x][0].second << "\n";
        // cout << dp[x][1].first << "|" << dp[x][1].second << "\n";
    }
    cur = 2 * n;
    num = n;
    type = -1;
    if (dp[2 * n][0].first <= n && n <= dp[2 * n][0].second)
    {
        type = 0;
    }
    if (dp[2 * n][1].first <= n && n <= dp[2 * n][1].second)
    {
        type = 1;
    }
    if (type == -1)
    {
        cout << -1 << "\n";
        return;
    }
    while (cur > 0)
    {
        if (type == 0)
        {
            num--;
            s += 'A';
            // cout << a[cur] << " ";
        }
        else
        {
            s += 'B';
            // cout << b[cur] << " ";
        }
        // cout << num << " " << cur << " " << type << " " << dp[cur][type].first << " " << dp[cur][type].second << "\n";
        if (cur == 1)
            break;
        if (type)
        {
            if (dp[cur - 1][0].first <= num && num <= dp[cur - 1][0].second && b[cur] > a[cur - 1])
            {
                type = 0;
                cur--;
            }
            else
            {
                type = 1;
                cur--;
            }
        }
        else
        {
            if (dp[cur - 1][0].first <= num && num <= dp[cur - 1][0].second && num > 0 && a[cur] > a[cur - 1])
            {
                type = 0;
                cur--;
            }
            else
            {
                type = 1;
                cur--;
            }
        }
    }
    reverse(s.begin(), s.end());
    cout << s;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...