# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211879 | jk89 | Building 4 (JOI20_building4) | C++14 | 4 ms | 256 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define f first
#define s second
const int MAXN = 1e6 + 3;
const int INF = 1e9 + 3;
int t[MAXN][2];
pair<int, int> dp[MAXN][2];
bool ans[MAXN];
int a = 0, b = 0, akt;
bool possible(int wym, int ind) {
if (dp[ind][wym].f == INF)
return false;
if (t[ind][wym] > t[ind + 1][akt])
return false;
return b - a >= dp[ind][wym].f && b - a <= dp[ind][wym].s;
}
void check(int wym, int ind) {
if (abs(dp[ind][wym].f - INF) == 1)
dp[ind][wym].f = INF;
if (abs(dp[ind][wym].s + INF) == 1)
dp[ind][wym].s = -INF;
}
int main() {
int n;
scanf("%d", &n);
n *= 2;
for (int i = 0; i < 2; i++) {
for (int j = 1; j <= n; j++)
scanf("%d", &t[j][i]);
}
for (int i = 1; i <= n; i++) {
dp[i][0] = dp[i][1] = {INF, -INF};
if (t[i - 1][0] <= t[i][0]) {
dp[i][0] = dp[i - 1][0];
dp[i][0].f++;
dp[i][0].s++;
}
if (t[i - 1][1] <= t[i][0]) {
dp[i][0].f = min(dp[i][0].f, dp[i - 1][1].f + 1);
dp[i][0].s = max(dp[i][0].s, dp[i - 1][1].s + 1);
}
if (t[i - 1][0] <= t[i][1]) {
dp[i][1] = dp[i - 1][0];
dp[i][1].f--;
dp[i][1].s--;
}
if (t[i - 1][1] <= t[i][1]) {
dp[i][1].f = min(dp[i][1].f, dp[i - 1][1].f - 1);
dp[i][1].s = max(dp[i][1].s, dp[i - 1][1].s - 1);
}
check(i, 0);
check(i, 1);
}
if (dp[n][0].f <= 0 && dp[n][0].s >= 0) {
a++;
akt = 0;
}
else if (dp[n][1].f <= 0 && dp[n][1].s >= 0) {
b++;
akt = 1;
ans[n] = true;
}
else {
printf("-1");
return 0;
}
for (int i = n; i > 1; i--) {
if (possible(0, i - 1)) {
a++;
akt = 0;
}
else {
b++;
akt = 1;
ans[i - 1] = true;
}
}
for (int i = 1; i <= n; i++)
printf(ans[i] ? "B" : "A");
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |