Submission #212321

#TimeUsernameProblemLanguageResultExecution timeMemory
2123214fectaBuilding 4 (JOI20_building4)C++14
0 / 100
10 ms8320 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define ll long long #define ld long double #define pii pair<int, int> #define f first #define s second #define readl(_s) getline(cin, (_s)); #define boost() cin.tie(0); cin.sync_with_stdio(0) const int MN = 1000005; int n, a[MN][2], mn[MN][2], mx[MN][2], valid[MN][2]; char ans[MN]; int main() { boost(); memset(mn, 0x3f, sizeof(mn)); cin >> n; for (int j = 0; j < 2; j++) for (int i = 1; i <= 2 * n; i++) cin >> a[i][j]; valid[1][0] = 1; valid[1][1] = 1; mn[1][0] = mx[1][0] = 0; mn[1][1] = mx[1][1] = 1; for (int i = 2; i <= 2 * n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { if (a[i][j] < a[i - 1][k]) continue; valid[i][j] = 1; mn[i][j] = min(mn[i][j], mn[i - 1][k] + j); mx[i][j] = max(mx[i][j], mx[i - 1][k] + j); } } } if (valid[2 * n][0] && mn[2 * n][0] <= n && mx[2 * n][0] >= n) { int j = 0, rem = n; for (int i = 2 * n; i > 0; i--) { ans[i] = 'A' + j; if (i == 1) break; rem -= j; if (valid[i - 1][0] && mn[i - 1][0] <= rem && mx[i - 1][0] >= rem) j = 0; if (valid[i - 1][1] && mn[i - 1][1] <= rem && mx[i - 1][1] >= rem) j = 1; } } else if (valid[2 * n][1] && mn[2 * n][1] <= n && mx[2 * n][1] >= n) { int j = 1, rem = n; for (int i = 2 * n; i > 0; i--) { ans[i] = 'A' + j; if (i == 1) break; rem -= j; if (valid[i - 1][0] && mn[i - 1][0] <= rem && mx[i - 1][0] >= rem) j = 0; if (valid[i - 1][1] && mn[i - 1][1] <= rem && mx[i - 1][1] >= rem) j = 1; } } else return 0 * printf("-1\n"); for (int i = 1; i <= 2 * n; i++) printf("%c", ans[i]); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...