// M
#include<bits/stdc++.h>
using namespace std;
const int N = 1000006 * 2;
int n, m, A[N][2], dp[N][2], dp2[N][2], R[N];
pair < int , int > F[N];
int main()
{
scanf("%d", &m); n = m + m;
for (int w = 0; w < 2; w ++)
for (int i = 1; i <= n; i ++)
scanf("%d", &A[i][w]);
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; i ++)
for (int w = 0; w < 2; w ++)
{
if (A[i][w] >= A[i - 1][0])
dp[i][w] |= dp[i - 1][0];
if (A[i][w] >= A[i - 1][1])
dp[i][w] |= dp[i - 1][1];
}
if (!dp[n][0] && !dp[n][1])
return !printf("-1\n");
dp2[n][0] = dp2[n][1] = 1;
for (int i = n - 1; i; i --)
for (int w = 0; w < 2; w ++)
{
if (A[i][w] <= A[i + 1][0])
dp2[i][w] |= dp2[i + 1][0];
if (A[i][w] <= A[i + 1][1])
dp2[i][w] |= dp2[i + 1][1];
}
if (!dp2[1][0] && !dp2[1][1])
return !printf("-1\n");
int Cnt0 = 0;
memset(R, -1, sizeof(R));
for (int i = 1; i <= n; i ++)
{
if ((!dp[i][0] || !dp2[i][0]) && (!dp[i][1] || !dp2[i][1]))
return !printf("-1\n");
assert((dp[i][0] && dp2[i][0]) || (dp[i][1] && dp2[i][1]));
if (!dp[i][0] || !dp2[i][0])
R[i] = 1;
else if (!dp[i][1] || !dp2[i][1])
R[i] = 0, Cnt0 ++;
}
vector < pair < int , int > > vec;
for (int i = 1; i <= n; i ++)
if (R[i] == -1)
{
int r = i + 1;
while (r <= n && R[r] == -1 && max(A[r - 1][0], A[r - 1][1]) > min(A[r][0], A[r][1]))
r ++;
vec.push_back({i, r - 1});
i = r - 1;
}
int TMn = 0, TMx = 0;
for (int j = 0; j < (int)vec.size(); j ++)
{
int l = vec[j].first;
int r = vec[j].second;
int cnt = 0;
for (int i = l; i <= r; i ++)
if (A[i][0] < A[i][1])
cnt ++;
int Mn = cnt, Mx = cnt;
for (int i = r; i >= l; i --)
{
if (A[i][0] < A[i][1])
cnt --;
else
cnt ++;
Mn = min(Mn, cnt);
Mx = max(Mx, cnt);
}
F[j] = {Mn, Mx};
TMn += Mn;
TMx += Mx;
}
if (Cnt0 + TMn > m || Cnt0 + TMx < m)
return !printf("-1\n");
for (int j = 0; j < (int)vec.size(); j ++)
{
assert(Cnt0 + TMn <= m);
TMn -= F[j].first;
int nd = m - Cnt0 - TMn;
nd = min(nd, F[j].second);
assert(nd >= F[j].first);
Cnt0 += nd;
int cnt = 0;
int l = vec[j].first;
int r = vec[j].second;
for (int i = l; i <= r; i ++)
if (A[i][0] < A[i][1])
R[i] = 0, cnt ++;
else
R[i] = 1;
if (cnt == nd)
continue;
for (int i = r; i >= l; i --)
{
if (A[i][0] < A[i][1])
R[i] = 1, cnt --;
else
R[i] = 0, cnt ++;
if (cnt == nd)
break;
}
}
for (int i = 1; i <= n; i ++)
printf(R[i] ? "B" : "A");
printf("\n");
return 0;
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:9:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &m); n = m + m;
~~~~~^~~~~~~~~~
building4.cpp:12:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &A[i][w]);
~~~~~^~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8192 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
8192 KB |
Output is correct |
4 |
Correct |
4 ms |
8192 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
8192 KB |
Output is correct |
7 |
Correct |
6 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8320 KB |
Output is correct |
9 |
Correct |
6 ms |
8320 KB |
Output is correct |
10 |
Correct |
5 ms |
8192 KB |
Output is correct |
11 |
Correct |
6 ms |
8192 KB |
Output is correct |
12 |
Correct |
6 ms |
8320 KB |
Output is correct |
13 |
Correct |
6 ms |
8320 KB |
Output is correct |
14 |
Correct |
7 ms |
8320 KB |
Output is correct |
15 |
Correct |
6 ms |
8320 KB |
Output is correct |
16 |
Correct |
6 ms |
8320 KB |
Output is correct |
17 |
Correct |
6 ms |
8320 KB |
Output is correct |
18 |
Correct |
6 ms |
8320 KB |
Output is correct |
19 |
Correct |
6 ms |
8320 KB |
Output is correct |
20 |
Correct |
6 ms |
8320 KB |
Output is correct |
21 |
Correct |
6 ms |
8320 KB |
Output is correct |
22 |
Correct |
6 ms |
8320 KB |
Output is correct |
23 |
Correct |
6 ms |
8320 KB |
Output is correct |
24 |
Correct |
7 ms |
8320 KB |
Output is correct |
25 |
Correct |
6 ms |
8320 KB |
Output is correct |
26 |
Correct |
6 ms |
8320 KB |
Output is correct |
27 |
Correct |
6 ms |
8320 KB |
Output is correct |
28 |
Correct |
6 ms |
8192 KB |
Output is correct |
29 |
Correct |
6 ms |
8320 KB |
Output is correct |
30 |
Correct |
5 ms |
8320 KB |
Output is correct |
31 |
Correct |
6 ms |
8320 KB |
Output is correct |
32 |
Correct |
6 ms |
8320 KB |
Output is correct |
33 |
Correct |
6 ms |
8320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
8192 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
4 ms |
8192 KB |
Output is correct |
4 |
Correct |
4 ms |
8192 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
6 ms |
8192 KB |
Output is correct |
7 |
Correct |
6 ms |
8192 KB |
Output is correct |
8 |
Correct |
6 ms |
8320 KB |
Output is correct |
9 |
Correct |
6 ms |
8320 KB |
Output is correct |
10 |
Correct |
5 ms |
8192 KB |
Output is correct |
11 |
Correct |
6 ms |
8192 KB |
Output is correct |
12 |
Correct |
6 ms |
8320 KB |
Output is correct |
13 |
Correct |
6 ms |
8320 KB |
Output is correct |
14 |
Correct |
7 ms |
8320 KB |
Output is correct |
15 |
Correct |
6 ms |
8320 KB |
Output is correct |
16 |
Correct |
6 ms |
8320 KB |
Output is correct |
17 |
Correct |
6 ms |
8320 KB |
Output is correct |
18 |
Correct |
6 ms |
8320 KB |
Output is correct |
19 |
Correct |
6 ms |
8320 KB |
Output is correct |
20 |
Correct |
6 ms |
8320 KB |
Output is correct |
21 |
Correct |
6 ms |
8320 KB |
Output is correct |
22 |
Correct |
6 ms |
8320 KB |
Output is correct |
23 |
Correct |
6 ms |
8320 KB |
Output is correct |
24 |
Correct |
7 ms |
8320 KB |
Output is correct |
25 |
Correct |
6 ms |
8320 KB |
Output is correct |
26 |
Correct |
6 ms |
8320 KB |
Output is correct |
27 |
Correct |
6 ms |
8320 KB |
Output is correct |
28 |
Correct |
6 ms |
8192 KB |
Output is correct |
29 |
Correct |
6 ms |
8320 KB |
Output is correct |
30 |
Correct |
5 ms |
8320 KB |
Output is correct |
31 |
Correct |
6 ms |
8320 KB |
Output is correct |
32 |
Correct |
6 ms |
8320 KB |
Output is correct |
33 |
Correct |
6 ms |
8320 KB |
Output is correct |
34 |
Correct |
400 ms |
34896 KB |
Output is correct |
35 |
Correct |
421 ms |
48888 KB |
Output is correct |
36 |
Correct |
404 ms |
48252 KB |
Output is correct |
37 |
Correct |
419 ms |
49016 KB |
Output is correct |
38 |
Correct |
411 ms |
63568 KB |
Output is correct |
39 |
Correct |
378 ms |
52196 KB |
Output is correct |
40 |
Correct |
402 ms |
56152 KB |
Output is correct |
41 |
Correct |
345 ms |
49144 KB |
Output is correct |
42 |
Correct |
406 ms |
50552 KB |
Output is correct |
43 |
Correct |
447 ms |
51960 KB |
Output is correct |
44 |
Correct |
447 ms |
52088 KB |
Output is correct |
45 |
Correct |
459 ms |
52012 KB |
Output is correct |
46 |
Correct |
456 ms |
67920 KB |
Output is correct |
47 |
Correct |
415 ms |
55404 KB |
Output is correct |
48 |
Correct |
392 ms |
55012 KB |
Output is correct |
49 |
Correct |
405 ms |
56280 KB |
Output is correct |
50 |
Correct |
429 ms |
51188 KB |
Output is correct |
51 |
Correct |
430 ms |
51188 KB |
Output is correct |
52 |
Correct |
331 ms |
40328 KB |
Output is correct |
53 |
Correct |
408 ms |
40312 KB |
Output is correct |
54 |
Correct |
320 ms |
55888 KB |
Output is correct |
55 |
Correct |
312 ms |
51976 KB |
Output is correct |
56 |
Correct |
410 ms |
52596 KB |
Output is correct |
57 |
Correct |
401 ms |
47352 KB |
Output is correct |
58 |
Correct |
345 ms |
47384 KB |
Output is correct |
59 |
Correct |
344 ms |
47224 KB |
Output is correct |
60 |
Correct |
342 ms |
45300 KB |
Output is correct |
61 |
Correct |
384 ms |
47812 KB |
Output is correct |
62 |
Correct |
382 ms |
47156 KB |
Output is correct |
63 |
Correct |
351 ms |
47736 KB |
Output is correct |
64 |
Correct |
336 ms |
46328 KB |
Output is correct |
65 |
Correct |
365 ms |
47736 KB |
Output is correct |