제출 #1032560

#제출 시각아이디문제언어결과실행 시간메모리
1032560juicy건물 4 (JOI20_building4)C++17
0 / 100
1 ms348 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif array<int, 2> operator + (const array<int, 2> &a, int x) { return {a[0] + x, a[1] + x}; } array<int, 2> mrg(const array<int, 2> &lt, const array<int, 2> &rt) { return {min(lt[0], lt[1]), max(rt[0], rt[1])}; } bool inside(const array<int, 2> &a, int i) { return a[0] <= i && i <= a[1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); const int inf = 1e9; int N; cin >> N; vector<int> a(2 * N), b(2 * N); for (int &x : a) { cin >> x; } for (int &x : b) { cin >> x; } vector<array<array<int, 2>, 2>> dp(2 * N); for (int i = 1; i < 2 * N; ++i) { for (int j = 0; j < 2; ++j) { dp[i][j] = {inf, -inf}; } } dp[0][0] = {0, 0}; dp[0][1] = {1, 1}; for (int i = 1; i < 2 * N; ++i) { if (a[i - 1] <= a[i]) { dp[i][0] = mrg(dp[i][0], dp[i - 1][0]); } if (b[i - 1] <= a[i]) { dp[i][0] = mrg(dp[i][0], dp[i - 1][1]); } if (a[i - 1] <= b[i]) { dp[i][1] = mrg(dp[i][1], dp[i - 1][0] + 1); } if (b[i - 1] <= b[i]) { dp[i][1] = mrg(dp[i][1], dp[i - 1][1] + 1); } } int taken = N, lst = inf; string res; for (int i = 2 * N - 1; i >= 0; --i) { if (inside(dp[i][0], taken) && a[i] <= lst) { res += 'A'; lst = a[i]; } else if (inside(dp[i][1], taken) && b[i] <= lst) { res += 'B'; taken -= 1; lst = b[i]; } else { cout << -1; exit(0); } } reverse(res.begin(), res.end()); cout << res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...