Submission #211596

#	Time	Username	Problem	Language	Result	Execution time	Memory
211596		M0REDA	Building 4 (JOI20_building4)	C++14	0 / 100	6 ms	768 KiB

building4

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << ", ";
#define ll long long
#define pb push_back
using namespace std;
#define FAST_IO                       \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
const int MAX = 2 * 500000;
ll n, len;
// vector<ll> a, b;
// string ans = "";
// bitset<MAX> bit;
// void solve1(ll curr)
// {
//     if (ans != "")
//         return;
//     if (curr == len)
//     {
//         if (bit.count() == n && ans == "")
//         {
//             for (int i = 0; i < len; i++)
//             {
//                 if (bit[i])
//                     ans += "A";
//                 else
//                     ans += "B";
//             }
//             cout << ans << endl;
//         }
//     }
//     else if (curr < len)
//     {
//         ll last = (bit[curr - 1] ? a[curr - 1] : b[curr - 1]);
//         if (a[curr] >= last)
//         {
//             bit[curr] = 1;
//             if (curr + 1 <= len)
//                 solve1(curr + 1);
//             bit[curr] = 0;
//         }
//         if (b[curr] >= last)
//         {
//             if (curr + 1 <= len)
//                 solve1(curr + 1);
//         }
//     }
// }
int main()
{
    FAST_IO
    cin >> n;
    len = 2 * n;
    // a.resize(len);
    // b.resize(len);
    vector<vector<ll>> v(len, vector<ll>(2)); // v[i][0] = b , v[i][1] = a
    for (int i = 0; i < len; i++)
    {
        // cin >> a[i];
        cin >> v[i][1];
    }
    for (int i = 0; i < len; i++)
    {
        // cin >> b[i];
        cin >> v[i][0];
    }
    vector<vector<pair<ll, ll>>> dp(len, vector<pair<ll, ll>>(2));
    for (int i = 0; i < len; i++)
    {
        dp[i][0] = {-1, -1};
        dp[i][1] = {-1, -1};
    }
    dp[0][0] = {0, 0};
    dp[0][1] = {1, 1};
    for (int i = 0; i < len - 1; i++)
    {
        for (int prev = 0; prev < 2; prev++)
        {
            if (dp[i][prev] != make_pair((ll)-1, (ll)-1))
            {
                for (int nxt = 0; nxt < 2; nxt++)
                {
                    pair<ll, ll> pp;
                    if (v[i][prev] > v[i + 1][nxt])
                    {
                        // cout << "prev is " << v[i][prev] << " nxt is " << v[i + 1][nxt] << endl;
                        continue;
                    }
                    // cout << "prev is " << v[i][prev] << " nxt is " << v[i + 1][nxt] << endl;

                    pp = {dp[i][prev].first + nxt, dp[i][prev].second + nxt};
                    if (dp[i + 1][nxt] == make_pair((ll)-1, (ll)-1))
                    {
                        // debug(prev);
                        // debug(i + 1);
                        // debug(nxt);
                        // cout << endl;
                        // cout << endl;

                        // cout << "        " << pp.first << " pp " << pp.second << endl;
                        // cout << "==============================" << endl;
                        dp[i + 1][nxt] = pp;
                    }
                    else
                    {
                        dp[i + 1][nxt] = {min(dp[i + 1][nxt].first, pp.first), max(dp[i + 1][nxt].second, pp.second)};
                    }
                }
            }
        }
    }
    ll cnt = n;
    string ans = "";
    if (!((dp[len - 1][0].first <= n && dp[len - 1][0].second >= n) || (dp[len - 1][1].first <= n && dp[len - 1][1].second >= n)))
    {
        cout << -1 << endl;
        return 0;
    }
    for (int i = len - 1; i >= 0; i--)
    {
        for (int nxt = 0; nxt < 2; nxt++)
        {
            if (dp[i][nxt].first <= cnt && cnt <= dp[i][nxt].second)
            {
                // debug(dp[i][nxt].first);
                // debug(dp[i][nxt].second);
                // debug(cnt);
                // debug(nxt);
                // cout << endl;
                // cout << " =============== " << endl;
                if (nxt == 1)
                {
                    cnt--;
                    ans += "A";
                }
                else
                    ans += "B";
                break;
            }
        }
    }
    reverse(ans.begin(), ans.end());
    // cout << ans.size() << endl;
    cout << ans << endl;
    // solve1(1);
    // if (ans == "")
    // {
    //     bit[0] = 1;
    //     solve1(1);
    // }
    // if (ans == "")
    //     cout << -1 << endl;
    return 0;
}

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