Submission #422070

#	Time	Username	Problem	Language	Result	Execution time	Memory
422070		alextodoran	Building 4 (JOI20_building4)	C++17	100 / 100	294 ms	45368 KiB

building4

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 1000000;

const int A = 0;
const int B = 1;

int n;

int a[N_MAX + 2];
int b[N_MAX + 2];

int L[N_MAX + 2][2];
int R[N_MAX + 2][2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    n *= 2;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        cin >> b[i];
    for(int i = 1; i <= n; i++)
    {
        L[i][A] = L[i][B] = INT_MAX / 2;
        R[i][A] = R[i][B] = INT_MIN / 2;
    }
    L[1][A] = 1;
    R[1][A] = 1;
    L[1][B] = 0;
    R[1][B] = 0;
    for(int i = 1; i < n; i++)
    {
        if(a[i] <= a[i + 1])
        {
            L[i + 1][A] = min(L[i + 1][A], L[i][A] + 1);
            R[i + 1][A] = max(R[i + 1][A], R[i][A] + 1);
        }
        if(a[i] <= b[i + 1])
        {
            L[i + 1][B] = min(L[i + 1][B], L[i][A]);
            R[i + 1][B] = max(R[i + 1][B], R[i][A]);
        }
        if(b[i] <= a[i + 1])
        {
            L[i + 1][A] = min(L[i + 1][A], L[i][B] + 1);
            R[i + 1][A] = max(R[i + 1][A], R[i][B] + 1);
        }
        if(b[i] <= b[i + 1])
        {
            L[i + 1][B] = min(L[i + 1][B], L[i][B]);
            R[i + 1][B] = max(R[i + 1][B], R[i][B]);
        }
    }
    bool okA = (L[n][A] <= n / 2 && n / 2 <= R[n][A]);
    bool okB = (L[n][B] <= n / 2 && n / 2 <= R[n][B]);
    if(okA == false && okB == false)
    {
        cout << "-1\n";
        return 0;
    }
    int pos = n;
    int cnt = n / 2;
    int last = (okA == true ? A : B);
    string sol;
    while(pos >= 2)
    {
        if(last == A)
            sol += 'A';
        else
            sol += 'B';
        if(last == A)
        {
            if(a[pos - 1] <= a[pos] && L[pos - 1][A] + 1 <= cnt && cnt <= R[pos - 1][A] + 1)
                last = A;
            else if(b[pos - 1] <= a[pos] && L[pos - 1][B] + 1 <= cnt && cnt <= R[pos - 1][B] + 1)
                last = B;
            cnt--;
        }
        else
        {
            if(a[pos - 1] <= b[pos] && L[pos - 1][A] <= cnt && cnt <= R[pos - 1][A])
                last = A;
            else if(b[pos - 1] <= b[pos] && L[pos - 1][B] <= cnt && cnt <= R[pos - 1][B])
                last = B;
        }
        pos--;
    }
    if(last == A)
        sol += 'A';
    else
        sol += 'B';
    reverse(sol.begin(), sol.end());
    cout << sol << "\n";
    return 0;
}

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