# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
211888 | jk89 | 건물 4 (JOI20_building4) | C++14 | 4 ms | 384 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <iostream>
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;
}
}
int pop = 0;
a = b = 0;
bool por = false;
for (int i = 1; i <= n; i++) {
if (ans[i]) {
b++;
if (t[i][1] < pop)
por = true;
pop = t[i][1];
}
else {
a++;
if (t[i][0] < pop)
por = true;
pop = t[i][0];
}
}
if (por) {
string ss;
for (int j = 0; j < 2; j++) {
for (int i = 1; i <= n; i++) {
int temp = t[i][j];
while (temp) {
ss += char(temp % 10 + '0');
temp /= 10;
}
ss += "_";
}
ss += "|_";
}
cout << ss;
return 0;
}
if (a != b) {
printf("WYJEBALO");
return 0;
}
for (int i = 1; i <= n; i++)
printf(ans[i] ? "B" : "A");
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |