Submission #1184796

#TimeUsernameProblemLanguageResultExecution timeMemory
1184796tvgkBuilding 4 (JOI20_building4)C++20
0 / 100
0 ms328 KiB
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ii pair<ll, ll>
const long mxN = 5e5 + 7, inf = 1e9 + 7;

int tt[mxN], a[2][mxN], n, p[mxN], cur[mxN];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    n *= 2;
    for (int j = 0; j <= 1; j++)
    {
        for (int i = 1; i <= n; i++)
            cin >> a[j][i];
    }

    for (int i = 1; i <= n; i++)
    {
        tt[i] = 2;
        p[i] = 1;
        if (a[0][i] > a[1][i])
        {
            swap(a[0][i], a[1][i]);
            p[i] = -1;
        }
    }

    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        cur[i] = a[0][i];

        if (a[0][i] < cur[i - 1])
        {
            cur[i] = a[1][i];
            tt[i] = 1;
            cnt += p[i];
        }
    }

    cur[n + 1] = inf;
    for (int i = n; i >= 1; i--)
    {
        cur[i] = a[1][i];

        if (a[1][i] > cur[i + 1])
        {
            cur[i] = a[0][i];
            tt[i] = 0;
            cnt -= p[i];
        }
    }

    for (int i = 1; i <= n; i++)
    {
        if (tt[i] == 2)
        {
            if (abs(cnt + p[i]) <= abs(cnt - p[i]))
            {
                cnt += p[i];
                tt[i] = 1;
            }
            else
            {
                cnt -= p[i];
                tt[i] = 0;
            }
        }

        if (a[tt[i - 1]][i - 1] > a[tt[i]][i])
        {
            cnt = 1;
            break;
        }
    }
    if (cnt)
    {
        cout << -1;
        return 0;
    }

    for (int i = 1; i <= n; i++)
    {
        tt[i] ^= (p[i] != 1);
        cout << char('A' + tt[i]);
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...