Submission #211624

#TimeUsernameProblemLanguageResultExecution timeMemory
211624kuroniBuilding 4 (JOI20_building4)C++17
100 / 100
322 ms28140 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; const int N = 500005; int n, a[2 * N][2]; bool chk[2 * N][2]; string ans; pair<int, int> r[2 * N][2]; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for (int it = 0; it < 2; it++) { for (int i = 1; i <= 2 * n; i++) { cin >> a[i][it]; } } chk[0][0] = true; for (int i = 1; i <= 2 * n; i++) { for (int it = 0; it < 2; it++) { for (int j = 0; j < 2; j++) { if (chk[i - 1][j] && a[i - 1][j] <= a[i][it]) { if (!chk[i][it]) { chk[i][it] = true; r[i][it] = {r[i - 1][j].fi + it, r[i - 1][j].se + it}; } else { r[i][it].fi = min(r[i][it].fi, r[i - 1][j].fi + it); r[i][it].se = max(r[i][it].se, r[i - 1][j].se + it); } } } } } for (int it = 0; it < 2; it++) { if (chk[2 * n][it] && r[2 * n][it].fi <= n && n <= r[2 * n][it].se) { for (int i = 2 * n, cur = n; i >= 1; i--) { ans.push_back('A' + it); cur -= it; for (int j = 0; j < 2; j++) { if (chk[i - 1][j] && a[i - 1][j] <= a[i][it] && r[i - 1][j].fi <= cur && cur <= r[i - 1][j].se) { it = j; break; } } } reverse(ans.begin(), ans.end()); return cout << ans, 0; } } cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...