이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
namespace
{
} // namespace
void solve()
{
int n;
cin >> n;
vector<int> a(2 * n), b(2 * n);
for (int &x : a)
cin >> x;
for (int &x : b)
cin >> x;
vector dp(2 * n, vector<array<int, 2>>(2, {-1, -1}));
dp[0][0] = {1, 1};
dp[0][1] = {0, 0};
for (int i = 1; i < 2 * n; i++)
{
{
int lo = 2 * n + 1, hi = -1;
if (dp[i - 1][0][0] != -1 && a[i] > a[i - 1])
{
lo = min(lo, dp[i - 1][0][0] + 1);
hi = max(hi, dp[i - 1][0][1] + 1);
}
if (dp[i - 1][1][0] != -1 && a[i] > b[i - 1])
{
lo = min(lo, dp[i - 1][1][0] + 1);
hi = max(hi, dp[i - 1][1][1] + 1);
}
if (lo <= hi)
dp[i][0] = {lo, hi};
}
{
int lo = 2 * n + 1, hi = -1;
if (dp[i - 1][0][0] != -1 && b[i] > a[i - 1])
{
lo = min(lo, dp[i - 1][0][0]);
hi = max(hi, dp[i - 1][0][1]);
}
if (dp[i - 1][1][0] != -1 && b[i] > b[i - 1])
{
lo = min(lo, dp[i - 1][1][0]);
hi = max(hi, dp[i - 1][1][1]);
}
if (lo <= hi)
dp[i][1] = {lo, hi};
}
}
if ((dp[2 * n - 1][0][0] <= n && n <= dp[2 * n - 1][0][1]) || (dp[2 * n - 1][1][0] <= n && n <= dp[2 * n - 1][1][1]))
{
string res = "";
int m = n;
int last = INT_MAX;
for (int i = 2 * n - 1; i >= 0; i--)
{
if (dp[i][0][0] != -1 && dp[i][0][0] <= m && m <= dp[i][0][1] && a[i] <= last)
{
res += 'A';
m--;
last = a[i];
}
else
{
res += 'B';
last = b[i];
}
}
reverse(res.begin(), res.end());
assert(m == 0);
cout << res << '\n';
}
else
cout << -1 << '\n';
}
int main()
{
ios_base::sync_with_stdio(false), cin.tie(NULL);
solve();
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |