제출 #528880

#제출 시각아이디문제언어결과실행 시간메모리
528880ajpiano건물 4 (JOI20_building4)C++17
11 / 100
609 ms524292 KiB
#include <bits/stdc++.h> using namespace std; #define f first #define s second typedef long long ll; typedef pair<int,int> pi; const int large = 1e5+5; bitset<large/2> dp[large][2]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<int> a(2*n), b(2*n); for(int i = 0; i < 2*n; i++) cin >> a[i]; for(int i = 0; i < 2*n; i++) cin >> b[i]; dp[0][0][0] = 1; dp[0][1][1] = 1; for(int i = 1; i < 2*n; i++){ if(a[i-1] <= a[i]) dp[i][0] = dp[i-1][0]; if(b[i-1] <= b[i]) dp[i][1] = dp[i-1][1]<<1; if(b[i-1] <= a[i]) dp[i][0] |= dp[i-1][1]; if(a[i-1] <= b[i]) dp[i][1] |= dp[i-1][0]<<1; } if(dp[2*n-1][0][n]|dp[2*n-1][1][n]){ string ans = ""; bool cur = 0; int num = n; if(dp[2*n-1][0][n]){ ans += 'A'; num = n; if(a[2*n-1] >= a[2*n-2] && dp[2*n-2][0][num]) cur = 0; else cur = 1; }else{ ans += 'B'; num = n-1; if(b[2*n-1] >= b[2*n-2] && dp[2*n-2][1][num]) cur = 1; else cur = 0; } for(int i = 2*n-2; i > 0; i--){ if(cur == 0){ ans += 'A'; num = num; if(a[i] >= a[i-1] && dp[i-1][0][num]) cur = 0; else cur = 1; }else{ ans += 'B'; num = num-1; if(b[i] >= b[i-1] && dp[i-1][1][num]) cur = 1; else cur = 0; } } if(cur) ans += 'B'; else ans += 'A'; reverse(ans.begin(), ans.end()); cout << ans << "\n"; }else cout << "-1\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...