Submission #224741

#TimeUsernameProblemLanguageResultExecution timeMemory
224741Minnakhmetov건물 4 (JOI20_building4)C++14
100 / 100
356 ms44268 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(aaa) aaa.begin(), aaa.end() const int N = 1e6 + 5; pair<int, int> dp[N][2]; int a[N][2]; int n; pair<int, int> mrg(pair<int, int> a, pair<int, int> b) { if (a.first > a.second) return b; if (b.first > b.second) return a; return {min(a.first, b.first), max(a.second, b.second)}; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; for (int j = 0; j < 2; j++) { for (int i = 0; i < n + n; i++) { cin >> a[i][j]; } } for (int i = 0; i <= n + n; i++) { for (int j = 0; j < 2; j++) { dp[i][j] = {1, 0}; } } dp[1][0] = {0, 0}; dp[1][1] = {1, 1}; for (int i = 1; i < n + n; i++) { for (int j = 0; j < 2; j++) { for (int k = 0; k < 2; k++) { if (a[i - 1][j] <= a[i][k]) { dp[i + 1][k] = mrg(dp[i + 1][k], dp[i][j]); } } } dp[i + 1][1].first++; dp[i + 1][1].second++; } int x = n + n, y = -1, z = n; for (int i = 0; i < 2; i++) { if (dp[n + n][i].first <= n && n <= dp[n + n][i].second) { y = i; break; } } if (y == -1) { cout << "-1"; } else { string ans; while (true) { ans.push_back({y ? 'B' : 'A'}); if (x == 1) break; z -= y; x--; for (int i = 0; i < 2; i++) { if (a[x - 1][i] <= a[x][y] && dp[x][i].first <= z && z <= dp[x][i].second) { y = i; break; } } } reverse(all(ans)); cout << ans << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...