이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vt vector
#define pb push_back
#define sz(x) int((x).size())
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vt<int> A(2 * N + 1), B(2 * N + 1);
for(int i = 1; i <= 2 * N; i++) cin >> A[i];
for(int i = 1; i <= 2 * N; i++) cin >> B[i];
vt<vt<vt<bool>>> dp(2 * N + 1, vt<vt<bool>>(N + 1, vt<bool>(2)));
dp[0][0] = {true, true};
for(int i = 1; i <= 2 * N; i++)
{
int curA = A[i], curB = B[i];
int prevA = A[i - 1], prevB = B[i - 1];
for(int j = 0; j <= N; j++)
{
if(j > 0) dp[i][j][0] = (curA >= prevA && dp[i - 1][j - 1][0]) || (curA >= prevB && dp[i - 1][j - 1][1]);
dp[i][j][1] = (curB >= prevA && dp[i - 1][j][0]) || (curB >= prevB && dp[i - 1][j][1]);
}
}
int curIdx = 0;
while(curIdx < 2 && !dp[2 * N][N][curIdx]) curIdx++;
if(curIdx >= 2)
{
cout << -1 << "\n";
return 0;
}
string ans(2 * N, '?');
for(int i = 2 * N, j = N; i > 0; i--)
{
assert(dp[i][j][curIdx]);
ans[i - 1] = curIdx == 1 ? 'B' : 'A';
j -= curIdx == 0;
if(dp[i - 1][j][0]) curIdx = 0;
else if(dp[i - 1][j][1]) curIdx = 1;
else assert(false);
}
assert(find(ans.begin(), ans.end(), '?') == ans.end());
cout << ans << "\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |