이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for (int i = x; i < y; i++)
#define pii pair<int, int>
#define f first
#define s second
const int mx = 1e6 + 5;
int n, A[mx][2]; pii dp[mx][2];
int main(){
cin >> n; n *= 2;
FOR(i, 1, n + 1) cin >> A[i][0];
FOR(i, 1, n + 1) cin >> A[i][1];
dp[0][0] = dp[0][1] = {0, 0};
FOR(i, 1, n + 1) FOR(k, 0, 2){
dp[i][k] = {1e9, -1e9};
FOR(prv, 0, 2) if (A[i][k] >= A[i - 1][prv]){
dp[i][k].f = min(dp[i][k].f, dp[i - 1][prv].f + !k);
dp[i][k].s = max(dp[i][k].s, dp[i - 1][prv].s + !k);
}
}
vector<char> ans; int cnt = n / 2, cur = -1;
for (int i = n; i; i--){
auto ok = [&](int use){
return (cnt >= dp[i][use].f and cnt <= dp[i][use].s) and
(cur == -1 or A[i][use] <= A[i + 1][cur]);
};
if (ok(0)) ans.push_back('A'), cnt--, cur = 0;
else if (ok(1)) ans.push_back('B'), cur = 1;
else{ cout<<-1<<endl; return 0; }
}
reverse(ans.begin(), ans.end());
for (char ret : ans) cout<<ret;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |