oj.uz

Submission #219868

# Submission time Handle Problem Language Result Execution time Memory
219868 2020-04-06T15:21:07 Z joseacaz Building 4 (JOI20_building4) C++17
0 / 100
 5 ms 384 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 89.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Incorrect 4 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -