Submission #683982

#TimeUsernameProblemLanguageResultExecution timeMemory
683982stevancvBuilding 4 (JOI20_building4)C++14
100 / 100
261 ms48068 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 = 1e6 + 2; const int inf = 1e9; int a[N][2], dpl[N][2], dpr[N][2], ans[N]; void Resi(int i, int j, int k) { if (i == 0) return; ans[i] = j; k -= j; if (dpl[i - 1][0] <= k && k <= dpr[i - 1][0] && a[i - 1][0] <= a[i][j]) Resi(i - 1, 0, k); else if (dpl[i - 1][1] <= k && k <= dpr[i - 1][1] && a[i - 1][1] <= a[i][j]) Resi(i - 1, 1, k); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; n = 2 * n; for (int i = 1; i <= n; i++) cin >> a[i][0]; for (int i = 1; i <= n; i++) cin >> a[i][1]; for (int i = 1; i <= n; i++) for (int j = 0; j < 2; j++) dpl[i][j] = inf, dpr[i][j] = -inf; dpl[1][0] = dpr[1][0] = 0; dpl[1][1] = dpr[1][1] = 1; for (int i = 2; i <= n; i++) { for (int j = 0; j < 2; j++) { for (int pj = 0; pj < 2; pj++) { if (a[i - 1][pj] > a[i][j]) continue; smin(dpl[i][j], dpl[i - 1][pj] + j); smax(dpr[i][j], dpr[i - 1][pj] + j); } } } if (dpl[n][0] <= n / 2 && n / 2 <= dpr[n][0]) Resi(n, 0, n / 2); else if (dpl[n][1] <= n / 2 && n / 2 <= dpr[n][1]) Resi(n, 1, n / 2); else {cout << -1; return 0;} for (int i = 1; i <= n; i++) { if (ans[i] == 0) cout << 'A'; if (ans[i] == 1) cout << 'B'; } cout << en; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...