Submission #683835

#	Time	Username	Problem	Language	Result	Execution time	Memory
683835		stevancv	Building 4 (JOI20_building4)	C++14	0 / 100	2 ms	468 KiB

building4

#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 i = 1; i <= 2 * n; i++) if (ans[i] == 1) swap(a[0][i], a[1][i]);
    for (int i = 1; i <= 2 * n; 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;
}

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