# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211845 | 2020-03-21T14:13:38 Z | jk89 | Building 4 (JOI20_building4) | C++14 | 4 ms | 384 KB |
#include <cstdio> #include <algorithm> #include <vector> using namespace std; #define f first #define s second const int MAXN = 5e5 + 3; const int INF = 1e9 + 3; int t[MAXN][2]; pair<int, int> dp[MAXN][2]; bool ans[MAXN]; int a = 0, b = 0, akt; bool possible(int wym, int ind) { if (dp[ind][wym].f == INF) return false; if (t[ind][wym] > t[ind + 1][akt]) return false; return b - a >= dp[ind][wym].f && b - a <= dp[ind][wym].s; } int main() { int n; scanf("%d", &n); n *= 2; for (int i = 0; i < 2; i++) { for (int j = 1; j <= n; j++) scanf("%d", &t[j][i]); } for (int i = 1; i <= n; i++) { dp[i][0] = dp[i][1] = {INF, 0}; if (t[i - 1][0] <= t[i][0]) { dp[i][0] = dp[i - 1][0]; dp[i][0].f++; dp[i][0].s++; } if (t[i - 1][1] <= t[i][0]) { dp[i][0].f = min(dp[i][0].f, dp[i - 1][1].f + 1); dp[i][0].s = max(dp[i][0].s, dp[i - 1][1].s + 1); } if (t[i - 1][0] <= t[i][1]) { dp[i][1] = dp[i - 1][0]; dp[i][1].f--; dp[i][1].s--; } if (t[i - 1][1] <= t[i][1]) { dp[i][1].f = min(dp[i][1].f, dp[i - 1][1].f - 1); dp[i][1].s = max(dp[i][1].s, dp[i - 1][1].s - 1); } } if (dp[n][0].f <= 0 && dp[n][0].s >= 0) { a++; akt = 0; } else { b++; akt = 1; ans[n] = true; } for (int i = n; i > 1; i--) { if (possible(0, i - 1)) { a++; akt = 0; } else { b++; akt = 1; ans[i - 1] = true; } } for (int i = 1; i <= n; i++) printf(ans[i] ? "B" : "A"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Incorrect | 4 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Incorrect | 4 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |