이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
const int Nmax = 1e6 + 5;
int A[Nmax], B[Nmax], s[Nmax][2], f[Nmax][2];
bool ok[Nmax][2];
char ans[Nmax];
int n;
void min_to(int &x, int y)
{
if(x > y) x = y;
}
void max_to(int &x, int y)
{
if(x < y) x = y;
}
void solve(int i, int y, int z)
{
if(!z) ans[i] = 'A', y--;
else ans[i] = 'B';
if(i == 1)
{
cout << (ans+1) << '\n';
return;
}
if(!z)
{
if(A[i] >= A[i-1] && ok[i-1][0] && s[i-1][0] <= y && y <= f[i-1][0])
solve(i-1, y, 0);
else if(A[i] >= B[i-1] && ok[i-1][1] && s[i-1][1] <= y && y <= f[i-1][1])
solve(i-1, y, 1);
else assert(0);
return;
}
else
{
if(B[i] >= A[i-1] && ok[i-1][0] && s[i-1][0] <= y && y <= f[i-1][0])
solve(i-1, y, 0);
else if(B[i] >= B[i-1] && ok[i-1][1] && s[i-1][1] <= y && y <= f[i-1][1])
solve(i-1, y, 1);
else assert(0);
return;
}
}
int main()
{
// freopen("input", "r", stdin);
cin.sync_with_stdio(false); cin.tie(0);
int i;
cin >> n;
for(i=1; i<=2*n; ++i) cin >> A[i];
for(i=1; i<=2*n; ++i) cin >> B[i];
s[1][0] = f[1][0] = 1;
s[1][1] = f[1][1] = 0;
ok[1][0] = ok[1][1] = 1;
for(i=2; i<=2*n; ++i)
{
s[i][0] = s[i][1] = 2*n+1;
f[i][0] = f[i][1] = -1;
if(A[i] >= A[i-1] && ok[i-1][0])
min_to(s[i][0], s[i-1][0] + 1), max_to(f[i][0], f[i-1][0] + 1);
if(A[i] >= B[i-1] && ok[i-1][1])
min_to(s[i][0], s[i-1][1] + 1), max_to(f[i][0], f[i-1][1] + 1);
if(B[i] >= A[i-1] && ok[i-1][0])
min_to(s[i][1], s[i-1][0]), max_to(f[i][1], f[i-1][0]);
if(B[i] >= B[i-1] && ok[i-1][1])
min_to(s[i][1], s[i-1][1]), max_to(f[i][1], f[i-1][1]);
ok[i][0] = (s[i][0] <= f[i][0]);
ok[i][1] = (s[i][1] <= f[i][1]);
}
if(s[2*n][0] <= n && n <= f[2*n][0])
solve(2*n, n, 0);
else if(s[2*n][1] <= n && n <= f[2*n][1])
solve(2*n, n, 1);
else cout << "-1\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |