#include<bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pb push_back
#define ii pair<int,int>
#define iii pair<ii,int>
#define ppb pop_back
#define st first
#define nd second
#define ll long long
#define inf 100000000
#define MOD 998244353
#define LOG 40
#define EPS 0.000000001
#define MAX 1000005
using namespace std;
int n;
pair<int, int> lr[MAX][2];
int c[2][MAX];
void no() {
cout << -1;
exit(0);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n;
n <<= 1;
for(int i = 0; i < 2; i++)
for(int j = 1; j <= n; j++)
cin >> c[i][j];
lr[0][0] = lr[0][1] = {0, 0};
for(int i = 1; i <= n; i++) {
for(int plan_c = 0; plan_c < 2; plan_c++) { // 0 if a else 1
lr[i][plan_c] = {inf, -inf};
for(int plan_b = 0; plan_b < 2; plan_b++) {
if(c[plan_c][i] >= c[plan_b][i - 1]) {
lr[i][plan_c].st = min(lr[i][plan_c].st, lr[i - 1][plan_b].st + !plan_c);
lr[i][plan_c].nd = max(lr[i][plan_c].nd, lr[i - 1][plan_b].nd + !plan_c);
}
}
}
}
int ind = n;
int req = n / 2;
string ans, _map = "AB";
int last = 2;
while(ind > 0) {
for(int plan_c = 0; plan_c < 2; plan_c++) {
if(lr[ind][plan_c].st <= req and lr[ind][plan_c].nd >= req) {
if(!(last - 2) or c[last][ind + 1] >= c[plan_c][ind]) {
ans.pb(_map[plan_c]);
req -= (!plan_c);
ind--;
last = plan_c;
break ;
}
}
if(plan_c == 1)
no();
}
}
reverse(ans.begin(), ans.end());
cout << ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
1 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
1 ms |
512 KB |
Output is correct |
26 |
Correct |
1 ms |
512 KB |
Output is correct |
27 |
Correct |
1 ms |
512 KB |
Output is correct |
28 |
Correct |
1 ms |
512 KB |
Output is correct |
29 |
Correct |
1 ms |
512 KB |
Output is correct |
30 |
Correct |
1 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
512 KB |
Output is correct |
32 |
Correct |
1 ms |
512 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
4 |
Correct |
0 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
512 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
2 ms |
512 KB |
Output is correct |
9 |
Correct |
2 ms |
512 KB |
Output is correct |
10 |
Correct |
2 ms |
512 KB |
Output is correct |
11 |
Correct |
2 ms |
512 KB |
Output is correct |
12 |
Correct |
2 ms |
512 KB |
Output is correct |
13 |
Correct |
2 ms |
512 KB |
Output is correct |
14 |
Correct |
2 ms |
512 KB |
Output is correct |
15 |
Correct |
2 ms |
512 KB |
Output is correct |
16 |
Correct |
3 ms |
512 KB |
Output is correct |
17 |
Correct |
2 ms |
512 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
512 KB |
Output is correct |
20 |
Correct |
1 ms |
512 KB |
Output is correct |
21 |
Correct |
2 ms |
512 KB |
Output is correct |
22 |
Correct |
1 ms |
512 KB |
Output is correct |
23 |
Correct |
1 ms |
512 KB |
Output is correct |
24 |
Correct |
2 ms |
512 KB |
Output is correct |
25 |
Correct |
1 ms |
512 KB |
Output is correct |
26 |
Correct |
1 ms |
512 KB |
Output is correct |
27 |
Correct |
1 ms |
512 KB |
Output is correct |
28 |
Correct |
1 ms |
512 KB |
Output is correct |
29 |
Correct |
1 ms |
512 KB |
Output is correct |
30 |
Correct |
1 ms |
512 KB |
Output is correct |
31 |
Correct |
2 ms |
512 KB |
Output is correct |
32 |
Correct |
1 ms |
512 KB |
Output is correct |
33 |
Correct |
2 ms |
512 KB |
Output is correct |
34 |
Correct |
365 ms |
42440 KB |
Output is correct |
35 |
Correct |
335 ms |
42032 KB |
Output is correct |
36 |
Correct |
329 ms |
41392 KB |
Output is correct |
37 |
Correct |
343 ms |
42288 KB |
Output is correct |
38 |
Correct |
336 ms |
42160 KB |
Output is correct |
39 |
Correct |
350 ms |
41392 KB |
Output is correct |
40 |
Correct |
367 ms |
44848 KB |
Output is correct |
41 |
Correct |
334 ms |
42428 KB |
Output is correct |
42 |
Correct |
375 ms |
43876 KB |
Output is correct |
43 |
Correct |
401 ms |
45420 KB |
Output is correct |
44 |
Correct |
369 ms |
45292 KB |
Output is correct |
45 |
Correct |
372 ms |
45500 KB |
Output is correct |
46 |
Correct |
353 ms |
45420 KB |
Output is correct |
47 |
Correct |
351 ms |
44396 KB |
Output is correct |
48 |
Correct |
349 ms |
44396 KB |
Output is correct |
49 |
Correct |
350 ms |
45036 KB |
Output is correct |
50 |
Correct |
385 ms |
44524 KB |
Output is correct |
51 |
Correct |
408 ms |
44572 KB |
Output is correct |
52 |
Correct |
225 ms |
33516 KB |
Output is correct |
53 |
Correct |
232 ms |
33516 KB |
Output is correct |
54 |
Correct |
222 ms |
33768 KB |
Output is correct |
55 |
Correct |
212 ms |
33264 KB |
Output is correct |
56 |
Correct |
368 ms |
45556 KB |
Output is correct |
57 |
Correct |
309 ms |
40300 KB |
Output is correct |
58 |
Correct |
307 ms |
40552 KB |
Output is correct |
59 |
Correct |
308 ms |
40568 KB |
Output is correct |
60 |
Correct |
294 ms |
38580 KB |
Output is correct |
61 |
Correct |
308 ms |
41068 KB |
Output is correct |
62 |
Correct |
308 ms |
40432 KB |
Output is correct |
63 |
Correct |
315 ms |
40940 KB |
Output is correct |
64 |
Correct |
329 ms |
39600 KB |
Output is correct |
65 |
Correct |
352 ms |
41196 KB |
Output is correct |