#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000005;
int n;
int a[maxn];
int b[maxn];
pair<int, int> dpA[maxn];
pair<int, int> dpB[maxn];
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n;
for (int i = 1; i <= 2 * n; ++i)
{
cin >> a[i];
}
for (int i = 1; i <= 2 * n; ++i)
{
cin >> b[i];
}
dpA[1] = make_pair(1, 1);
dpB[1] = make_pair(0, 0);
for (int pos = 2; pos <= 2 * n; ++pos)
{
dpA[pos] = make_pair(-1, -1);
dpB[pos] = make_pair(-1, -1);
if (a[pos] >= a[pos - 1])
{
if (dpA[pos - 1] != make_pair(-1, -1))
{
dpA[pos].first = dpA[pos - 1].first + 1;
dpA[pos].second = dpA[pos - 1].second + 1;
}
}
if (a[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
{
if (dpA[pos] == make_pair(-1, -1))
{
dpA[pos].first = dpB[pos - 1].first + 1;
dpA[pos].second = dpB[pos - 1].second + 1;
}
else
{
dpA[pos].first = min(dpA[pos].first, dpB[pos - 1].first + 1);
dpA[pos].second = max(dpA[pos].second, dpB[pos - 1].second + 1);
}
}
if (b[pos] >= a[pos - 1])
{
if (dpA[pos - 1] != make_pair(-1, -1))
{
dpB[pos] = dpA[pos - 1];
}
}
if (b[pos] >= b[pos - 1] && dpB[pos - 1] != make_pair(-1, -1))
{
if (dpB[pos] == make_pair(-1, -1))
{
dpB[pos] = dpB[pos - 1];
}
else
{
dpB[pos].first = min(dpB[pos].first, dpB[pos - 1].first);
dpB[pos].second = max(dpB[pos].second, dpB[pos - 1].second);
}
}
}
int curr = -1;
//cout << dpA[2 * n].first << " " << dpA[2 * n].second << endl;
//cout << dpB[2 * n].first << " " << dpB[2 * n].second << endl;
if (dpA[2 * n].first <= n && n <= dpA[2 * n].second)
{
curr = 0;
}
if (dpB[2 * n].first <= n && n <= dpB[2 * n].second)
{
curr = 1;
}
if (curr == -1)
{
//cout << "here" << endl;
cout << -1 << endl;
return 0;
}
stack<char> result;
result.push(char(curr + 'A'));
int bound = (curr == 0 ? n - 1 : n);
for (int pos = 2 * n - 1; pos >= 1; --pos)
{
int prv = (curr == 0 ? a[pos + 1] : b[pos + 1]);
curr = -1;
if (bound > 0 && prv >= a[pos] && dpA[pos].first <= bound && bound <= dpA[pos].second)
{
curr = 0;
--bound;
}
else if (prv >= b[pos] && dpB[pos].first <= bound && bound <= dpB[pos].second)
{
curr = 1;
}
if (curr == -1)
{
cout << -1 << endl;
return 0;
}
result.push(char(curr + 'A'));
}
while (!result.empty())
{
cout << result.top();
result.pop();
}
cout << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 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 |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6616 KB |
Output is correct |
9 |
Correct |
2 ms |
6488 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6612 KB |
Output is correct |
14 |
Correct |
2 ms |
6620 KB |
Output is correct |
15 |
Correct |
2 ms |
6520 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6488 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6488 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6492 KB |
Output is correct |
30 |
Correct |
2 ms |
6492 KB |
Output is correct |
31 |
Correct |
2 ms |
6492 KB |
Output is correct |
32 |
Correct |
2 ms |
6624 KB |
Output is correct |
33 |
Correct |
1 ms |
6488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
6492 KB |
Output is correct |
2 |
Correct |
1 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 |
6492 KB |
Output is correct |
7 |
Correct |
1 ms |
6492 KB |
Output is correct |
8 |
Correct |
2 ms |
6616 KB |
Output is correct |
9 |
Correct |
2 ms |
6488 KB |
Output is correct |
10 |
Correct |
2 ms |
6492 KB |
Output is correct |
11 |
Correct |
2 ms |
6492 KB |
Output is correct |
12 |
Correct |
2 ms |
6492 KB |
Output is correct |
13 |
Correct |
2 ms |
6612 KB |
Output is correct |
14 |
Correct |
2 ms |
6620 KB |
Output is correct |
15 |
Correct |
2 ms |
6520 KB |
Output is correct |
16 |
Correct |
1 ms |
6492 KB |
Output is correct |
17 |
Correct |
1 ms |
6492 KB |
Output is correct |
18 |
Correct |
2 ms |
6488 KB |
Output is correct |
19 |
Correct |
2 ms |
6492 KB |
Output is correct |
20 |
Correct |
2 ms |
6492 KB |
Output is correct |
21 |
Correct |
2 ms |
6492 KB |
Output is correct |
22 |
Correct |
2 ms |
6488 KB |
Output is correct |
23 |
Correct |
2 ms |
6488 KB |
Output is correct |
24 |
Correct |
2 ms |
6492 KB |
Output is correct |
25 |
Correct |
1 ms |
6492 KB |
Output is correct |
26 |
Correct |
1 ms |
6492 KB |
Output is correct |
27 |
Correct |
1 ms |
6492 KB |
Output is correct |
28 |
Correct |
1 ms |
6492 KB |
Output is correct |
29 |
Correct |
2 ms |
6492 KB |
Output is correct |
30 |
Correct |
2 ms |
6492 KB |
Output is correct |
31 |
Correct |
2 ms |
6492 KB |
Output is correct |
32 |
Correct |
2 ms |
6624 KB |
Output is correct |
33 |
Correct |
1 ms |
6488 KB |
Output is correct |
34 |
Correct |
164 ms |
37832 KB |
Output is correct |
35 |
Correct |
180 ms |
43336 KB |
Output is correct |
36 |
Correct |
211 ms |
42840 KB |
Output is correct |
37 |
Correct |
184 ms |
43484 KB |
Output is correct |
38 |
Correct |
212 ms |
43348 KB |
Output is correct |
39 |
Correct |
172 ms |
42524 KB |
Output is correct |
40 |
Correct |
202 ms |
44800 KB |
Output is correct |
41 |
Correct |
175 ms |
43120 KB |
Output is correct |
42 |
Correct |
182 ms |
44252 KB |
Output is correct |
43 |
Correct |
215 ms |
45284 KB |
Output is correct |
44 |
Correct |
191 ms |
45216 KB |
Output is correct |
45 |
Correct |
192 ms |
45124 KB |
Output is correct |
46 |
Correct |
182 ms |
45228 KB |
Output is correct |
47 |
Correct |
194 ms |
44336 KB |
Output is correct |
48 |
Correct |
172 ms |
44180 KB |
Output is correct |
49 |
Correct |
174 ms |
44884 KB |
Output is correct |
50 |
Correct |
189 ms |
44340 KB |
Output is correct |
51 |
Correct |
196 ms |
44344 KB |
Output is correct |
52 |
Correct |
135 ms |
33516 KB |
Output is correct |
53 |
Correct |
132 ms |
33360 KB |
Output is correct |
54 |
Correct |
124 ms |
33432 KB |
Output is correct |
55 |
Correct |
123 ms |
33112 KB |
Output is correct |
56 |
Correct |
176 ms |
45464 KB |
Output is correct |
57 |
Correct |
154 ms |
40272 KB |
Output is correct |
58 |
Correct |
151 ms |
40276 KB |
Output is correct |
59 |
Correct |
152 ms |
40532 KB |
Output is correct |
60 |
Correct |
147 ms |
39464 KB |
Output is correct |
61 |
Correct |
154 ms |
40784 KB |
Output is correct |
62 |
Correct |
153 ms |
40448 KB |
Output is correct |
63 |
Correct |
172 ms |
40788 KB |
Output is correct |
64 |
Correct |
151 ms |
39984 KB |
Output is correct |
65 |
Correct |
156 ms |
40896 KB |
Output is correct |