Submission #770858

#TimeUsernameProblemLanguageResultExecution timeMemory
770858PurpleCrayonBuilding 4 (JOI20_building4)C++17
11 / 100
42 ms13376 KiB
#include <bits/stdc++.h> using namespace std; #define sz(v) int(v.size()) #define ar array typedef long long ll; const int N = 5e5+10, MOD = 1e9+7; // some are switchable, but only if the next thing switches (or if it's the tail end) // you can just start from the end and swithc stuff while you need to int n, a[N][2]; ar<int, 2> dp[N][2]; void add_self(ar<int, 2>& x, ar<int, 2> y, int delta) { y[0] += delta; y[1] += delta; x[0] = min(x[0], y[0]); x[1] = max(x[1], y[1]); } void solve() { cin >> n; for (int j = 0; j < 2; j++) { for (int i = 0; i < 2 * n; i++) cin >> a[i][j]; } dp[0][0] = {-1, -1}; dp[0][1] = {1, 1}; for (int i = 1; i < 2 * n; i++) { // 1 if you take b, -1 if you take a dp[i][0] = {MOD, -MOD}; dp[i][1] = {MOD, -MOD}; for (int x = 0; x < 2; x++) { for (int y = 0; y < 2; y++) { if (a[i-1][x] <= a[i][y]) { add_self(dp[i][y], dp[i-1][x], (y ? +1 : -1)); } } } } int last = -1; for (int x : {0, 1}) if (dp[2*n-1][x][0] <= 0 && 0 <= dp[2*n-1][x][1]) last = x; if (last == -1) { cout << -1 << '\n'; return; } string ans(2 * n, '?'); int start = 0; for (int i = 2*n-1; i >= 0; i--) { ans[i] = last + 'A'; if (!i) break; start -= (last ? +1 : -1); for (int x : {0, 1}) { if (a[i-1][x] <= a[i][last] && dp[i-1][x][0] <= start && start <= dp[i-1][x][1]) { last = x; break; } } } cout << ans << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T = 1; // cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...