#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
const int INF = 1e9;
int N;
int A[1'000'000], B[1'000'000];
// A の数を最大化
int dpA[1'000'000][2];
int solveA(int n, int l){
if(n == 2*N) return 0;
if(n == 0) return max(solveA(1, 0)+1, solveA(1, 1));
if(dpA[n][l] != -1) return dpA[n][l];
int ret = -INF;
if(l == 0){
if(A[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1);
if(A[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1));
}
else{
if(B[n-1] <= A[n]) ret = max(ret, solveA(n+1, 0)+1);
if(B[n-1] <= B[n]) ret = max(ret, solveA(n+1, 1));
}
return dpA[n][l] = ret;
}
// B の数を最大化
int dpB[1'000'000][2];
int solveB(int n, int l){
if(n == 2*N) return 0;
if(n == 0) return max(solveB(1, 0), solveB(1, 1)+1);
if(dpB[n][l] != -1) return dpB[n][l];
int ret = -INF;
if(l == 0){
if(A[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0));
if(A[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1);
}
else{
if(B[n-1] <= A[n]) ret = max(ret, solveB(n+1, 0));
if(B[n-1] <= B[n]) ret = max(ret, solveB(n+1, 1)+1);
}
return dpB[n][l] = ret;
}
void print(int n, int a, int l){
if(l == 0) printf("A");
if(l == 1) printf("B");
if(n == 2*N) return;
if(n == 0){
if(solveA(1, 0) >= N-1 && solveB(1, 0) >= N){
print(n+1, a+1, 0);
return;
}
if(solveA(1, 1) >= N && solveB(1, 1) >= N-1){
print(n+1, a, 1);
return;
}
}
int b = n-a;
if(l == 0){
if(A[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){
print(n+1, a+1, 0);
return;
}
if(A[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){
print(n+1, a, 1);
return;
}
}
else{
if(B[n-1] <= A[n] && solveA(n+1, 0) >= N-a-1 && solveB(n+1, 0) >= N-b){
print(n+1, a+1, 0);
return;
}
if(B[n-1] <= B[n] && solveA(n+1, 1) >= N-a && solveB(n+1, 1) >= N-b-1){
print(n+1, a, 1);
return;
}
}
}
signed main(){
scanf("%d", &N);
rep(i, 2*N) scanf("%d", A+i);
rep(i, 2*N) scanf("%d", B+i);
memset(dpA, -1, sizeof(dpA));
memset(dpB, -1, sizeof(dpB));
if(solveA(0, -1) < N || solveB(0, -1) < N){
printf("-1\n");
return 0;
}
print(0, 0, -1);
printf("\n");
}
Compilation message
building4.cpp: In function 'int main()':
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
| ^
building4.cpp:95:2: note: in expansion of macro 'rep'
95 | rep(i, 2*N) scanf("%d", A+i);
| ^~~
building4.cpp:8:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
8 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
| ^
building4.cpp:96:2: note: in expansion of macro 'rep'
96 | rep(i, 2*N) scanf("%d", B+i);
| ^~~
building4.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &N);
| ~~~~~^~~~~~~~~~
building4.cpp:95:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
95 | rep(i, 2*N) scanf("%d", A+i);
| ~~~~~^~~~~~~~~~~
building4.cpp:96:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
96 | rep(i, 2*N) scanf("%d", B+i);
| ~~~~~^~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
15948 KB |
Output is correct |
2 |
Correct |
7 ms |
15948 KB |
Output is correct |
3 |
Correct |
8 ms |
15948 KB |
Output is correct |
4 |
Correct |
8 ms |
15864 KB |
Output is correct |
5 |
Correct |
9 ms |
16056 KB |
Output is correct |
6 |
Correct |
11 ms |
16228 KB |
Output is correct |
7 |
Correct |
9 ms |
16204 KB |
Output is correct |
8 |
Correct |
10 ms |
16252 KB |
Output is correct |
9 |
Correct |
9 ms |
16204 KB |
Output is correct |
10 |
Correct |
9 ms |
16256 KB |
Output is correct |
11 |
Correct |
11 ms |
16252 KB |
Output is correct |
12 |
Correct |
11 ms |
16328 KB |
Output is correct |
13 |
Correct |
9 ms |
16264 KB |
Output is correct |
14 |
Correct |
9 ms |
16220 KB |
Output is correct |
15 |
Correct |
10 ms |
16200 KB |
Output is correct |
16 |
Correct |
9 ms |
16204 KB |
Output is correct |
17 |
Correct |
9 ms |
16332 KB |
Output is correct |
18 |
Correct |
9 ms |
16260 KB |
Output is correct |
19 |
Correct |
11 ms |
16312 KB |
Output is correct |
20 |
Correct |
12 ms |
16152 KB |
Output is correct |
21 |
Correct |
11 ms |
16236 KB |
Output is correct |
22 |
Correct |
8 ms |
16204 KB |
Output is correct |
23 |
Correct |
9 ms |
16164 KB |
Output is correct |
24 |
Correct |
9 ms |
16268 KB |
Output is correct |
25 |
Correct |
9 ms |
16280 KB |
Output is correct |
26 |
Correct |
9 ms |
16232 KB |
Output is correct |
27 |
Correct |
9 ms |
16280 KB |
Output is correct |
28 |
Correct |
11 ms |
16204 KB |
Output is correct |
29 |
Correct |
10 ms |
16184 KB |
Output is correct |
30 |
Correct |
9 ms |
16204 KB |
Output is correct |
31 |
Correct |
10 ms |
16236 KB |
Output is correct |
32 |
Correct |
10 ms |
16136 KB |
Output is correct |
33 |
Correct |
9 ms |
16164 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
15948 KB |
Output is correct |
2 |
Correct |
7 ms |
15948 KB |
Output is correct |
3 |
Correct |
8 ms |
15948 KB |
Output is correct |
4 |
Correct |
8 ms |
15864 KB |
Output is correct |
5 |
Correct |
9 ms |
16056 KB |
Output is correct |
6 |
Correct |
11 ms |
16228 KB |
Output is correct |
7 |
Correct |
9 ms |
16204 KB |
Output is correct |
8 |
Correct |
10 ms |
16252 KB |
Output is correct |
9 |
Correct |
9 ms |
16204 KB |
Output is correct |
10 |
Correct |
9 ms |
16256 KB |
Output is correct |
11 |
Correct |
11 ms |
16252 KB |
Output is correct |
12 |
Correct |
11 ms |
16328 KB |
Output is correct |
13 |
Correct |
9 ms |
16264 KB |
Output is correct |
14 |
Correct |
9 ms |
16220 KB |
Output is correct |
15 |
Correct |
10 ms |
16200 KB |
Output is correct |
16 |
Correct |
9 ms |
16204 KB |
Output is correct |
17 |
Correct |
9 ms |
16332 KB |
Output is correct |
18 |
Correct |
9 ms |
16260 KB |
Output is correct |
19 |
Correct |
11 ms |
16312 KB |
Output is correct |
20 |
Correct |
12 ms |
16152 KB |
Output is correct |
21 |
Correct |
11 ms |
16236 KB |
Output is correct |
22 |
Correct |
8 ms |
16204 KB |
Output is correct |
23 |
Correct |
9 ms |
16164 KB |
Output is correct |
24 |
Correct |
9 ms |
16268 KB |
Output is correct |
25 |
Correct |
9 ms |
16280 KB |
Output is correct |
26 |
Correct |
9 ms |
16232 KB |
Output is correct |
27 |
Correct |
9 ms |
16280 KB |
Output is correct |
28 |
Correct |
11 ms |
16204 KB |
Output is correct |
29 |
Correct |
10 ms |
16184 KB |
Output is correct |
30 |
Correct |
9 ms |
16204 KB |
Output is correct |
31 |
Correct |
10 ms |
16236 KB |
Output is correct |
32 |
Correct |
10 ms |
16136 KB |
Output is correct |
33 |
Correct |
9 ms |
16164 KB |
Output is correct |
34 |
Correct |
300 ms |
24960 KB |
Output is correct |
35 |
Correct |
438 ms |
83456 KB |
Output is correct |
36 |
Correct |
473 ms |
83984 KB |
Output is correct |
37 |
Correct |
420 ms |
83800 KB |
Output is correct |
38 |
Correct |
407 ms |
83772 KB |
Output is correct |
39 |
Correct |
393 ms |
82904 KB |
Output is correct |
40 |
Correct |
448 ms |
88600 KB |
Output is correct |
41 |
Correct |
523 ms |
86664 KB |
Output is correct |
42 |
Correct |
463 ms |
87944 KB |
Output is correct |
43 |
Correct |
449 ms |
88768 KB |
Output is correct |
44 |
Correct |
562 ms |
88768 KB |
Output is correct |
45 |
Correct |
436 ms |
88900 KB |
Output is correct |
46 |
Correct |
497 ms |
88644 KB |
Output is correct |
47 |
Correct |
487 ms |
88656 KB |
Output is correct |
48 |
Correct |
425 ms |
90248 KB |
Output is correct |
49 |
Correct |
458 ms |
88692 KB |
Output is correct |
50 |
Correct |
480 ms |
88684 KB |
Output is correct |
51 |
Correct |
440 ms |
89656 KB |
Output is correct |
52 |
Correct |
385 ms |
88772 KB |
Output is correct |
53 |
Correct |
371 ms |
88772 KB |
Output is correct |
54 |
Correct |
397 ms |
88696 KB |
Output is correct |
55 |
Correct |
381 ms |
88876 KB |
Output is correct |
56 |
Correct |
467 ms |
88852 KB |
Output is correct |
57 |
Correct |
435 ms |
88524 KB |
Output is correct |
58 |
Correct |
422 ms |
88736 KB |
Output is correct |
59 |
Correct |
442 ms |
88868 KB |
Output is correct |
60 |
Correct |
372 ms |
84540 KB |
Output is correct |
61 |
Correct |
396 ms |
88808 KB |
Output is correct |
62 |
Correct |
394 ms |
87704 KB |
Output is correct |
63 |
Correct |
401 ms |
88876 KB |
Output is correct |
64 |
Correct |
381 ms |
86340 KB |
Output is correct |
65 |
Correct |
391 ms |
88680 KB |
Output is correct |