#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
int N;
int A[MAXN * 2];
int B[MAXN * 2];
namespace solution_naive {
int memo[5005][5005][2];
string ans;
void read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 1; i <= 2 * N; i++) {
cin >> A[i];
}
for (int i = 1; i <= 2 * N; i++) {
cin >> B[i];
}
A[0] = B[0] = 0;
A[2 * N + 1] = B[2 * N + 1] = 2e9;
}
int dp(int cur, int a, int last) {
if (a > N) return 0;
if (cur == 2 * N + 1) return a == N;
if (memo[cur][a][last] != -1) return memo[cur][a][last];
int res = 0;
int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);
if (prv <= A[cur]) res = max(res, dp(cur + 1, a + 1, 0));
if (prv <= B[cur]) res = max(res, dp(cur + 1, a, 1));
return memo[cur][a][last] = res;
}
void trace(int cur, int a, int last) {
if (cur == 2 * N + 1) return;
int res = 0;
int prv = (last == 0 ? A[cur - 1] : B[cur - 1]);
if (prv <= A[cur] && dp(cur + 1, a + 1, 0) == 1) {
ans.push_back('A');
trace(cur + 1, a + 1, 0);
} else if (prv <= B[cur] && dp(cur + 1, a, 1) == 1) {
ans.push_back('B');
trace(cur + 1, a, 1);
}
}
void solve() {
read();
memset(memo, -1, sizeof(memo));
trace(1, 0, 0);
if (ans.empty()) ans = "-1";
cout << ans << "\n";
}
} // NAMESPACE
namespace full_solution {
void read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 0; i < 2 * N; i++) {
cin >> A[i];
}
for (int i = 0; i < 2 * N; i++) {
cin >> B[i];
}
}
vector<pair<int, int>> adj[MAXN * 4]; // (to, value)
void init() {
for (int i = 0; i + 1 < 2 * N; i++) {
if (A[i] <= A[i + 1]) adj[i * 2].emplace_back(i * 2 + 2, 1);
if (A[i] <= B[i + 1]) adj[i * 2].emplace_back(i * 2 + 3, 0);
if (B[i] <= A[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 2, 1);
if (B[i] <= B[i + 1]) adj[i * 2 + 1].emplace_back(i * 2 + 3, 0);
}
adj[4 * N].emplace_back(0, 1);
adj[4 * N].emplace_back(1, 0);
}
int vis[MAXN * 4];
// set<int> all[MAXN * 4]; (all possible value of all possible paths)
pair<int, int> dp[MAXN * 4]; // all[n] has consecutive elements, save this interval in a dp of (min, max)
void dfs(int n) {
if (vis[n]) return;
vis[n] = 1;
int mn = -1, mx = -1;
// all[n] has consecutive elements due to nature of naive_dp's transition (shifting elements only by 1 position, then ORing them).
for (auto &i : adj[n]) {
dfs(i.first);
if (dp[i.first] == make_pair(-1, -1)) {
continue;
}
if (mn == -1 || mn > dp[i.first].first + i.second) {
mn = dp[i.first].first + i.second;
}
if (mx == -1 || mx < dp[i.first].second + i.second) {
mx = dp[i.first].second + i.second;
}
}
dp[n] = make_pair(mn, mx);
}
string ans;
void trace(int n, int cur = N) {
if (dp[n] == make_pair(-1, -1) || !(dp[n].first <= cur && cur <= dp[n].second)) {
ans = "-1";
return;
}
for (auto &i : adj[n]) {
if (dp[i.first] != make_pair(-1, -1) && dp[i.first].first <= cur - i.second && cur - i.second <= dp[i.first].second) {
if (i.second == 1) ans.push_back('A');
if (i.second == 0) ans.push_back('B');
trace(i.first, cur - i.second);
return;
}
}
}
void solve() {
read();
init();
dp[4 * N - 2] = make_pair(0, 0);
dp[4 * N - 1] = make_pair(0, 0);
vis[4 * N - 2] = 1;
vis[4 * N - 1] = 1;
dfs(4 * N);
trace(4 * N);
cout << ans << "\n";
}
} /// NAMESPACE
int main() {
full_solution::solve();
return 0;
}
Compilation message
building4.cpp: In function 'void solution_naive::trace(int, int, int)':
building4.cpp:46:7: warning: unused variable 'res' [-Wunused-variable]
int res = 0;
^~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47488 KB |
Output is correct |
2 |
Correct |
32 ms |
47360 KB |
Output is correct |
3 |
Correct |
32 ms |
47360 KB |
Output is correct |
4 |
Correct |
32 ms |
47360 KB |
Output is correct |
5 |
Correct |
33 ms |
47608 KB |
Output is correct |
6 |
Correct |
33 ms |
47872 KB |
Output is correct |
7 |
Correct |
33 ms |
47872 KB |
Output is correct |
8 |
Correct |
34 ms |
47864 KB |
Output is correct |
9 |
Correct |
34 ms |
47864 KB |
Output is correct |
10 |
Correct |
34 ms |
47872 KB |
Output is correct |
11 |
Correct |
33 ms |
47864 KB |
Output is correct |
12 |
Correct |
34 ms |
47992 KB |
Output is correct |
13 |
Correct |
34 ms |
48000 KB |
Output is correct |
14 |
Correct |
34 ms |
48000 KB |
Output is correct |
15 |
Correct |
34 ms |
47992 KB |
Output is correct |
16 |
Correct |
34 ms |
48000 KB |
Output is correct |
17 |
Correct |
34 ms |
47992 KB |
Output is correct |
18 |
Correct |
34 ms |
47992 KB |
Output is correct |
19 |
Correct |
35 ms |
47992 KB |
Output is correct |
20 |
Correct |
34 ms |
47864 KB |
Output is correct |
21 |
Correct |
33 ms |
47864 KB |
Output is correct |
22 |
Correct |
39 ms |
48000 KB |
Output is correct |
23 |
Correct |
33 ms |
48000 KB |
Output is correct |
24 |
Correct |
33 ms |
47992 KB |
Output is correct |
25 |
Correct |
33 ms |
48000 KB |
Output is correct |
26 |
Correct |
33 ms |
47992 KB |
Output is correct |
27 |
Correct |
33 ms |
47872 KB |
Output is correct |
28 |
Correct |
33 ms |
47872 KB |
Output is correct |
29 |
Correct |
35 ms |
48000 KB |
Output is correct |
30 |
Correct |
33 ms |
47872 KB |
Output is correct |
31 |
Correct |
33 ms |
48000 KB |
Output is correct |
32 |
Correct |
33 ms |
47864 KB |
Output is correct |
33 |
Correct |
34 ms |
48000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
35 ms |
47488 KB |
Output is correct |
2 |
Correct |
32 ms |
47360 KB |
Output is correct |
3 |
Correct |
32 ms |
47360 KB |
Output is correct |
4 |
Correct |
32 ms |
47360 KB |
Output is correct |
5 |
Correct |
33 ms |
47608 KB |
Output is correct |
6 |
Correct |
33 ms |
47872 KB |
Output is correct |
7 |
Correct |
33 ms |
47872 KB |
Output is correct |
8 |
Correct |
34 ms |
47864 KB |
Output is correct |
9 |
Correct |
34 ms |
47864 KB |
Output is correct |
10 |
Correct |
34 ms |
47872 KB |
Output is correct |
11 |
Correct |
33 ms |
47864 KB |
Output is correct |
12 |
Correct |
34 ms |
47992 KB |
Output is correct |
13 |
Correct |
34 ms |
48000 KB |
Output is correct |
14 |
Correct |
34 ms |
48000 KB |
Output is correct |
15 |
Correct |
34 ms |
47992 KB |
Output is correct |
16 |
Correct |
34 ms |
48000 KB |
Output is correct |
17 |
Correct |
34 ms |
47992 KB |
Output is correct |
18 |
Correct |
34 ms |
47992 KB |
Output is correct |
19 |
Correct |
35 ms |
47992 KB |
Output is correct |
20 |
Correct |
34 ms |
47864 KB |
Output is correct |
21 |
Correct |
33 ms |
47864 KB |
Output is correct |
22 |
Correct |
39 ms |
48000 KB |
Output is correct |
23 |
Correct |
33 ms |
48000 KB |
Output is correct |
24 |
Correct |
33 ms |
47992 KB |
Output is correct |
25 |
Correct |
33 ms |
48000 KB |
Output is correct |
26 |
Correct |
33 ms |
47992 KB |
Output is correct |
27 |
Correct |
33 ms |
47872 KB |
Output is correct |
28 |
Correct |
33 ms |
47872 KB |
Output is correct |
29 |
Correct |
35 ms |
48000 KB |
Output is correct |
30 |
Correct |
33 ms |
47872 KB |
Output is correct |
31 |
Correct |
33 ms |
48000 KB |
Output is correct |
32 |
Correct |
33 ms |
47864 KB |
Output is correct |
33 |
Correct |
34 ms |
48000 KB |
Output is correct |
34 |
Correct |
415 ms |
96888 KB |
Output is correct |
35 |
Correct |
479 ms |
171056 KB |
Output is correct |
36 |
Correct |
479 ms |
169136 KB |
Output is correct |
37 |
Correct |
494 ms |
171824 KB |
Output is correct |
38 |
Correct |
521 ms |
181296 KB |
Output is correct |
39 |
Correct |
488 ms |
180400 KB |
Output is correct |
40 |
Correct |
542 ms |
190572 KB |
Output is correct |
41 |
Correct |
552 ms |
184412 KB |
Output is correct |
42 |
Correct |
470 ms |
156596 KB |
Output is correct |
43 |
Correct |
526 ms |
180972 KB |
Output is correct |
44 |
Correct |
629 ms |
180972 KB |
Output is correct |
45 |
Correct |
515 ms |
180848 KB |
Output is correct |
46 |
Correct |
555 ms |
191468 KB |
Output is correct |
47 |
Correct |
521 ms |
187628 KB |
Output is correct |
48 |
Correct |
516 ms |
190444 KB |
Output is correct |
49 |
Correct |
535 ms |
191340 KB |
Output is correct |
50 |
Correct |
514 ms |
180588 KB |
Output is correct |
51 |
Correct |
510 ms |
180588 KB |
Output is correct |
52 |
Correct |
402 ms |
180844 KB |
Output is correct |
53 |
Correct |
393 ms |
180844 KB |
Output is correct |
54 |
Correct |
416 ms |
191260 KB |
Output is correct |
55 |
Correct |
398 ms |
187500 KB |
Output is correct |
56 |
Correct |
531 ms |
191468 KB |
Output is correct |
57 |
Correct |
476 ms |
190700 KB |
Output is correct |
58 |
Correct |
482 ms |
191340 KB |
Output is correct |
59 |
Correct |
460 ms |
191380 KB |
Output is correct |
60 |
Correct |
433 ms |
182704 KB |
Output is correct |
61 |
Correct |
477 ms |
191340 KB |
Output is correct |
62 |
Correct |
475 ms |
189292 KB |
Output is correct |
63 |
Correct |
461 ms |
191216 KB |
Output is correct |
64 |
Correct |
449 ms |
186288 KB |
Output is correct |
65 |
Correct |
471 ms |
191208 KB |
Output is correct |