Submission #824836

#	Time	Username	Problem	Language	Result	Execution time	Memory
824836		xink	Building 4 (JOI20_building4)	C++14	11 / 100	2084 ms	32700 KiB

building4

#include <iostream>
#include <vector>
#include <utility>
#include <sstream>
#include <climits>
#include <cstring>
#include <algorithm>
#define ll long long
#define ld long double
using namespace std;
const ll mod = 1e9 + 7;
const int maxn = 5e5 + 5, maxn1 = 2e3 + 5;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
bool can_construct[maxn1][maxn1][2];
int a[2 * maxn], b[2 * maxn];

void solve()
{
    int n;
    cin >> n;
    for (int i = 0; i < 2 * n; i++)
    {
        cin >> a[i];
    }
    for (int i = 0; i < 2 * n; i++)
    {
        cin >> b[i];
    }
    can_construct[1][0][0] = can_construct[0][1][1] = 1;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            if (i + j < 2)
                continue;

            if (i > 1)
                can_construct[i][j][0] |= can_construct[i - 1][j][0] && a[i + j - 1] >= a[i + j - 2];

            if (j > 1)
                can_construct[i][j][1] |= can_construct[i][j - 1][1] && b[i + j - 1] >= b[i + j - 2];

            if (i != 0 && j != 0)
            {
                can_construct[i][j][0] |= can_construct[i - 1][j][1] && a[i + j - 1] >= b[i + j - 2];
                can_construct[i][j][1] |= can_construct[i][j - 1][0] && b[i + j - 1] >= a[i + j - 2];
            }
        }
    }
    if (!can_construct[n][n][0] && !can_construct[n][n][1])
    {
        cout << "-1";
        return;
    }
    string ans;
    int i = n, j = n, last_pos = (can_construct[n][n][0] ? 0 : 1);
    while (i || j)
    {
        if (i == 0 && j == 1)
        {
            ans.push_back('B');
            break;
        }
        if (j == 0 && i == 1)
        {
            ans.push_back('A');
            break;
        }
        if (last_pos == 0)
        {
            ans.push_back('A');
            if (i > 1 && can_construct[i - 1][j][0] && a[i + j - 1] >= a[i + j - 2])
                last_pos = 0;
            else if (i > 0 && j > 0 && can_construct[i - 1][j][1] && a[i + j - 1] >= b[i + j - 2])
                last_pos = 1;
            i--;
        }
        else
        {
            ans.push_back('B');
            if (j > 1 && can_construct[i][j - 1][1] && b[i + j - 1] >= b[i + j - 2])
                last_pos = 1;
            else if (i > 0 && j > 0 && can_construct[i][j - 1][0] && b[i + j - 1] >= a[i + j - 2])
                last_pos = 0;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans;
}

int main()
{
    // freopen("input_text", "r", stdin);
    // freopen("output_text", "w", stdout);
    // ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t-- > 0)
        solve();
}

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