이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
array<int, 2> operator + (const array<int, 2> &a, int x) {
return {a[0] + x, a[1] + x};
}
array<int, 2> mrg(const array<int, 2> <, const array<int, 2> &rt) {
return {min(lt[0], lt[1]), max(rt[0], rt[1])};
}
bool inside(const array<int, 2> &a, int i) {
return a[0] <= i && i <= a[1];
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
const int inf = 1e9;
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<array<array<int, 2>, 2>> dp(2 * N);
for (int i = 1; i < 2 * N; ++i) {
for (int j = 0; j < 2; ++j) {
dp[i][j] = {inf, -inf};
}
}
dp[0][0] = {0, 0};
dp[0][1] = {1, 1};
for (int i = 1; i < 2 * N; ++i) {
if (a[i - 1] <= a[i]) {
dp[i][0] = mrg(dp[i][0], dp[i - 1][0]);
}
if (b[i - 1] <= a[i]) {
dp[i][0] = mrg(dp[i][0], dp[i - 1][1]);
}
if (a[i - 1] <= b[i]) {
dp[i][1] = mrg(dp[i][1], dp[i - 1][0] + 1);
}
if (b[i - 1] <= b[i]) {
dp[i][1] = mrg(dp[i][1], dp[i - 1][1] + 1);
}
}
int taken = N, lst = inf;
string res;
for (int i = 2 * N - 1; i >= 0; --i) {
if (inside(dp[i][0], taken) && a[i] <= lst) {
res += 'A';
lst = a[i];
} else if (inside(dp[i][1], taken) && b[i] <= lst) {
res += 'B';
taken -= 1;
lst = b[i];
} else {
cout << -1;
exit(0);
}
}
reverse(res.begin(), res.end());
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |