Submission #427492

#	Time	Username	Problem	Language	Result	Execution time	Memory
427492		blue	Building 4 (JOI20_building4)	C++17	100 / 100	1484 ms	45236 KiB

building4

#include <iostream>
using namespace std;

/*
Let us sort all the 4N coloring plans together, first by height then by building index.

Out of this sequence, we have to choose 2N elements such that:
    No two coloring plans for a single building are chosen.

*/

int main()
{
    int N;
    cin >> N;

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

    A[0] = B[0] = 0;
    int lo[2*N + 1][2], hi[2*N + 1][2]; //lower & upper limits on number of A buildings.

    lo[0][0] = hi[0][0] = 0;
    lo[0][1] = hi[0][1] = 0;

    for(int i = 1; i <= 2*N; i++)
    {
        lo[i][0] = lo[i][1] = 1e9;
        hi[i][0] = hi[i][1] = -1e9;

        if(A[i-1] <= A[i])
        {
            hi[i][0] = max(hi[i][0], hi[i-1][0] + 1);
            lo[i][0] = min(lo[i][0], lo[i-1][0] + 1);
        }

        if(B[i-1] <= A[i])
        {
            hi[i][0] = max(hi[i][0], hi[i-1][1] + 1);
            lo[i][0] = min(lo[i][0], lo[i-1][1] + 1);
        }

        if(A[i-1] <= B[i])
        {
            hi[i][1] = max(hi[i][1], hi[i-1][0]);
            lo[i][1] = min(lo[i][1], lo[i-1][0]);
        }

        if(B[i-1] <= B[i])
        {
            hi[i][1] = max(hi[i][1], hi[i-1][1]);
            lo[i][1] = min(lo[i][1], lo[i-1][1]);
        }

        // cerr << "i = " << i << '\n';
        // cerr << lo[i][0] << ' ' << hi[i][0] << " | " << lo[i][1] << ' ' << hi[i][1] << '\n';
    }

    if(!(lo[2*N][0] <= N && N <= hi[2*N][0]) && !(lo[2*N][1] <= N && N <= hi[2*N][1]))
    {
        cout << "-1\n";
        return 0;
    }

    string res(2*N, '.');

    int i = 2*N;
    int lb = (lo[i][1] <= N && N <= hi[i][1]);
    int buildA = N;

    for(int i = 2*N; i >= 1; i--)
    {
        if(lb == 0)
        {
            res[i-1] = 'A';
            buildA--;
        }
        else res[i-1] = 'B';

        if(lb == 0)
        {
            if(A[i-1] <= A[i] && lo[i-1][0] <= buildA && buildA <= hi[i-1][0])
                lb = 0;
            else
                lb = 1;
        }
        else
        {
            if(A[i-1] <= B[i] && lo[i-1][0] <= buildA && buildA <= hi[i-1][0])
                lb = 0;
            else
                lb = 1;
        }
    }

    cout << res << '\n';
}

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