#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
#define F0R(i, a) for(int i=0; i<a; i++)
#define FOR(i, a, b) for(int i=a; i<=b; i++)
#define RFOR(i, b, a) for(int i=b; i>=a; i--)
#define f first
#define s second
#define pb push_back
#define INF 0x3f3f3f3f
#define MOD 998244353LL
#define MN 1000005
int n;
int a[MN], b[MN];
pii rg[MN][2]; //# A chosen, min-max
int main(){
cin >> n;
FOR(i, 1, 2*n) cin >> a[i];
FOR(i, 1, 2*n) cin >> b[i];
FOR(i, 1, 2*n) rg[i][0] = rg[i][1] = {INF, -INF};
FOR(i, 1, 2*n){
if(a[i] >= a[i-1]){
rg[i][0].f = min(rg[i][0].f, rg[i-1][0].f+1);
rg[i][0].s = max(rg[i][0].s, rg[i-1][0].s+1);
}
if(a[i] >= b[i-1]){
rg[i][0].f = min(rg[i][0].f, rg[i-1][1].f+1);
rg[i][0].s = max(rg[i][0].s, rg[i-1][1].s+1);
}
if(b[i] >= a[i-1]){
rg[i][1].f = min(rg[i][1].f, rg[i-1][0].f);
rg[i][1].s = max(rg[i][1].s, rg[i-1][0].s);
}
if(b[i] >= b[i-1]){
rg[i][1].f = min(rg[i][1].f, rg[i-1][1].f);
rg[i][1].s = max(rg[i][1].s, rg[i-1][1].s);
}
}
int onA, cur=n;
if(rg[2*n][0].f <= n && rg[2*n][0].s >= n){
onA = true;
} else if(rg[2*n][1].f <= n && rg[2*n][1].s >= n){
onA = false;
} else{
cout << "-1\n";
return 0;
}
string s;
RFOR(i, 2*n, 1){
if(onA) s.pb('A');
else s.pb('B');
if(onA){
--cur;
if(a[i-1] <= a[i] && rg[i-1][0].f <= cur && cur <= rg[i-1][0].s){
onA = true;
} else if(b[i-1] <= a[i] && rg[i-1][1].f <= cur && cur <= rg[i-1][1].s){
onA = false;
} else{
assert(false);
}
} else{
if(a[i-1] <= b[i] && rg[i-1][0].f <= cur && cur <= rg[i-1][0].s){
onA = true;
} else if(b[i-1] <= b[i] && rg[i-1][1].f <= cur && cur <= rg[i-1][1].s){
onA = false;
} else{
assert(false);
}
}
}
reverse(s.begin(), s.end());
cout << s << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
9 ms |
512 KB |
Output is correct |
6 |
Correct |
11 ms |
512 KB |
Output is correct |
7 |
Correct |
9 ms |
512 KB |
Output is correct |
8 |
Correct |
9 ms |
512 KB |
Output is correct |
9 |
Correct |
9 ms |
512 KB |
Output is correct |
10 |
Correct |
8 ms |
512 KB |
Output is correct |
11 |
Correct |
9 ms |
512 KB |
Output is correct |
12 |
Correct |
10 ms |
512 KB |
Output is correct |
13 |
Correct |
12 ms |
512 KB |
Output is correct |
14 |
Correct |
9 ms |
512 KB |
Output is correct |
15 |
Correct |
9 ms |
512 KB |
Output is correct |
16 |
Correct |
9 ms |
512 KB |
Output is correct |
17 |
Correct |
10 ms |
512 KB |
Output is correct |
18 |
Correct |
10 ms |
512 KB |
Output is correct |
19 |
Correct |
10 ms |
512 KB |
Output is correct |
20 |
Correct |
7 ms |
512 KB |
Output is correct |
21 |
Correct |
7 ms |
512 KB |
Output is correct |
22 |
Correct |
7 ms |
512 KB |
Output is correct |
23 |
Correct |
7 ms |
512 KB |
Output is correct |
24 |
Correct |
9 ms |
512 KB |
Output is correct |
25 |
Correct |
8 ms |
640 KB |
Output is correct |
26 |
Correct |
8 ms |
512 KB |
Output is correct |
27 |
Correct |
8 ms |
512 KB |
Output is correct |
28 |
Correct |
7 ms |
512 KB |
Output is correct |
29 |
Correct |
8 ms |
512 KB |
Output is correct |
30 |
Correct |
7 ms |
512 KB |
Output is correct |
31 |
Correct |
8 ms |
640 KB |
Output is correct |
32 |
Correct |
7 ms |
512 KB |
Output is correct |
33 |
Correct |
8 ms |
512 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
9 ms |
512 KB |
Output is correct |
6 |
Correct |
11 ms |
512 KB |
Output is correct |
7 |
Correct |
9 ms |
512 KB |
Output is correct |
8 |
Correct |
9 ms |
512 KB |
Output is correct |
9 |
Correct |
9 ms |
512 KB |
Output is correct |
10 |
Correct |
8 ms |
512 KB |
Output is correct |
11 |
Correct |
9 ms |
512 KB |
Output is correct |
12 |
Correct |
10 ms |
512 KB |
Output is correct |
13 |
Correct |
12 ms |
512 KB |
Output is correct |
14 |
Correct |
9 ms |
512 KB |
Output is correct |
15 |
Correct |
9 ms |
512 KB |
Output is correct |
16 |
Correct |
9 ms |
512 KB |
Output is correct |
17 |
Correct |
10 ms |
512 KB |
Output is correct |
18 |
Correct |
10 ms |
512 KB |
Output is correct |
19 |
Correct |
10 ms |
512 KB |
Output is correct |
20 |
Correct |
7 ms |
512 KB |
Output is correct |
21 |
Correct |
7 ms |
512 KB |
Output is correct |
22 |
Correct |
7 ms |
512 KB |
Output is correct |
23 |
Correct |
7 ms |
512 KB |
Output is correct |
24 |
Correct |
9 ms |
512 KB |
Output is correct |
25 |
Correct |
8 ms |
640 KB |
Output is correct |
26 |
Correct |
8 ms |
512 KB |
Output is correct |
27 |
Correct |
8 ms |
512 KB |
Output is correct |
28 |
Correct |
7 ms |
512 KB |
Output is correct |
29 |
Correct |
8 ms |
512 KB |
Output is correct |
30 |
Correct |
7 ms |
512 KB |
Output is correct |
31 |
Correct |
8 ms |
640 KB |
Output is correct |
32 |
Correct |
7 ms |
512 KB |
Output is correct |
33 |
Correct |
8 ms |
512 KB |
Output is correct |
34 |
Correct |
1174 ms |
24084 KB |
Output is correct |
35 |
Correct |
1149 ms |
24880 KB |
Output is correct |
36 |
Correct |
1144 ms |
24392 KB |
Output is correct |
37 |
Correct |
1177 ms |
24920 KB |
Output is correct |
38 |
Correct |
1121 ms |
24852 KB |
Output is correct |
39 |
Correct |
1073 ms |
24936 KB |
Output is correct |
40 |
Correct |
1172 ms |
26532 KB |
Output is correct |
41 |
Correct |
1110 ms |
25532 KB |
Output is correct |
42 |
Correct |
1263 ms |
25968 KB |
Output is correct |
43 |
Correct |
1215 ms |
45404 KB |
Output is correct |
44 |
Correct |
1210 ms |
45460 KB |
Output is correct |
45 |
Correct |
1214 ms |
45396 KB |
Output is correct |
46 |
Correct |
1212 ms |
45292 KB |
Output is correct |
47 |
Correct |
1152 ms |
26604 KB |
Output is correct |
48 |
Correct |
1151 ms |
26668 KB |
Output is correct |
49 |
Correct |
1198 ms |
45008 KB |
Output is correct |
50 |
Correct |
1172 ms |
26732 KB |
Output is correct |
51 |
Correct |
1182 ms |
26732 KB |
Output is correct |
52 |
Correct |
659 ms |
33644 KB |
Output is correct |
53 |
Correct |
668 ms |
33516 KB |
Output is correct |
54 |
Correct |
652 ms |
33712 KB |
Output is correct |
55 |
Correct |
627 ms |
33388 KB |
Output is correct |
56 |
Correct |
1224 ms |
44136 KB |
Output is correct |
57 |
Correct |
981 ms |
40348 KB |
Output is correct |
58 |
Correct |
991 ms |
40556 KB |
Output is correct |
59 |
Correct |
987 ms |
40672 KB |
Output is correct |
60 |
Correct |
945 ms |
38576 KB |
Output is correct |
61 |
Correct |
1004 ms |
41108 KB |
Output is correct |
62 |
Correct |
981 ms |
40368 KB |
Output is correct |
63 |
Correct |
1004 ms |
40940 KB |
Output is correct |
64 |
Correct |
975 ms |
39600 KB |
Output is correct |
65 |
Correct |
1002 ms |
41036 KB |
Output is correct |