Submission #212741

#	Time	Username	Problem	Language	Result	Execution time	Memory
212741		Alexa2001	Building 4 (JOI20_building4)	C++17	100 / 100	362 ms	64376 KiB

building4

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1e6 + 5;

int A[Nmax], B[Nmax], s[Nmax][2], f[Nmax][2];
bool ok[Nmax][2];

char ans[Nmax];
int n;


void min_to(int &x, int y)
{
    if(x > y) x = y;
}
void max_to(int &x, int y)
{
    if(x < y) x = y;
}

void solve(int i, int y, int z)
{
    if(!z) ans[i] = 'A', y--;
        else ans[i] = 'B';

    if(i == 1)
    {
        cout << (ans+1) << '\n';
        return;
    }

    if(!z)
    {
        if(A[i] >= A[i-1] && ok[i-1][0] && s[i-1][0] <= y && y <= f[i-1][0])
            solve(i-1, y, 0);
        else if(A[i] >= B[i-1] && ok[i-1][1] && s[i-1][1] <= y && y <= f[i-1][1])
            solve(i-1, y, 1);
        else assert(0);

        return;
    }
    else
    {
        if(B[i] >= A[i-1] && ok[i-1][0] && s[i-1][0] <= y && y <= f[i-1][0])
            solve(i-1, y, 0);
        else if(B[i] >= B[i-1] && ok[i-1][1] && s[i-1][1] <= y && y <= f[i-1][1])
            solve(i-1, y, 1);
        else assert(0);

        return;
    }
}

int main()
{
   // freopen("input", "r", stdin);
    cin.sync_with_stdio(false); cin.tie(0);

    int i;
    cin >> n;
    for(i=1; i<=2*n; ++i) cin >> A[i];
    for(i=1; i<=2*n; ++i) cin >> B[i];

    s[1][0] = f[1][0] = 1;
    s[1][1] = f[1][1] = 0;

    ok[1][0] = ok[1][1] = 1;

    for(i=2; i<=2*n; ++i)
    {
        s[i][0] = s[i][1] = 2*n+1;
        f[i][0] = f[i][1] = -1;

        if(A[i] >= A[i-1] && ok[i-1][0])
            min_to(s[i][0], s[i-1][0] + 1), max_to(f[i][0], f[i-1][0] + 1);

        if(A[i] >= B[i-1] && ok[i-1][1])
            min_to(s[i][0], s[i-1][1] + 1), max_to(f[i][0], f[i-1][1] + 1);

        if(B[i] >= A[i-1] && ok[i-1][0])
            min_to(s[i][1], s[i-1][0]), max_to(f[i][1], f[i-1][0]);

        if(B[i] >= B[i-1] && ok[i-1][1])
            min_to(s[i][1], s[i-1][1]), max_to(f[i][1], f[i-1][1]);


        ok[i][0] = (s[i][0] <= f[i][0]);
        ok[i][1] = (s[i][1] <= f[i][1]);
    }

    if(s[2*n][0] <= n && n <= f[2*n][0])
        solve(2*n, n, 0);
    else if(s[2*n][1] <= n && n <= f[2*n][1])
        solve(2*n, n, 1);
    else cout << "-1\n";

    return 0;
}

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