#include <bits/extc++.h>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define ll long long
// #define double long double
#define all(x) x.begin(), x.end()
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
#define f first
#define s second
using pii = pair<int, int>;
// #define endl '\n'
const ll inf = 1ll << 60;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n; cin >> n; n *= 2;
vector<int> a(n), b(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
}
for(int i = 0; i < n; i++) {
cin >> b[i];
}
vector<pair<pii, pii>> dp(n, {{-1, -1}, {-1, -1}});
dp[n - 1] = {{1, 1}, {0, 0}};
auto merge = [&](pii a, pii b) {
if(min(a, b) == pii{-1, -1}) return max(a, b);
return pii{min(a.f, b.f), max(a.s, b.s)};
};
for(int i = n - 2; i >= 0; i--) {
if(a[i] <= a[i + 1]) {
dp[i].f = merge(dp[i].f, dp[i + 1].f);
}
if(a[i] <= b[i + 1]) {
dp[i].f = merge(dp[i].f, dp[i + 1].s);
}
if(dp[i].f != pii{-1, -1}) {
dp[i].f.f++;
dp[i].f.s++;
}
if(b[i] <= a[i + 1]) {
dp[i].s = merge(dp[i].s, dp[i + 1].f);
}
if(b[i] <= b[i + 1]) {
dp[i].s = merge(dp[i].s, dp[i + 1].s);
}
// cout << i << " " << dp[i].f.f << " " << dp[i].f.s << " " << dp[i].s.f << " " << dp[i].s.s << endl;
}
int rem = n / 2;
int last = -1;
string ans;
auto die = [&]() {
cout << -1 << endl;
exit(0);
};
for(int i = 0; i < n; i++) {
if(last <= a[i] && dp[i].f.f <= rem && rem <= dp[i].f.s) {
ans += "A";
last = a[i];
rem--;
} else if(last <= b[i] && dp[i].s != pii{-1, -1}) {
ans += "B";
last = b[i];
} else {
die();
}
}
if(count(all(ans), 'A') != n / 2) die();
cout << ans << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
564 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
560 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
2 ms |
604 KB |
Output is correct |
7 |
Correct |
2 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
564 KB |
Output is correct |
11 |
Correct |
1 ms |
604 KB |
Output is correct |
12 |
Correct |
1 ms |
604 KB |
Output is correct |
13 |
Correct |
1 ms |
604 KB |
Output is correct |
14 |
Correct |
1 ms |
604 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
600 KB |
Output is correct |
18 |
Correct |
1 ms |
604 KB |
Output is correct |
19 |
Correct |
1 ms |
604 KB |
Output is correct |
20 |
Correct |
1 ms |
604 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
1 ms |
604 KB |
Output is correct |
23 |
Correct |
1 ms |
604 KB |
Output is correct |
24 |
Correct |
2 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
604 KB |
Output is correct |
27 |
Correct |
1 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
604 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
1 ms |
560 KB |
Output is correct |
34 |
Correct |
188 ms |
65528 KB |
Output is correct |
35 |
Correct |
168 ms |
63776 KB |
Output is correct |
36 |
Correct |
165 ms |
62652 KB |
Output is correct |
37 |
Correct |
184 ms |
64088 KB |
Output is correct |
38 |
Correct |
167 ms |
63964 KB |
Output is correct |
39 |
Correct |
163 ms |
63252 KB |
Output is correct |
40 |
Correct |
176 ms |
68220 KB |
Output is correct |
41 |
Correct |
157 ms |
64780 KB |
Output is correct |
42 |
Correct |
184 ms |
66472 KB |
Output is correct |
43 |
Correct |
188 ms |
68636 KB |
Output is correct |
44 |
Correct |
205 ms |
68820 KB |
Output is correct |
45 |
Correct |
183 ms |
68776 KB |
Output is correct |
46 |
Correct |
184 ms |
68692 KB |
Output is correct |
47 |
Correct |
172 ms |
67912 KB |
Output is correct |
48 |
Correct |
192 ms |
67540 KB |
Output is correct |
49 |
Correct |
179 ms |
68564 KB |
Output is correct |
50 |
Correct |
178 ms |
67808 KB |
Output is correct |
51 |
Correct |
178 ms |
67912 KB |
Output is correct |
52 |
Correct |
133 ms |
56932 KB |
Output is correct |
53 |
Correct |
127 ms |
57052 KB |
Output is correct |
54 |
Correct |
139 ms |
56908 KB |
Output is correct |
55 |
Correct |
125 ms |
56648 KB |
Output is correct |
56 |
Correct |
179 ms |
68884 KB |
Output is correct |
57 |
Correct |
155 ms |
63612 KB |
Output is correct |
58 |
Correct |
152 ms |
64080 KB |
Output is correct |
59 |
Correct |
185 ms |
63952 KB |
Output is correct |
60 |
Correct |
151 ms |
60432 KB |
Output is correct |
61 |
Correct |
153 ms |
64328 KB |
Output is correct |
62 |
Correct |
150 ms |
63596 KB |
Output is correct |
63 |
Correct |
160 ms |
64328 KB |
Output is correct |
64 |
Correct |
148 ms |
62336 KB |
Output is correct |
65 |
Correct |
155 ms |
64464 KB |
Output is correct |