Submission #1352167

#TimeUsernameProblemLanguageResultExecution timeMemory
1352167fgggBuilding 4 (JOI20_building4)C++20
0 / 100
3 ms2372 KiB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
vector<vector<ll>> g;
vector<ll> vis, p;
map<array<ll, 3>, ll> cv;
void dfs(ll u, ll c1, ll c2) {
    p.push_back(u);
    c1 += (u < g.size() / 2);
    c2 += (u >= g.size() / 2);
    if (cv.find({u, c1, c2}) != cv.end()) return;
    cv[{u, c1, c2}] = 1;
    if (c1 == g.size() / 4 && c2 == g.size() / 4) {
        for (ll i = 0; i < p.size(); i++) {
            if (p[i] < g.size() / 2) cout << 'A';
            else cout << 'B';
        }
        exit(0);
    }
    for (ll v : g[u]) {
        if (!vis[v]) {
            dfs(v, c1, c2);
        }
    }
    p.pop_back();
}
void solve() {
    ll n;
    cin >> n;
    n *= 2;
    vector<ll> a(n), b(n);
    for (ll& x : a) cin >> x;
    for (ll& x : b) cin >> x;
    g.resize(n + n);
    vis.resize(n + n);
    for (ll i = 0; i < n - 1; i++) {
        if (a[i] <= a[i + 1]) g[i].push_back(i + 1);
        if (a[i] <= b[i + 1]) g[i].push_back(i + 1 + n);
        if (b[i] <= a[i + 1]) g[i + n].push_back(i + 1);
        if (b[i] <= b[i + 1]) g[i + n].push_back(i + n + 1);
    }
    dfs(0, 0, 0);
    vis.assign(n + n, 0);
    cv.clear();
    dfs(n, 0, 0);
    cout << -1;
}
signed main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    ll t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...