이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10, INF = 0x3f3f3f3f;
int n;
int arr[2][MAXN], dp[2][MAXN][2];
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n;
for(int i = 0; i < (n<<1); i++) cin >> arr[0][i];
for(int i = 0; i < (n<<1); i++) cin >> arr[1][i];
for(int i = 0; i < (n<<1) - 1; i++)
{
bool flag = false;
for(auto& k: {0, 1})
if(arr[k][i] <= arr[k][i+1] ||
arr[k][i] <= arr[k^1][i+1])
flag = true;
if(!flag)
return cout << -1 << "\n", 0;
}
for(auto& k: {0, 1})
dp[k][n << 1][0] = dp[k][n << 1][1] = 0;
for(int i = (n<<1) - 1; i >= 1; i--)
for(int f: {0, 1})
{
dp[0][i][f] = arr[1][i] >= arr[f][i-1] ? dp[0][i+1][1] : INF;
if(arr[0][i] >= arr[f][i - 1])
dp[0][i][f] = min(dp[0][i][f], 1 + dp[0][i+1][0]);
}
for(int i = (n<<1) - 1; i >= 1; i--)
for(int f: {0, 1})
{
dp[1][i][f] = arr[1][i] >= arr[f][i-1] ? dp[1][i+1][1] : -INF;
if(arr[0][i] >= arr[f][i - 1] && dp[1][i+1][0] != INF)
dp[1][i][f] = max(dp[1][i][f], dp[1][i+1][0]+1);
}
string ans = "";
int cnt = n, last = 0;
for(int i = 0; i < (n<<1); i++)
{
if(arr[0][i] >= last &&
dp[0][i+1][0] <= cnt-1 &&
dp[1][i+1][0] >= cnt-1 && cnt > 0)
ans += "A", last = arr[0][i], cnt--;
else if(dp[0][i+1][1] <= cnt &&
dp[1][i+1][1] >= cnt)
ans += "B";
else
return cout << -1 << "\n", 0;
}
cout << ans << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |