제출 #1173270

#제출 시각아이디문제언어결과실행 시간메모리
1173270chikien2009건물 4 (JOI20_building4)C++20
0 / 100
1 ms580 KiB
#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)
{
    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 - i);
            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] + j);
                    rb[i][j] = max(rb[i][j], rb[i - 1][k] + 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;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...