Submission #1173278

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173278		chikien2009	Building 4 (JOI20_building4)	C++20	100 / 100	178 ms	56212 KiB

building4

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a[1000001][2], lb[1000001][2], rb[1000001][2];

inline void Print(int ind, int cur, int num)
{
    num -= cur;
    if (ind == 0)
    {
        return;
    }
    for (int i = 1; i >= 0; --i)
    {
        if (a[ind - 1][i] <= a[ind][cur] &&
            lb[ind - 1][i] <= num && num <= rb[ind - 1][i])
        {
            Print(ind - 1, i, num);
            break;
        }
    }
    cout << char('A' + cur);
}

int main()
{
    setup();

    cin >> n;
    for (int j = 0; j < 2; ++j)
    {
        for (int i = 1; i <= 2 * n; ++i)
        {
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= 2 * n; ++i)
    {
        for (int j = 0; j < 2; ++j)
        {
            lb[i][j] = 1e9;
            rb[i][j] = -1e9;
            for (int k = 0; k < 2; ++k)
            {
                if (a[i - 1][k] <= a[i][j])
                {
                    lb[i][j] = min(lb[i][j], lb[i - 1][k]);
                    rb[i][j] = max(rb[i][j], rb[i - 1][k]);
                }
            }
            lb[i][j] += j;
            rb[i][j] += j;
        }
    }
    for (int i = 0; i < 2; ++i)
    {
        if (lb[2 * n][i] <= n && n <= rb[2 * n][i])
        {
            Print(2 * n, i, n);
            return 0;
        }
    }
    cout << -1;
    return 0;
}

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