#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 1e6 + 5, inf = 1e9;
int N;
ll a[maxn][2];
ii f[maxn][2];
bool vis[maxn][2];
void trav(int pos, int t)
{
if(vis[pos][t]) return;
vis[pos][t] = true;
int mn = inf, mx = -inf;
if(a[pos][t] <= a[pos + 1][1]){
trav(pos + 1, 1);
mn = min(mn, f[pos + 1][1].fi);
mx = max(mx, f[pos + 1][1].se);
}
if(a[pos][t] <= a[pos + 1][0]){
trav(pos + 1, 0);
mn = min(mn, f[pos + 1][0].fi + 1);
mx = max(mx, f[pos + 1][0].se + 1);
}
//cerr << pos << ' ' << t << ' ' << mn << ' ' << mx << '\n';
f[pos][t] = mp(mn, mx);
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifdef LOCAL
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
#endif // LOCAL
cin >> N; N *= 2;
for(int j = 0; j < 2; ++j){
for(int i = 1; i <= N; ++i)
cin >> a[i][j];
}
vis[N][0] = vis[N][1] = true;
trav(0, 0);
if(f[0][0].fi > N / 2 || f[0][0].fi > f[0][0].se){
cout << -1;
return 0;
}
int last = 0;
int cur = N / 2;
for(int i = 1; i <= N; ++i){
if(a[i][0] >= a[i - 1][last] && f[i][0].fi <= cur - 1 && cur - 1 <= f[i][0].se){
last = 0;
--cur;
cout << 'A';
}
else{
last = 1;
cout << 'B';
}
}
}
# |
Verdict |
Execution time |
Memory |
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 |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
7 ms |
960 KB |
Output is correct |
9 |
Correct |
6 ms |
768 KB |
Output is correct |
10 |
Correct |
7 ms |
768 KB |
Output is correct |
11 |
Correct |
7 ms |
896 KB |
Output is correct |
12 |
Correct |
7 ms |
964 KB |
Output is correct |
13 |
Correct |
6 ms |
896 KB |
Output is correct |
14 |
Correct |
6 ms |
896 KB |
Output is correct |
15 |
Correct |
6 ms |
896 KB |
Output is correct |
16 |
Correct |
6 ms |
896 KB |
Output is correct |
17 |
Correct |
6 ms |
896 KB |
Output is correct |
18 |
Correct |
6 ms |
896 KB |
Output is correct |
19 |
Correct |
6 ms |
896 KB |
Output is correct |
20 |
Correct |
6 ms |
768 KB |
Output is correct |
21 |
Correct |
6 ms |
768 KB |
Output is correct |
22 |
Correct |
5 ms |
768 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
6 ms |
896 KB |
Output is correct |
25 |
Correct |
6 ms |
896 KB |
Output is correct |
26 |
Correct |
6 ms |
768 KB |
Output is correct |
27 |
Correct |
6 ms |
768 KB |
Output is correct |
28 |
Correct |
6 ms |
768 KB |
Output is correct |
29 |
Correct |
6 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
768 KB |
Output is correct |
31 |
Correct |
6 ms |
896 KB |
Output is correct |
32 |
Correct |
6 ms |
768 KB |
Output is correct |
33 |
Correct |
6 ms |
896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
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 |
6 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
512 KB |
Output is correct |
6 |
Correct |
6 ms |
768 KB |
Output is correct |
7 |
Correct |
6 ms |
768 KB |
Output is correct |
8 |
Correct |
7 ms |
960 KB |
Output is correct |
9 |
Correct |
6 ms |
768 KB |
Output is correct |
10 |
Correct |
7 ms |
768 KB |
Output is correct |
11 |
Correct |
7 ms |
896 KB |
Output is correct |
12 |
Correct |
7 ms |
964 KB |
Output is correct |
13 |
Correct |
6 ms |
896 KB |
Output is correct |
14 |
Correct |
6 ms |
896 KB |
Output is correct |
15 |
Correct |
6 ms |
896 KB |
Output is correct |
16 |
Correct |
6 ms |
896 KB |
Output is correct |
17 |
Correct |
6 ms |
896 KB |
Output is correct |
18 |
Correct |
6 ms |
896 KB |
Output is correct |
19 |
Correct |
6 ms |
896 KB |
Output is correct |
20 |
Correct |
6 ms |
768 KB |
Output is correct |
21 |
Correct |
6 ms |
768 KB |
Output is correct |
22 |
Correct |
5 ms |
768 KB |
Output is correct |
23 |
Correct |
6 ms |
768 KB |
Output is correct |
24 |
Correct |
6 ms |
896 KB |
Output is correct |
25 |
Correct |
6 ms |
896 KB |
Output is correct |
26 |
Correct |
6 ms |
768 KB |
Output is correct |
27 |
Correct |
6 ms |
768 KB |
Output is correct |
28 |
Correct |
6 ms |
768 KB |
Output is correct |
29 |
Correct |
6 ms |
896 KB |
Output is correct |
30 |
Correct |
6 ms |
768 KB |
Output is correct |
31 |
Correct |
6 ms |
896 KB |
Output is correct |
32 |
Correct |
6 ms |
768 KB |
Output is correct |
33 |
Correct |
6 ms |
896 KB |
Output is correct |
34 |
Correct |
298 ms |
16628 KB |
Output is correct |
35 |
Correct |
397 ms |
122620 KB |
Output is correct |
36 |
Correct |
398 ms |
120596 KB |
Output is correct |
37 |
Correct |
388 ms |
123164 KB |
Output is correct |
38 |
Correct |
378 ms |
123104 KB |
Output is correct |
39 |
Correct |
370 ms |
122616 KB |
Output is correct |
40 |
Correct |
401 ms |
131104 KB |
Output is correct |
41 |
Correct |
357 ms |
125048 KB |
Output is correct |
42 |
Correct |
362 ms |
127992 KB |
Output is correct |
43 |
Correct |
379 ms |
132216 KB |
Output is correct |
44 |
Correct |
389 ms |
132160 KB |
Output is correct |
45 |
Correct |
375 ms |
132216 KB |
Output is correct |
46 |
Correct |
396 ms |
132216 KB |
Output is correct |
47 |
Correct |
372 ms |
131320 KB |
Output is correct |
48 |
Correct |
376 ms |
131192 KB |
Output is correct |
49 |
Correct |
397 ms |
131960 KB |
Output is correct |
50 |
Correct |
391 ms |
131320 KB |
Output is correct |
51 |
Correct |
391 ms |
131576 KB |
Output is correct |
52 |
Correct |
271 ms |
120440 KB |
Output is correct |
53 |
Correct |
259 ms |
120440 KB |
Output is correct |
54 |
Correct |
254 ms |
120444 KB |
Output is correct |
55 |
Correct |
277 ms |
120412 KB |
Output is correct |
56 |
Correct |
407 ms |
132488 KB |
Output is correct |
57 |
Correct |
381 ms |
126968 KB |
Output is correct |
58 |
Correct |
371 ms |
127480 KB |
Output is correct |
59 |
Correct |
396 ms |
127352 KB |
Output is correct |
60 |
Correct |
339 ms |
120184 KB |
Output is correct |
61 |
Correct |
345 ms |
127904 KB |
Output is correct |
62 |
Correct |
356 ms |
126072 KB |
Output is correct |
63 |
Correct |
342 ms |
127924 KB |
Output is correct |
64 |
Correct |
337 ms |
123512 KB |
Output is correct |
65 |
Correct |
357 ms |
127992 KB |
Output is correct |