Submission #683855

#TimeUsernameProblemLanguageResultExecution timeMemory
683855stevancvBuilding 4 (JOI20_building4)C++14
0 / 100
28 ms436 KiB
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 5e5 + 2;
bool can[2][2 * N], prv[2][2 * N];
int a[2][2 * N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for (int j = 0; j < 2; j++) for (int i = 1; i <= 2 * n; i++) cin >> a[j][i];
    a[0][2 * n + 1] = 1e9;
    can[0][1] = can[1][1] = 1;
    for (int i = 2; i <= 2 * n + 1; i++) {
        bool manji = 0, veci = 1;
        if (a[0][i - 1] > a[1][i - 1]) swap(manji, veci);
        for (int j = 0; j < 2; j++) {
            if (a[veci][i - 1] <= a[j][i] && can[veci][i - 1]) {
                can[j][i] = 1;
                prv[j][i] = veci;
            }
            else if (a[manji][i - 1] <= a[j][i] && can[manji][i - 1]) {
                can[j][i] = 1;
                prv[j][i] = manji;
            }
        }
    }
    if (can[0][2 * n + 1] == 0) {
        cout << -1 << en;
        return 0;
    }
    int i = 2 * n + 1, j = 0;
    vector<int> ans;
    int diff = 0;
    while (1) {
        j = prv[j][i];
        i -= 1;
        if (i == 0) break;
        diff += 2 * j - 1;
        ans.push_back(j);
    }
    ans.push_back(-1);
    reverse(ans.begin(), ans.end());
    for (int z = 0; z < 3000; z++) {
        for (int i = 2 * n; i >= 1; i--) {
            if (ans[i] == 0 && diff < 0 && can[1][i] == 1) {
                bool moze = 1;
                if (i >= 2 && a[ans[i - 1]][i - 1] > a[1][i]) moze = 0;
                if (i < 2 * n && a[1][i] > a[ans[i + 1]][i + 1]) moze = 0;
                if (moze) {
                    diff += 2;
                    ans[i] ^= 1;
                }
            }
            else if (ans[i] == 1 && diff > 0 && can[0][i] == 1) {
                bool moze = 1;
                if (i >= 2 && a[ans[i - 1]][i - 1] > a[0][i]) moze = 0;
                if (i < 2 * n && a[0][i] > a[ans[i + 1]][i + 1]) moze = 0;
                if (moze) {
                    diff -= 2;
                    ans[i] ^= 1;
                }
            }
        }
    }
    if (diff != 0) {
        cout << -1 << en;
        return 0;
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (ans[i] == 0) cout << 'A';
        if (ans[i] == 1) cout << 'B';
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...