제출 #522165

#제출 시각아이디문제언어결과실행 시간메모리
522165Rainbowbunny건물 4 (JOI20_building4)C++17
100 / 100
261 ms48276 KiB
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 5; const int INF = 1e9; int n; int A[MAXN][2], l[MAXN][2], r[MAXN][2]; int ans[MAXN]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= 2 * n; i++) { cin >> A[i][0]; } for(int i = 1; i <= 2 * n; i++) { cin >> A[i][1]; } for(int i = 1; i <= 2 * n; i++) { for(int j = 0; j < 2; j++) { l[i][j] = INF; r[i][j] = -INF; for(int k = 0; k < 2; k++) { if(A[i][j] >= A[i - 1][k]) { l[i][j] = min(l[i][j], l[i - 1][k] + j); r[i][j] = max(r[i][j], r[i - 1][k] + j); } } } } int root = -1, cntb = n; for(int i = 0; i < 2; i++) { if(l[2 * n][i] <= cntb and r[2 * n][i] >= cntb) { root = i; } } if(root == -1) { cout << -1 << '\n'; } else { for(int i = 2 * n; i >= 1; i--) { for(int j = 0; j < 2; j++) { if(A[i][root] >= A[i - 1][j] and cntb - root >= l[i - 1][j] and cntb - root <= r[i - 1][j]) { ans[i] = root; cntb -= root; root = j; break; } } } for(int i = 1; i <= 2 * n; i++) { cout << char(ans[i] + 'A'); } cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...