#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
#define f first
#define s second
typedef vector<ll> vi;
typedef vector<pi> vpi;
#define pb push_back
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
const ll INF = 1e18 + 100;
const pi PINF = pi(INF, INF);
ll n, a[1000005], b[1000005], v, rv;
pi range[1000005][2]; //0 A, 1 B
string ans;
bool A;
inline pi add(pi a, ll v) {
return pi(a.f+v, a.s+v);
}
inline pi merge(pi a, pi b) {
if (a == PINF) return b;
if (b == PINF) return a;
return pi(min(a.f, b.f), max(a.s, b.s));
}
inline bool inter(pi a, int b) {
return (a.f <= b and b <= a.s);
}
void fail() {
cout << -1;
exit(0);
}
int main() {
fastio; cin >> n;
FOR(i, 1, 2*n) cin >> a[i];
FOR(i, 1, 2*n) cin >> b[i];
range[1][0] = pi(1, 1);
range[1][1] = pi(-1, -1);
FOR(i, 2, 2*n) {
range[i][0] = PINF; range[i][1] = PINF;
if (a[i] >= a[i-1] and range[i-1][0] != PINF) range[i][0] = add(range[i-1][0], 1);
if (a[i] >= b[i-1] and range[i-1][1] != PINF) range[i][0] = merge(range[i][0], add(range[i-1][1], 1));
if (b[i] >= a[i-1] and range[i-1][0] != PINF) range[i][1] = add(range[i-1][0], -1);
if (b[i] >= b[i-1] and range[i-1][1] != PINF) range[i][1] = merge(range[i][1], add(range[i-1][1], -1));
}
v = -1, A = 0, rv = INF;
DEC(i, 2*n+1, 2) {
v = v + (A ? -1 : 1);
if (inter(range[i-1][0], v) and rv >= a[i-1]) A = 1;
else if (inter(range[i-1][1], v) and rv >= b[i-1]) A = 0;
else fail();
ans += (A ? 'A' : 'B');
rv = (A ? a[i-1] : b[i-1]);
}
reverse(all(ans));
cout << ans;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Correct |
6 ms |
640 KB |
Output is correct |
13 |
Correct |
6 ms |
640 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
6 ms |
640 KB |
Output is correct |
16 |
Correct |
6 ms |
640 KB |
Output is correct |
17 |
Correct |
6 ms |
640 KB |
Output is correct |
18 |
Correct |
6 ms |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
5 ms |
640 KB |
Output is correct |
21 |
Correct |
5 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
640 KB |
Output is correct |
23 |
Correct |
5 ms |
640 KB |
Output is correct |
24 |
Correct |
6 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
640 KB |
Output is correct |
26 |
Correct |
5 ms |
640 KB |
Output is correct |
27 |
Correct |
5 ms |
640 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
640 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
640 KB |
Output is correct |
32 |
Correct |
5 ms |
640 KB |
Output is correct |
33 |
Correct |
5 ms |
640 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 |
4 ms |
384 KB |
Output is correct |
5 |
Correct |
6 ms |
640 KB |
Output is correct |
6 |
Correct |
6 ms |
640 KB |
Output is correct |
7 |
Correct |
6 ms |
640 KB |
Output is correct |
8 |
Correct |
6 ms |
640 KB |
Output is correct |
9 |
Correct |
6 ms |
640 KB |
Output is correct |
10 |
Correct |
5 ms |
512 KB |
Output is correct |
11 |
Correct |
6 ms |
640 KB |
Output is correct |
12 |
Correct |
6 ms |
640 KB |
Output is correct |
13 |
Correct |
6 ms |
640 KB |
Output is correct |
14 |
Correct |
6 ms |
640 KB |
Output is correct |
15 |
Correct |
6 ms |
640 KB |
Output is correct |
16 |
Correct |
6 ms |
640 KB |
Output is correct |
17 |
Correct |
6 ms |
640 KB |
Output is correct |
18 |
Correct |
6 ms |
640 KB |
Output is correct |
19 |
Correct |
6 ms |
640 KB |
Output is correct |
20 |
Correct |
5 ms |
640 KB |
Output is correct |
21 |
Correct |
5 ms |
640 KB |
Output is correct |
22 |
Correct |
5 ms |
640 KB |
Output is correct |
23 |
Correct |
5 ms |
640 KB |
Output is correct |
24 |
Correct |
6 ms |
640 KB |
Output is correct |
25 |
Correct |
6 ms |
640 KB |
Output is correct |
26 |
Correct |
5 ms |
640 KB |
Output is correct |
27 |
Correct |
5 ms |
640 KB |
Output is correct |
28 |
Correct |
5 ms |
512 KB |
Output is correct |
29 |
Correct |
5 ms |
640 KB |
Output is correct |
30 |
Correct |
5 ms |
512 KB |
Output is correct |
31 |
Correct |
6 ms |
640 KB |
Output is correct |
32 |
Correct |
5 ms |
640 KB |
Output is correct |
33 |
Correct |
5 ms |
640 KB |
Output is correct |
34 |
Correct |
291 ms |
46560 KB |
Output is correct |
35 |
Correct |
286 ms |
46000 KB |
Output is correct |
36 |
Correct |
290 ms |
45232 KB |
Output is correct |
37 |
Correct |
292 ms |
46128 KB |
Output is correct |
38 |
Correct |
283 ms |
46128 KB |
Output is correct |
39 |
Correct |
280 ms |
46384 KB |
Output is correct |
40 |
Correct |
299 ms |
49376 KB |
Output is correct |
41 |
Correct |
277 ms |
47152 KB |
Output is correct |
42 |
Correct |
290 ms |
47920 KB |
Output is correct |
43 |
Correct |
310 ms |
52076 KB |
Output is correct |
44 |
Correct |
311 ms |
52072 KB |
Output is correct |
45 |
Correct |
309 ms |
52076 KB |
Output is correct |
46 |
Correct |
293 ms |
52076 KB |
Output is correct |
47 |
Correct |
303 ms |
49616 KB |
Output is correct |
48 |
Correct |
297 ms |
49644 KB |
Output is correct |
49 |
Correct |
319 ms |
52232 KB |
Output is correct |
50 |
Correct |
323 ms |
49496 KB |
Output is correct |
51 |
Correct |
306 ms |
49516 KB |
Output is correct |
52 |
Correct |
190 ms |
50668 KB |
Output is correct |
53 |
Correct |
191 ms |
50672 KB |
Output is correct |
54 |
Correct |
187 ms |
50540 KB |
Output is correct |
55 |
Correct |
170 ms |
50540 KB |
Output is correct |
56 |
Correct |
318 ms |
51820 KB |
Output is correct |
57 |
Correct |
268 ms |
50372 KB |
Output is correct |
58 |
Correct |
260 ms |
50540 KB |
Output is correct |
59 |
Correct |
260 ms |
50412 KB |
Output is correct |
60 |
Correct |
258 ms |
47440 KB |
Output is correct |
61 |
Correct |
271 ms |
50556 KB |
Output is correct |
62 |
Correct |
257 ms |
49772 KB |
Output is correct |
63 |
Correct |
268 ms |
50412 KB |
Output is correct |
64 |
Correct |
252 ms |
48688 KB |
Output is correct |
65 |
Correct |
261 ms |
50412 KB |
Output is correct |