제출 #212225

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

building4

#include <algorithm>
#include <iostream>
#include <utility>
#include <string>
#define F first
#define S second

using namespace std;

int _1[1000 * 1000 + 5], _2[1000 * 1000 + 5];
pair <int, int> dyn[1000 * 1000 + 5][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string wyn;
    int n;

    cin >> n;

    for(int i = 1; i < (n << 1) + 1; ++i)
    {
        cin >> _1[i];
    }
    for(int i = 1; i < (n << 1) + 1; ++i)
    {
        cin >> _2[i];
    }

    dyn[1][0] = {1, 1};
    dyn[1][1] = {0, 0};
    for(int i = 2; i < (n << 1) + 1; ++i)
    {
        dyn[i][0] = {1000 * 1000 * 1000 + 5, - (1000 * 1000 * 1000 + 5)};
        if(_1[i - 1] <= _1[i])
        {
            dyn[i][0] = {min(dyn[i][0].F, dyn[i - 1][0].F + 1), max(dyn[i][0].S, dyn[i - 1][0].S + 1)};
        }
        if(_2[i - 1] <= _1[i])
        {
            dyn[i][0] = {min(dyn[i][0].F, dyn[i - 1][1].F + 1), max(dyn[i][0].S, dyn[i - 1][1].S + 1)};
        }

        dyn[i][1] = {1000 * 1000 * 1000 + 5, - (1000 * 1000 * 1000 + 5)};
        if(_1[i - 1] <= _2[i])
        {
            dyn[i][1] = {min(dyn[i][1].F, dyn[i - 1][0].F), max(dyn[i][1].S, dyn[i - 1][0].S)};
        }
        if(_2[i - 1] <= _2[i])
        {
            dyn[i][1] = {min(dyn[i][1].F, dyn[i - 1][1].F), max(dyn[i][1].S, dyn[i - 1][1].S)};
        }
    }

    if((dyn[(n << 1)][0].F > n || n > dyn[(n << 1)][0].S) && (dyn[(n << 1)][1].F > n || n > dyn[(n << 1)][1].S))
    {
        cout << "-1\n";
        return 0;
    }

    for(int i = (n << 1), ile = n; i > 0; --i)
    {
        if(dyn[i][0].F <= ile && ile <= dyn[i][0].S && (wyn.empty() || _1[i] <= _1[i + 1] * (wyn.back() == 'A') + _2[i + 1] * (wyn.back() == 'B')))
        {
            wyn += "A";
            ile--;
        }
        else
        {
            wyn += "B";
        }
    }
    reverse(wyn.begin(), wyn.end());

    cout << wyn << "\n";

    return 0;
}

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