제출 #211638

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
211638		M0REDA	건물 4 (JOI20_building4)	C++14	100 / 100	470 ms	143500 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);
int main()
{
    FAST_IO
    ll n, len;
    cin >> n;
    len = 2 * n;
    vector<vector<ll>> v(len, vector<ll>(2));
    for (int i = 0; i < len; i++)
    {
        cin >> v[i][1];
    }
    for (int i = 0; i < len; i++)
    {
        cin >> v[i][0];
    }
    vector<vector<pair<pair<ll, ll>, ll>>> dp(len, vector<pair<pair<ll, ll>, ll>>(2));
    for (int i = 0; i < len; i++)
    {
        dp[i][0] = {{-1, -1}, -1};
        dp[i][1] = {{-1, -1}, -1};
    }
    dp[0][0] = {{0, 0}, -1};
    dp[0][1] = {{1, 1}, -1};
    for (int i = 0; i < len - 1; i++)
    {
        for (int prev = 0; prev < 2; prev++)
        {
            if (dp[i][prev].first != 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])
                    {
                        continue;
                    }
                    pp = {dp[i][prev].first.first + nxt, dp[i][prev].first.second + nxt};
                    if (dp[i + 1][nxt].first == make_pair((ll)-1, (ll)-1))
                    {
                        dp[i + 1][nxt].first = pp;
                        dp[i + 1][nxt].second = prev;
                    }
                    else
                    {
                        dp[i + 1][nxt].first = {min(dp[i + 1][nxt].first.first, pp.first), max(dp[i + 1][nxt].first.second, pp.second)};

                        if (dp[i + 1][nxt].second == 0)
                        {
                            if (prev == 1)
                            {
                                dp[i + 1][nxt].second = 2;
                            }
                        }
                        else if (dp[i + 1][nxt].second == 1)
                        {
                            if (prev == 0)
                                dp[i + 1][nxt].second = 2;
                        }
                    }
                }
            }
        }
    }
    ll cnt = n;
    string ans = "";
    // debug(dp[len - 1][0].first.first);
    // debug(dp[len - 1][0].first.second);
    // debug(dp[len - 1][1].first.first);
    // debug(dp[len - 1][1].first.second);
    // cout << endl;
    if (!((dp[len - 1][0].first.first <= n && dp[len - 1][0].first.second >= n) || (dp[len - 1][1].first.first <= n && dp[len - 1][1].first.second >= n)))
    {
        cout << -1 << endl;
        return 0;
    }
    bool from2 = false;
    for (int i = len - 1; i >= 0; i--)
    {
        for (int nxt = 0; nxt < 2; nxt++)
        {
            pair<ll, ll> curr = dp[i][nxt].first;
            int prevv = dp[i][nxt].second;
            // debug(i);
            // debug(prevv);
            // debug(curr.first);
            // debug(curr.second);
            // debug(cnt);
            // debug(nxt);
            // cout << endl;
            // cout << "==========" << endl;
            if (from2 && !(cnt >= curr.first && cnt <= curr.second))
            {
                from2 = false;
                nxt = -1;
                continue;
            }
            if (cnt >= curr.first && cnt <= curr.second)
            {
                ans += (nxt == 0 ? "B" : "A");
                cnt -= (nxt == 0 ? 0 : 1);
                if (prevv == 2)
                {
                    if (cnt)
                    {
                        from2 = true;
                        i--;
                        nxt = 0;
                        continue;
                    }
                    else
                    {
                        i--;
                        nxt = -1;
                        continue;
                    }
                }
                if (prevv == 1)
                {
                    i--;
                    nxt = 0;
                    continue;
                }
                if (prevv == 0)
                {
                    i--;
                    nxt = -1;
                    continue;
                }
                break;
            }
        }
    }
    // cout << cnt << endl;
    reverse(ans.begin(), ans.end());
    // cout << ans.size() << endl;
    cout << ans << endl;

    return 0;
}

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