제출 #646581

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
646581		boris_mihov	건물 4 (JOI20_building4)	C++17	100 / 100	244 ms	41988 KiB

building4

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <bitset>
#include <set>
#include <map>

typedef long long llong;
const int MAXN = 1000000 + 10;
const int INF  = 1e9;

int a[MAXN][2], n;
int dpA[MAXN][2];
int dpB[MAXN][2];
char ans[MAXN];

void solve()
{
    for (int i = 1 ; i <= 2*n ; ++i)
    {
        dpA[i][0] = dpB[i][0] = -INF;
        dpA[i][1] = dpB[i][1] = -INF;
        for (int last = 0 ; last <= 1 ; ++last)
        {
            if (a[i][0] >= a[i - 1][last])
            {
                dpA[i][0] = std::max(dpA[i][0], dpA[i - 1][last] + 1);
                dpB[i][0] = std::max(dpB[i][0], dpB[i - 1][last]);
            }

            if (a[i][1] >= a[i - 1][last])
            {
                dpA[i][1] = std::max(dpA[i][1], dpA[i - 1][last]);
                dpB[i][1] = std::max(dpB[i][1], dpB[i - 1][last] + 1);
            }
        }
    }

    if (std::max(dpA[2*n][0], dpA[2*n][1]) < n || std::max(dpB[2*n][0], dpB[2*n][1]) < n)
    {
        std::cout << -1 << '\n';
        return;
    }

    a[2*n + 1][0] = INF;
    int cntA = n, cntB = n;
    int idx = 2*n, last = 0;

    while (cntA >= 1 || cntB >= 1)
    {
        if (a[idx][0] <= a[idx + 1][last] && dpA[idx][0] >= cntA && dpB[idx][0] >= cntB)
        {
            ans[idx - 1] = 'A';
            last = 0;
            cntA--;
            idx--;
            continue;
        }

        if (a[idx][1] <= a[idx + 1][last] && dpA[idx][1] >= cntA && dpB[idx][1] >= cntB)
        {
            ans[idx - 1] = 'B';
            last = 1;
            cntB--;
            idx--;
            continue;
        }
    
        std::cout << -1 << '\n';
        return;
    }

    ans[2*n] = '\0';
    std::cout << ans << '\n';
}

void read()
{
    std::cin >> n;
    for (int i = 1 ; i <= 2*n ; ++i) std::cin >> a[i][0];
    for (int i = 1 ; i <= 2*n ; ++i) std::cin >> a[i][1]; 
}

void fastIO()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIO();
    read();
    solve();

    return 0;
}

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