Submission #219868

#	Time	Username	Problem	Language	Result	Execution time	Memory
219868		joseacaz	Building 4 (JOI20_building4)	C++17	0 / 100	5 ms	384 KiB

building4

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int MAXN = 5e5 + 5, INF = (1 << 30);
int N, a[2*MAXN], b[2*MAXN], maxim[2*MAXN][2], minim[2*MAXN][2];

int main ()
{
	ios_base::sync_with_stdio ( 0 ); cin.tie ( 0 );
	cin >> N;
	for ( int i = 1; i <= 2*N; i++ )
		cin >> a[i];
	for ( int i = 1; i <= 2*N; i++ )
		cin >> b[i];

    maxim[2*N][0] = 1;
    minim[2*N][0] = 1;
    for(int i = 2*N - 1; i >= 1; i--)
    {
        if(a[i + 1] > a[i])
            maxim[i][0] = max(maxim[i][0], maxim[i + 1][0]);
        if(b[i + 1] > a[i])
            maxim[i][0] = max(maxim[i][0], maxim[i + 1][1]);
        ++maxim[i][0];

        minim[i][0] = INF;
        if(a[i + 1] > a[i])
            minim[i][0] = min(minim[i][0], minim[i + 1][0]);
        if(b[i + 1] > a[i])
            minim[i][0] = min(minim[i][0], minim[i + 1][1]);
        ++minim[i][0];

        if(a[i + 1] > b[i])
            maxim[i][1] = max(maxim[i][0], maxim[i + 1][0]);
        if(b[i + 1] > b[i])
            maxim[i][1] = max(maxim[i][0], maxim[i + 1][1]);

        minim[i][1] = INF;
        if(a[i + 1] > b[i])
            minim[i][1] = min(minim[i][1], minim[i + 1][0]);
        if(b[i + 1] > b[i])
            minim[i][1] = min(minim[i][1], minim[i + 1][1]);
    }
    
    int curr;
    if(minim[1][0] <= N && N <= maxim[1][0])
        curr = 0;
    else if(minim[1][1] <= N && N <= maxim[1][1])
        curr = 1;
    else
    {
        cout << "-1\n";
        return 0;
    }

    int left = N;
    for(int i = 1; i <= 2*N; i++)
    {
        if(curr == 0)
        {
            left--;
            cout << "A";
            if(a[i + 1] > a[i] && minim[i + 1][0] <= left && left <= maxim[i + 1][0])
                curr = 0;
            else
                curr = 1;
        }
        else
        {
            cout << "B";
            if(a[i + 1] > b[i] && minim[i + 1][0] <= left && left <= maxim[i + 1][0])
                curr = 0;
            else
                curr = 1;
        }
    }
    cout << "\n";
	return 0;
}

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