#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
int n,a[N],b[N];
bool dp[2005][1005][2];
void resimali(){
dp[1][0][1] = dp[1][1][0] = 1;
for(int i = 2; i <= 2*n; i++){
for(int j = 0; j <= n; j++){ /// br A-ova
if(a[i-1] <= a[i] && j >= 1){
dp[i][j][0] |= dp[i-1][j-1][0];
}
if(b[i-1] <= a[i] && j >= 1){
dp[i][j][0] |= dp[i-1][j-1][1];
}
if(a[i-1] <= b[i]){
dp[i][j][1] |= dp[i-1][j][0];
}
if(b[i-1] <= b[i]){
dp[i][j][1] |= dp[i-1][j][1];
}
}
}
if(!dp[2*n][n][0] && !dp[2*n][n][1]){
cout << -1 << endl;
return;
}
int i = 2*n,j = n,k = -1;
string ans;
a[2*n+1] = b[2*n+1] = 2000000000;
while(i){
if(dp[i][j][0] && a[i] <= (k == 0 ? a[i+1] : b[i+1])){
k = 0;
}
else{
k = 1;
}
if(k == 0){
ans += 'A';
j--;
}
else{
ans += 'B';
}
i--;
}
reverse(ans.begin(),ans.end());
cout << ans << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for(int i = 1; i <= 2*n; i++){
cin >> a[i];
}
for(int i = 1; i <= 2*n; i++){
cin >> b[i];
}
if(n <= 2000){
resimali();
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Runtime error |
5 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
6 |
Halted |
0 ms |
0 KB |
- |