#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
#define debug(x...) cout << '[' << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;
const int MXN = 1000005;
int n, N, a[MXN], b[MXN];
int p[MXN];
string s, t, ans;
bitset<MXN> big, sml;
vector<pii> tanya;
vector<int> v;
void INIT() {
ans = string(N, '-');
s = string(N, 'A');
t = string(N, 'B');
FOR(i, 0, N) {
if (a[i] > b[i]) {
swap(a[i], b[i]);
swap(s[i], t[i]);
}
}
}
bool DIE() {
return (big & sml).any();
}
bool GET_NUM() {
FOR(i, 0, N - 1) {
int ls = a[i], lb = b[i], rs = a[i + 1], rb = b[i + 1];
int val = (ls <= rs) + (ls <= rb) + (lb <= rs) + (lb <= rb);
p[i] = val;
if (val == 0) return false;
if (val == 1) {
sml[i] = true;
big[i + 1] = true;
}
if (val == 2) {
if (ls <= rs) {
sml[i] = true;
} else {
big[i + 1] = true;
}
}
}
return true;
}
bool GET_3() {
for (int i = 0, j = 0; i < N - 1; i = j) {
while (j < N - 1 && (p[i] == 3) == (p[j] == 3)) j++;
if (p[i] != 3) continue;
int l = i, r = j;
if (big[l] && sml[r]) return false;
if (sml[r]) {
FOR(k, l, r + 1) {
sml[k] = true;
}
continue;
}
if (!big[l]) tanya.push_back(mp(l, r + 1));
FOR(k, l, r + 1) {
big[k] = true;
}
}
return true;
}
void FREE() {
FOR(i, 0, N) if (!big[i] && !sml[i]) {
big[i] = true;
tanya.push_back(mp(i, i + 1));
}
}
bool SELECT() {
int val = 0;
FOR(i, 0, N) {
if (sml[i]) val += (s[i] == 'A' ? 1 : -1);
else val += (t[i] == 'A' ? 1 : -1);
// cout << (sml[i] ? s[i] : t[i]);
}
// cout << endl;
// cout << val << endl;
// for (auto &[l, r] : tanya) cout << '<' << l << ' ' << r << "> ";
// cout << endl;
for (auto &[l, r] : tanya) {
int now = val, pre = l;
FOR(i, l, r) {
now += (t[i] == 'A' ? -2 : 2);
if (abs(now) < abs(val)) {
// debug(i, now);
FOR(j, pre, i + 1) {
sml[j] = true;
big[j] = false;
}
val = now;
pre = i + 1;
}
}
}
return val == 0;
}
string miku() {
cin >> n;
N = n * 2;
FOR(i, 0, N) cin >> a[i];
FOR(i, 0, N) cin >> b[i];
INIT();
if (!GET_NUM()) return "-1";
// FOR(i, 0, N - 1) cout << p[i] << ' ';
// cout << endl;
if (DIE()) return "-1";
if (!GET_3()) return "-1";
FREE();
if (!SELECT()) return "-1";
FOR(i, 0, N) ans[i] = (sml[i] ? s[i] : t[i]);
return ans;
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(iostream::failbit);
cout << miku() << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6620 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6700 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6620 KB |
Output is correct |
14 |
Correct |
2 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6748 KB |
Output is correct |
16 |
Correct |
2 ms |
6744 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
2 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
2 ms |
6620 KB |
Output is correct |
22 |
Correct |
1 ms |
6624 KB |
Output is correct |
23 |
Correct |
2 ms |
6744 KB |
Output is correct |
24 |
Correct |
2 ms |
6748 KB |
Output is correct |
25 |
Correct |
2 ms |
6748 KB |
Output is correct |
26 |
Correct |
2 ms |
6748 KB |
Output is correct |
27 |
Correct |
1 ms |
6748 KB |
Output is correct |
28 |
Correct |
2 ms |
6748 KB |
Output is correct |
29 |
Correct |
2 ms |
6748 KB |
Output is correct |
30 |
Correct |
1 ms |
6748 KB |
Output is correct |
31 |
Correct |
1 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
2 ms |
7000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
2 ms |
6492 KB |
Output is correct |
3 |
Correct |
1 ms |
6492 KB |
Output is correct |
4 |
Correct |
1 ms |
6492 KB |
Output is correct |
5 |
Correct |
2 ms |
6492 KB |
Output is correct |
6 |
Correct |
2 ms |
6620 KB |
Output is correct |
7 |
Correct |
2 ms |
6748 KB |
Output is correct |
8 |
Correct |
2 ms |
6748 KB |
Output is correct |
9 |
Correct |
2 ms |
6748 KB |
Output is correct |
10 |
Correct |
2 ms |
6748 KB |
Output is correct |
11 |
Correct |
2 ms |
6700 KB |
Output is correct |
12 |
Correct |
2 ms |
6748 KB |
Output is correct |
13 |
Correct |
2 ms |
6620 KB |
Output is correct |
14 |
Correct |
2 ms |
6748 KB |
Output is correct |
15 |
Correct |
2 ms |
6748 KB |
Output is correct |
16 |
Correct |
2 ms |
6744 KB |
Output is correct |
17 |
Correct |
2 ms |
6748 KB |
Output is correct |
18 |
Correct |
2 ms |
6748 KB |
Output is correct |
19 |
Correct |
2 ms |
6748 KB |
Output is correct |
20 |
Correct |
2 ms |
6748 KB |
Output is correct |
21 |
Correct |
2 ms |
6620 KB |
Output is correct |
22 |
Correct |
1 ms |
6624 KB |
Output is correct |
23 |
Correct |
2 ms |
6744 KB |
Output is correct |
24 |
Correct |
2 ms |
6748 KB |
Output is correct |
25 |
Correct |
2 ms |
6748 KB |
Output is correct |
26 |
Correct |
2 ms |
6748 KB |
Output is correct |
27 |
Correct |
1 ms |
6748 KB |
Output is correct |
28 |
Correct |
2 ms |
6748 KB |
Output is correct |
29 |
Correct |
2 ms |
6748 KB |
Output is correct |
30 |
Correct |
1 ms |
6748 KB |
Output is correct |
31 |
Correct |
1 ms |
6748 KB |
Output is correct |
32 |
Correct |
2 ms |
6748 KB |
Output is correct |
33 |
Correct |
2 ms |
7000 KB |
Output is correct |
34 |
Correct |
159 ms |
33996 KB |
Output is correct |
35 |
Correct |
168 ms |
34760 KB |
Output is correct |
36 |
Correct |
160 ms |
34136 KB |
Output is correct |
37 |
Correct |
186 ms |
34896 KB |
Output is correct |
38 |
Correct |
173 ms |
42072 KB |
Output is correct |
39 |
Correct |
150 ms |
35612 KB |
Output is correct |
40 |
Correct |
162 ms |
38540 KB |
Output is correct |
41 |
Correct |
145 ms |
34640 KB |
Output is correct |
42 |
Correct |
155 ms |
35668 KB |
Output is correct |
43 |
Correct |
175 ms |
36588 KB |
Output is correct |
44 |
Correct |
175 ms |
36684 KB |
Output is correct |
45 |
Correct |
176 ms |
37200 KB |
Output is correct |
46 |
Correct |
170 ms |
44340 KB |
Output is correct |
47 |
Correct |
168 ms |
37848 KB |
Output is correct |
48 |
Correct |
160 ms |
37608 KB |
Output is correct |
49 |
Correct |
165 ms |
40140 KB |
Output is correct |
50 |
Correct |
184 ms |
36044 KB |
Output is correct |
51 |
Correct |
177 ms |
35920 KB |
Output is correct |
52 |
Correct |
120 ms |
24920 KB |
Output is correct |
53 |
Correct |
120 ms |
25048 KB |
Output is correct |
54 |
Correct |
112 ms |
32708 KB |
Output is correct |
55 |
Correct |
116 ms |
32952 KB |
Output is correct |
56 |
Correct |
165 ms |
37340 KB |
Output is correct |
57 |
Correct |
142 ms |
31656 KB |
Output is correct |
58 |
Correct |
142 ms |
31828 KB |
Output is correct |
59 |
Correct |
141 ms |
31944 KB |
Output is correct |
60 |
Correct |
134 ms |
30912 KB |
Output is correct |
61 |
Correct |
159 ms |
32500 KB |
Output is correct |
62 |
Correct |
137 ms |
32080 KB |
Output is correct |
63 |
Correct |
142 ms |
32336 KB |
Output is correct |
64 |
Correct |
141 ms |
31568 KB |
Output is correct |
65 |
Correct |
146 ms |
32836 KB |
Output is correct |