#include <iostream>
#include <cstdio>
#include <vector>
//maksimumi i minimumi su rastuci
// a +1 b -1
using namespace std;
#define ss second
#define ff first
#define mp make_pair
#define pb push_back
#define ll long long
const int N = 1e6+11;
int n;
int a[N], b[N];
int res;
vector <int> v[N];
vector <int> s1[N];
vector <int> s2[N];
vector <int> koji1[N];
vector <int> koji2[N];
int mali[N];
int veliki[N];
int br;
int uzeo[N];
int sol[N];
void ne() {
cout << -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i=0;i<2*n;i++) {
cin >> a[i];
}
for (int i=0;i<2*n;i++) {
cin >> b[i];
}
int mini = min(a[0], b[0]);
for (int i=1;i<2*n;i++) {
if (a[i] < mini && b[i] < mini) {
ne();
return 0;
}
if (a[i] < mini) {
a[i] = -1;
mini = b[i];
}
else if (b[i] < mini) {
b[i] = -1;
mini = a[i];
}
else {
mini = min(a[i], b[i]);
}
}
int maksi = max(a[2*n-1], b[2*n-1]);
for (int i=2*n-2; i >= 0; i--) {
if (a[i] > maksi && b[i] > maksi) {
ne();
return 0;
}
if (a[i] > maksi) {
a[i] = -1;
maksi = b[i];
}
else if (b[i] > maksi) {
b[i] = -1;
maksi = a[i];
}
else {
maksi = max(a[i], b[i]);
}
if (a[i] == -1 && b[i] == -1) {
ne();
return 0;
}
}
int a1 = 1e9+1, b1 = 1e9+1;
for (int i=0;i<2*n;i++) {
if (a[i] == -1) res -= 1;
else if (b[i] == -1) res += 1;
else {
if (a1 <= a[i] && a1 <= b[i] && b1 <= a[i] && b1 <= b[i]) {
br++;
v[br].pb(i);
a1 = a[i];
b1 = b[i];
}
else {
v[br].pb(i);
a1 = a[i];
b1 = b[i];
}
}
}
br++;
for (int i=0;i<br;i++) {
int siz = v[i].size();
for (int j=0;j<siz;j++) {
int x = v[i][j];
if (a[x] < b[x]) {
s1[i].pb(1);
koji1[i].pb(1);
s2[i].pb(-1);
koji2[i].pb(-1);
}
else {
s1[i].pb(-1);
koji1[i].pb(-1);
s2[i].pb(1);
koji2[i].pb(1);
}
}
for (int j=1;j<siz;j++) {
s1[i][j] += s1[i][j-1];
}
for (int j=siz-2;j>=0;j--) {
s2[i][j] += s2[i][j+1];
}
int manji, veci;
veci = max(s2[i][0], s1[i][siz-1]);
manji = min(s2[i][0], s1[i][siz-1]);
for (int j=1;j<siz;j++) {
int sada = s2[i][j] + s1[i][j-1];
veci = max(sada, veci);
manji = min(sada, manji);
}
mali[i] = manji;
veliki[i] = veci;
uzeo[i] = manji;
res += manji;
}
if (res % 2 == 1 || res > 0) {
ne();
return 0;
}
for (int i=0;i<br;i++) {
int uzmi = veliki[i] - mali[i];
uzmi = min(uzmi, -res);
uzeo[i] = mali[i] + uzmi;
res += uzmi;
}
if (res != 0) {
ne();
return 0;
}
for (int i=0;i<br;i++) {
int siz = v[i].size();
int c = uzeo[i];
if (s1[i][siz-1] == c) {
for (int j=0;j<siz;j++) {
sol[v[i][j]] = koji1[i][j];
}
continue;
}
if (s2[i][0] == c) {
for (int j=0;j<siz;j++) {
sol[v[i][j]] = koji2[i][j];
}
continue;
}
for (int j=1;j<siz;j++) {
if (s2[i][j] + s1[i][j-1] == c) {
for (int k=0;k<j;k++) {
sol[v[i][k]] = koji1[i][k];
}
for (int k=j;k<siz;k++) {
sol[v[i][k]] = koji2[i][k];
}
break;
}
}
}
for (int i=0;i<2*n;i++) {
if (a[i] == -1) cout << "B";
else if (b[i] == -1) cout << "A";
else if (sol[i] == -1) cout << "B";
else if (sol[i] == 1) cout << "A";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
117752 KB |
Output is correct |
2 |
Correct |
76 ms |
117752 KB |
Output is correct |
3 |
Correct |
73 ms |
117752 KB |
Output is correct |
4 |
Correct |
72 ms |
117752 KB |
Output is correct |
5 |
Correct |
70 ms |
117884 KB |
Output is correct |
6 |
Correct |
70 ms |
118008 KB |
Output is correct |
7 |
Correct |
68 ms |
117880 KB |
Output is correct |
8 |
Correct |
66 ms |
118392 KB |
Output is correct |
9 |
Correct |
68 ms |
118008 KB |
Output is correct |
10 |
Correct |
68 ms |
118136 KB |
Output is correct |
11 |
Correct |
70 ms |
117880 KB |
Output is correct |
12 |
Correct |
70 ms |
117880 KB |
Output is correct |
13 |
Correct |
67 ms |
117880 KB |
Output is correct |
14 |
Correct |
69 ms |
118520 KB |
Output is correct |
15 |
Correct |
69 ms |
118008 KB |
Output is correct |
16 |
Correct |
68 ms |
118008 KB |
Output is correct |
17 |
Correct |
67 ms |
118008 KB |
Output is correct |
18 |
Correct |
67 ms |
117880 KB |
Output is correct |
19 |
Correct |
70 ms |
117880 KB |
Output is correct |
20 |
Correct |
71 ms |
118008 KB |
Output is correct |
21 |
Correct |
68 ms |
117880 KB |
Output is correct |
22 |
Correct |
69 ms |
118520 KB |
Output is correct |
23 |
Correct |
71 ms |
118392 KB |
Output is correct |
24 |
Correct |
68 ms |
118008 KB |
Output is correct |
25 |
Correct |
68 ms |
117880 KB |
Output is correct |
26 |
Correct |
69 ms |
118008 KB |
Output is correct |
27 |
Correct |
67 ms |
118008 KB |
Output is correct |
28 |
Correct |
67 ms |
117880 KB |
Output is correct |
29 |
Correct |
67 ms |
118008 KB |
Output is correct |
30 |
Correct |
68 ms |
117884 KB |
Output is correct |
31 |
Correct |
68 ms |
118008 KB |
Output is correct |
32 |
Correct |
68 ms |
117880 KB |
Output is correct |
33 |
Correct |
69 ms |
117948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
66 ms |
117752 KB |
Output is correct |
2 |
Correct |
76 ms |
117752 KB |
Output is correct |
3 |
Correct |
73 ms |
117752 KB |
Output is correct |
4 |
Correct |
72 ms |
117752 KB |
Output is correct |
5 |
Correct |
70 ms |
117884 KB |
Output is correct |
6 |
Correct |
70 ms |
118008 KB |
Output is correct |
7 |
Correct |
68 ms |
117880 KB |
Output is correct |
8 |
Correct |
66 ms |
118392 KB |
Output is correct |
9 |
Correct |
68 ms |
118008 KB |
Output is correct |
10 |
Correct |
68 ms |
118136 KB |
Output is correct |
11 |
Correct |
70 ms |
117880 KB |
Output is correct |
12 |
Correct |
70 ms |
117880 KB |
Output is correct |
13 |
Correct |
67 ms |
117880 KB |
Output is correct |
14 |
Correct |
69 ms |
118520 KB |
Output is correct |
15 |
Correct |
69 ms |
118008 KB |
Output is correct |
16 |
Correct |
68 ms |
118008 KB |
Output is correct |
17 |
Correct |
67 ms |
118008 KB |
Output is correct |
18 |
Correct |
67 ms |
117880 KB |
Output is correct |
19 |
Correct |
70 ms |
117880 KB |
Output is correct |
20 |
Correct |
71 ms |
118008 KB |
Output is correct |
21 |
Correct |
68 ms |
117880 KB |
Output is correct |
22 |
Correct |
69 ms |
118520 KB |
Output is correct |
23 |
Correct |
71 ms |
118392 KB |
Output is correct |
24 |
Correct |
68 ms |
118008 KB |
Output is correct |
25 |
Correct |
68 ms |
117880 KB |
Output is correct |
26 |
Correct |
69 ms |
118008 KB |
Output is correct |
27 |
Correct |
67 ms |
118008 KB |
Output is correct |
28 |
Correct |
67 ms |
117880 KB |
Output is correct |
29 |
Correct |
67 ms |
118008 KB |
Output is correct |
30 |
Correct |
68 ms |
117884 KB |
Output is correct |
31 |
Correct |
68 ms |
118008 KB |
Output is correct |
32 |
Correct |
68 ms |
117880 KB |
Output is correct |
33 |
Correct |
69 ms |
117948 KB |
Output is correct |
34 |
Correct |
349 ms |
144596 KB |
Output is correct |
35 |
Correct |
361 ms |
135032 KB |
Output is correct |
36 |
Correct |
358 ms |
136184 KB |
Output is correct |
37 |
Correct |
368 ms |
132372 KB |
Output is correct |
38 |
Correct |
702 ms |
291448 KB |
Output is correct |
39 |
Correct |
570 ms |
186360 KB |
Output is correct |
40 |
Correct |
589 ms |
185208 KB |
Output is correct |
41 |
Correct |
420 ms |
163908 KB |
Output is correct |
42 |
Correct |
384 ms |
128248 KB |
Output is correct |
43 |
Correct |
400 ms |
128632 KB |
Output is correct |
44 |
Correct |
414 ms |
128384 KB |
Output is correct |
45 |
Correct |
397 ms |
128504 KB |
Output is correct |
46 |
Correct |
740 ms |
300588 KB |
Output is correct |
47 |
Correct |
588 ms |
174584 KB |
Output is correct |
48 |
Correct |
583 ms |
174764 KB |
Output is correct |
49 |
Correct |
607 ms |
185336 KB |
Output is correct |
50 |
Correct |
404 ms |
128632 KB |
Output is correct |
51 |
Correct |
390 ms |
128376 KB |
Output is correct |
52 |
Correct |
275 ms |
136952 KB |
Output is correct |
53 |
Correct |
263 ms |
136824 KB |
Output is correct |
54 |
Correct |
618 ms |
304760 KB |
Output is correct |
55 |
Correct |
525 ms |
264088 KB |
Output is correct |
56 |
Correct |
424 ms |
156892 KB |
Output is correct |
57 |
Correct |
370 ms |
154088 KB |
Output is correct |
58 |
Correct |
371 ms |
154260 KB |
Output is correct |
59 |
Correct |
401 ms |
169176 KB |
Output is correct |
60 |
Correct |
341 ms |
153720 KB |
Output is correct |
61 |
Correct |
372 ms |
156284 KB |
Output is correct |
62 |
Correct |
372 ms |
156272 KB |
Output is correct |
63 |
Correct |
379 ms |
156920 KB |
Output is correct |
64 |
Correct |
374 ms |
155336 KB |
Output is correct |
65 |
Correct |
386 ms |
156664 KB |
Output is correct |