#include <iostream>
using namespace std;
/*
Let us sort all the 4N coloring plans together, first by height then by building index.
Out of this sequence, we have to choose 2N elements such that:
No two coloring plans for a single building are chosen.
*/
int main()
{
int N;
cin >> N;
int A[2*N + 1];
int B[2*N + 1];
for(int i = 1; i <= 2*N; i++) cin >> A[i];
for(int i = 1; i <= 2*N; i++) cin >> B[i];
A[0] = B[0] = 0;
int lo[2*N + 1][2], hi[2*N + 1][2]; //lower & upper limits on number of A buildings.
lo[0][0] = hi[0][0] = 0;
lo[0][1] = hi[0][1] = 0;
for(int i = 1; i <= 2*N; i++)
{
lo[i][0] = lo[i][1] = 1e9;
hi[i][0] = hi[i][1] = -1e9;
if(A[i-1] <= A[i])
{
hi[i][0] = max(hi[i][0], hi[i-1][0] + 1);
lo[i][0] = min(lo[i][0], lo[i-1][0] + 1);
}
if(B[i-1] <= A[i])
{
hi[i][0] = max(hi[i][0], hi[i-1][1] + 1);
lo[i][0] = min(lo[i][0], lo[i-1][1] + 1);
}
if(A[i-1] <= B[i])
{
hi[i][1] = max(hi[i][1], hi[i-1][0]);
lo[i][1] = min(lo[i][1], lo[i-1][0]);
}
if(B[i-1] <= B[i])
{
hi[i][1] = max(hi[i][1], hi[i-1][1]);
lo[i][1] = min(lo[i][1], lo[i-1][1]);
}
// cerr << "i = " << i << '\n';
// cerr << lo[i][0] << ' ' << hi[i][0] << " | " << lo[i][1] << ' ' << hi[i][1] << '\n';
}
if(!(lo[2*N][0] <= N && N <= hi[2*N][0]) && !(lo[2*N][1] <= N && N <= hi[2*N][1]))
{
cout << "-1\n";
return 0;
}
string res(2*N, '.');
int i = 2*N;
int lb = (lo[i][1] <= N && N <= hi[i][1]);
int buildA = N;
for(int i = 2*N; i >= 1; i--)
{
if(lb == 0)
{
res[i-1] = 'A';
buildA--;
}
else res[i-1] = 'B';
if(lb == 0)
{
if(A[i-1] <= A[i] && lo[i-1][0] <= buildA && buildA <= hi[i-1][0])
lb = 0;
else
lb = 1;
}
else
{
if(A[i-1] <= B[i] && lo[i-1][0] <= buildA && buildA <= hi[i-1][0])
lb = 0;
else
lb = 1;
}
}
cout << res << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
272 KB |
Output is correct |
5 |
Correct |
5 ms |
324 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
4 ms |
380 KB |
Output is correct |
9 |
Correct |
4 ms |
360 KB |
Output is correct |
10 |
Correct |
4 ms |
296 KB |
Output is correct |
11 |
Correct |
4 ms |
396 KB |
Output is correct |
12 |
Correct |
4 ms |
460 KB |
Output is correct |
13 |
Correct |
4 ms |
460 KB |
Output is correct |
14 |
Correct |
4 ms |
460 KB |
Output is correct |
15 |
Correct |
4 ms |
412 KB |
Output is correct |
16 |
Correct |
5 ms |
460 KB |
Output is correct |
17 |
Correct |
4 ms |
460 KB |
Output is correct |
18 |
Correct |
4 ms |
408 KB |
Output is correct |
19 |
Correct |
4 ms |
368 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
3 ms |
300 KB |
Output is correct |
22 |
Correct |
4 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
352 KB |
Output is correct |
24 |
Correct |
4 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
432 KB |
Output is correct |
26 |
Correct |
3 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
332 KB |
Output is correct |
28 |
Correct |
3 ms |
300 KB |
Output is correct |
29 |
Correct |
3 ms |
436 KB |
Output is correct |
30 |
Correct |
3 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
368 KB |
Output is correct |
32 |
Correct |
3 ms |
300 KB |
Output is correct |
33 |
Correct |
8 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
1 ms |
296 KB |
Output is correct |
3 |
Correct |
1 ms |
204 KB |
Output is correct |
4 |
Correct |
1 ms |
272 KB |
Output is correct |
5 |
Correct |
5 ms |
324 KB |
Output is correct |
6 |
Correct |
4 ms |
332 KB |
Output is correct |
7 |
Correct |
3 ms |
332 KB |
Output is correct |
8 |
Correct |
4 ms |
380 KB |
Output is correct |
9 |
Correct |
4 ms |
360 KB |
Output is correct |
10 |
Correct |
4 ms |
296 KB |
Output is correct |
11 |
Correct |
4 ms |
396 KB |
Output is correct |
12 |
Correct |
4 ms |
460 KB |
Output is correct |
13 |
Correct |
4 ms |
460 KB |
Output is correct |
14 |
Correct |
4 ms |
460 KB |
Output is correct |
15 |
Correct |
4 ms |
412 KB |
Output is correct |
16 |
Correct |
5 ms |
460 KB |
Output is correct |
17 |
Correct |
4 ms |
460 KB |
Output is correct |
18 |
Correct |
4 ms |
408 KB |
Output is correct |
19 |
Correct |
4 ms |
368 KB |
Output is correct |
20 |
Correct |
3 ms |
332 KB |
Output is correct |
21 |
Correct |
3 ms |
300 KB |
Output is correct |
22 |
Correct |
4 ms |
332 KB |
Output is correct |
23 |
Correct |
3 ms |
352 KB |
Output is correct |
24 |
Correct |
4 ms |
460 KB |
Output is correct |
25 |
Correct |
3 ms |
432 KB |
Output is correct |
26 |
Correct |
3 ms |
332 KB |
Output is correct |
27 |
Correct |
3 ms |
332 KB |
Output is correct |
28 |
Correct |
3 ms |
300 KB |
Output is correct |
29 |
Correct |
3 ms |
436 KB |
Output is correct |
30 |
Correct |
3 ms |
332 KB |
Output is correct |
31 |
Correct |
3 ms |
368 KB |
Output is correct |
32 |
Correct |
3 ms |
300 KB |
Output is correct |
33 |
Correct |
8 ms |
300 KB |
Output is correct |
34 |
Correct |
918 ms |
42300 KB |
Output is correct |
35 |
Correct |
839 ms |
41820 KB |
Output is correct |
36 |
Correct |
829 ms |
41224 KB |
Output is correct |
37 |
Correct |
831 ms |
42004 KB |
Output is correct |
38 |
Correct |
917 ms |
41984 KB |
Output is correct |
39 |
Correct |
806 ms |
41144 KB |
Output is correct |
40 |
Correct |
965 ms |
44560 KB |
Output is correct |
41 |
Correct |
855 ms |
42288 KB |
Output is correct |
42 |
Correct |
884 ms |
43628 KB |
Output is correct |
43 |
Correct |
915 ms |
45112 KB |
Output is correct |
44 |
Correct |
1016 ms |
44988 KB |
Output is correct |
45 |
Correct |
957 ms |
45036 KB |
Output is correct |
46 |
Correct |
1058 ms |
45108 KB |
Output is correct |
47 |
Correct |
1050 ms |
44076 KB |
Output is correct |
48 |
Correct |
1016 ms |
43940 KB |
Output is correct |
49 |
Correct |
1012 ms |
44756 KB |
Output is correct |
50 |
Correct |
920 ms |
44200 KB |
Output is correct |
51 |
Correct |
1484 ms |
43992 KB |
Output is correct |
52 |
Correct |
702 ms |
33336 KB |
Output is correct |
53 |
Correct |
625 ms |
33284 KB |
Output is correct |
54 |
Correct |
641 ms |
33348 KB |
Output is correct |
55 |
Correct |
906 ms |
33056 KB |
Output is correct |
56 |
Correct |
1250 ms |
45236 KB |
Output is correct |
57 |
Correct |
1018 ms |
40068 KB |
Output is correct |
58 |
Correct |
965 ms |
40368 KB |
Output is correct |
59 |
Correct |
1030 ms |
40248 KB |
Output is correct |
60 |
Correct |
1332 ms |
38204 KB |
Output is correct |
61 |
Correct |
939 ms |
40768 KB |
Output is correct |
62 |
Correct |
851 ms |
40072 KB |
Output is correct |
63 |
Correct |
877 ms |
40744 KB |
Output is correct |
64 |
Correct |
901 ms |
39328 KB |
Output is correct |
65 |
Correct |
979 ms |
40700 KB |
Output is correct |