Submission #213152

#	Time	Username	Problem	Language	Result	Execution time	Memory
213152		ho94949	Building 4 (JOI20_building4)	C++17	100 / 100	1277 ms	26020 KiB

building4

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int N; cin >> N;
    vector<int> A(2*N), B(2*N);
    for(int i=0; i<2*N; ++i) cin >> A[i];
    for(int i=0; i<2*N; ++i) cin >> B[i];

    const int INF = 0x3f3f3f3f;

    vector<pair<int, int> > dpA(2*N), dpB(2*N); //# of A
    dpA[0] = make_pair(1, 1);
    dpB[0] = make_pair(0, 0);
    for(int i=0; i<2*N-1; ++i)
    {
        int mina = INF, maxa = -INF, minb = INF, maxb = -INF;
        auto [al, ar] = dpA[i]; auto[bl, br] = dpB[i];

        if(al != -1)
        {
            if(A[i] <= A[i+1])
                mina = min(mina, al+1), maxa = max(maxa, ar+1);
            if(A[i] <= B[i+1])
                minb = min(minb, al), maxb = max(maxb, ar);
        }
        if(bl != -1)
        {
            if(B[i] <= A[i+1])
                mina = min(mina, bl+1), maxa = max(maxa, br+1);
            if(B[i] <= B[i+1])
                minb = min(minb, bl), maxb = max(maxb, br);
        }
        if(mina > maxa) mina = maxa = -1;
        if(minb > maxb) minb = maxb = -1;
        dpA[i+1] = make_pair(mina, maxa);
        dpB[i+1] = make_pair(minb, maxb);
    }

    bool a; int b = 2*N-1, c = N;
    if(dpA[2*N-1].first <= N && N <= dpA[2*N-1].second)
        a = true;
    else if(dpB[2*N-1].first <= N && N <= dpB[2*N-1].second)
        a = false;
    else
    {
        puts("-1"); return 0;
    }

    string s;
    if(a) s = "A", c=N-1; else s = "B";

    while(b)
    {
        if(a)
        {
            if(A[b] >= A[b-1] && dpA[b-1].first != -1 && dpA[b-1].first <= c && c <= dpA[b-1].second)
            {
                s += "A";
                a = true; b = b-1; c = c-1;
            }
            else
            {
                s += "B";
                a = false; b = b-1; c = c;                
            }
        }
        else
        {
            if(B[b] >= A[b-1] && dpA[b-1].first != -1 && dpA[b-1].first <= c && c <= dpA[b-1].second)
            {
                s += "A";
                a = true; b = b-1; c = c-1;
            }
            else
            {
                s += "B";
                a = false; b = b-1; c=c;
            }
        }
    }
    reverse(s.begin(), s.end());
    puts(s.c_str());
}

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