제출 #596828

#제출 시각아이디문제언어결과실행 시간메모리
596828czhang2718건물 4 (JOI20_building4)C++17
100 / 100
248 ms27188 KiB
#include "bits/stdc++.h" using namespace std; const int N=1e6; int n; int a[N], b[N]; int dp[N][2][2]; int main(){ cin.tie(0)->sync_with_stdio(0); cin >> n; for(int i=0; i<2*n; i++){ cin >> a[i]; } for(int i=0; i<2*n; i++){ cin >> b[i]; } // dp[i][A/B][min/max] dp[0][0][0]=dp[0][0][1]=1; dp[0][1][0]=dp[0][1][1]=0; for(int i=1; i<2*n; i++){ dp[i][0][0]=dp[i][1][0]=1e9; dp[i][0][1]=dp[i][1][1]=-1e9; dp[i][0][0]=min(a[i-1]<=a[i]?dp[i-1][0][0]+1:1e9, b[i-1]<=a[i]?dp[i-1][1][0]+1:1e9); dp[i][0][1]=max(a[i-1]<=a[i]?dp[i-1][0][1]+1:-1e9, b[i-1]<=a[i]?dp[i-1][1][1]+1:-1e9); dp[i][1][0]=min(a[i-1]<=b[i]?dp[i-1][0][0]:1e9, b[i-1]<=b[i]?dp[i-1][1][0]:1e9); dp[i][1][1]=max(a[i-1]<=b[i]?dp[i-1][0][1]:-1e9, b[i-1]<=b[i]?dp[i-1][1][1]:-1e9); // cout << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << "\n"; } if((dp[2*n-1][0][0]<=n && dp[2*n-1][0][1]>=n) || (dp[2*n-1][1][0]<=n && dp[2*n-1][1][1]>=n)){ int k=n; string ans(" ", 2*n); // cout << ans.size() << "\n"; int lst=1e9; for(int i=2*n-1; i>=1; i--){ // cout << "k " << k << " lst " << lst << "\n"; if(a[i]<=lst && dp[i][0][0]<=k && dp[i][0][1]>=k){ ans[i]='A'; lst=a[i]; k--; } else ans[i]='B', lst=b[i]; } if(k) ans[0]='A'; else ans[0]='B'; cout << ans; } else cout << -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...