#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define endl '\n'
#define pb push_back
using pi = array<int, 2>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
/*
iau mereu cel mai mic posibil si dau switch
daca v[i][min] <= v[i + 1][min] si v[i][max] >= v[i + 1][min] si v[i][max] <= v[i + 1][max] atunci daca schimb i, schimb si i+1
pot sa iau sufix la cel mai mare interval
sufixul e un interval de valori (se schimba cu 1 costul)
v[i][0] = minimu
v[i][1] = maximu
balance = A - B
*/
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
n *= 2;
vector<bool> swappedv(n + 1), is_max(n + 1);
vector<int> cost(n + 1);
vector<vector<int>> v(n + 1, vector<int>(2));
for (int i = 1; i <= n; ++i) cin >> v[i][0];
for (int i = 1; i <= n; ++i) cin >> v[i][1];
bool ok = true;
int balance = 0, lastc = 0;
for (int i = 1; i <= n; ++i) {
if (v[i][0] <= v[i][1]) {
if (v[i][0] >= lastc) {
balance += 1;
cost[i] = -1;
lastc = v[i][0];
} else {
ok &= (v[i][1] >= lastc);
balance -= 1;
cost[i] = 0;
is_max[i] = true;
lastc = v[i][1];
}
} else {
swappedv[i] = true;
swap(v[i][0], v[i][1]);
if (v[i][0] >= lastc) {
balance -= 1;
cost[i] = 1;
lastc = v[i][0];
} else {
ok &= (v[i][1] >= lastc);
balance += 1;
cost[i] = 0;
is_max[i] = true;
lastc = v[i][1];
}
}
}
if (!ok) {
cout << "-1";
return 0;
}
balance /= 2;
vector<pi> segments;
int st = 1;
for (int dr = 1; dr < n; ++dr) {
if (cost[dr] == 0) { // sunt deja max
segments.pb({st, dr});
st = dr + 1;
continue;
}
if (v[dr][1] > v[dr + 1][1]) { // nu pot da swap la asta, segmentul e invalidat
st = dr + 1;
continue;
}
if (v[dr][1] > v[dr + 1][0]) continue; // trebuie sa dau swap si la urmatorul
// segmentul se termina aici
segments.pb({st, dr});
st = dr + 1;
}
segments.pb({st, n});
/*cout << endl << endl;
for (int i = 1; i <= n; ++i) cout << is_max[i] << " ";*/
/*cout << endl << endl << balance << endl;
for (pi s : segments) {
cout << s[0] << " " << s[1] << " | ";
for (int i = s[0]; i <= s[1]; ++i) cout << cost[i] << " ";
cout << endl;
}
cout << endl;*/
for (pi s : segments) {
int l = s[0], r = s[1];
int suf = 0;
if (balance < 0) {
int maxi = 0, maxidx = r + 1;
for (int i = r; i >= l; --i) {
suf += cost[i];
if (balance + suf <= 0 && suf > maxi) {
maxi = suf;
maxidx = i;
}
}
for (int i = r; i >= maxidx; --i) is_max[i] = true;
balance += maxi;
} else if (balance > 0) {
int mini = 0, minidx = r + 1;
for (int i = r; i >= l; --i) {
suf += cost[i];
if (balance + suf >= 0 && suf < mini) {
mini = suf;
minidx = i;
}
}
for (int i = r; i >= minidx; --i) is_max[i] = true;
balance += mini;
}
}
if (balance != 0) {
cout << "-1";
return 0;
}
for (int i = 1; i <= n; ++i) {
bool is_a = true;
if (swappedv[i]) is_a = !is_a;
if (is_max[i]) is_a = !is_a;
cout << (is_a ? 'A' : 'B');
}
}
/*
2
42 14 97 89
30 68 69 53
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
764 KB |
Output is correct |
12 |
Correct |
2 ms |
784 KB |
Output is correct |
13 |
Correct |
2 ms |
600 KB |
Output is correct |
14 |
Correct |
2 ms |
860 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
752 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
2 ms |
784 KB |
Output is correct |
20 |
Correct |
2 ms |
600 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
1 ms |
860 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
720 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
600 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
2 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
604 KB |
Output is correct |
6 |
Correct |
1 ms |
604 KB |
Output is correct |
7 |
Correct |
1 ms |
604 KB |
Output is correct |
8 |
Correct |
1 ms |
604 KB |
Output is correct |
9 |
Correct |
1 ms |
604 KB |
Output is correct |
10 |
Correct |
1 ms |
604 KB |
Output is correct |
11 |
Correct |
1 ms |
764 KB |
Output is correct |
12 |
Correct |
2 ms |
784 KB |
Output is correct |
13 |
Correct |
2 ms |
600 KB |
Output is correct |
14 |
Correct |
2 ms |
860 KB |
Output is correct |
15 |
Correct |
1 ms |
604 KB |
Output is correct |
16 |
Correct |
1 ms |
752 KB |
Output is correct |
17 |
Correct |
1 ms |
604 KB |
Output is correct |
18 |
Correct |
1 ms |
600 KB |
Output is correct |
19 |
Correct |
2 ms |
784 KB |
Output is correct |
20 |
Correct |
2 ms |
600 KB |
Output is correct |
21 |
Correct |
1 ms |
604 KB |
Output is correct |
22 |
Correct |
1 ms |
860 KB |
Output is correct |
23 |
Correct |
1 ms |
860 KB |
Output is correct |
24 |
Correct |
1 ms |
604 KB |
Output is correct |
25 |
Correct |
1 ms |
604 KB |
Output is correct |
26 |
Correct |
1 ms |
720 KB |
Output is correct |
27 |
Correct |
1 ms |
600 KB |
Output is correct |
28 |
Correct |
1 ms |
604 KB |
Output is correct |
29 |
Correct |
1 ms |
604 KB |
Output is correct |
30 |
Correct |
1 ms |
600 KB |
Output is correct |
31 |
Correct |
1 ms |
604 KB |
Output is correct |
32 |
Correct |
1 ms |
604 KB |
Output is correct |
33 |
Correct |
2 ms |
604 KB |
Output is correct |
34 |
Correct |
212 ms |
81092 KB |
Output is correct |
35 |
Correct |
222 ms |
85828 KB |
Output is correct |
36 |
Correct |
256 ms |
84368 KB |
Output is correct |
37 |
Correct |
223 ms |
85700 KB |
Output is correct |
38 |
Correct |
230 ms |
94144 KB |
Output is correct |
39 |
Correct |
223 ms |
81404 KB |
Output is correct |
40 |
Correct |
224 ms |
92100 KB |
Output is correct |
41 |
Correct |
218 ms |
78776 KB |
Output is correct |
42 |
Correct |
229 ms |
80912 KB |
Output is correct |
43 |
Correct |
249 ms |
91832 KB |
Output is correct |
44 |
Correct |
260 ms |
92212 KB |
Output is correct |
45 |
Correct |
269 ms |
91436 KB |
Output is correct |
46 |
Correct |
246 ms |
99888 KB |
Output is correct |
47 |
Correct |
238 ms |
88004 KB |
Output is correct |
48 |
Correct |
234 ms |
86468 KB |
Output is correct |
49 |
Correct |
246 ms |
92588 KB |
Output is correct |
50 |
Correct |
244 ms |
90932 KB |
Output is correct |
51 |
Correct |
248 ms |
91580 KB |
Output is correct |
52 |
Correct |
220 ms |
79916 KB |
Output is correct |
53 |
Correct |
187 ms |
80640 KB |
Output is correct |
54 |
Correct |
190 ms |
88752 KB |
Output is correct |
55 |
Correct |
190 ms |
88380 KB |
Output is correct |
56 |
Correct |
235 ms |
83784 KB |
Output is correct |
57 |
Correct |
230 ms |
78420 KB |
Output is correct |
58 |
Correct |
203 ms |
78676 KB |
Output is correct |
59 |
Correct |
222 ms |
78792 KB |
Output is correct |
60 |
Correct |
222 ms |
74344 KB |
Output is correct |
61 |
Correct |
209 ms |
79152 KB |
Output is correct |
62 |
Correct |
210 ms |
78120 KB |
Output is correct |
63 |
Correct |
225 ms |
79136 KB |
Output is correct |
64 |
Correct |
195 ms |
76368 KB |
Output is correct |
65 |
Correct |
208 ms |
79184 KB |
Output is correct |