# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
335216 | 2020-12-11T14:36:47 Z | CaroLinda | 건물 4 (JOI20_building4) | C++14 | 403 ms | 48236 KB |
#include <bits/stdc++.h> const int MAXN = 1e6+10 ; const int inf = 1e9+7 ; using namespace std; int N ; int dpMin[MAXN][2], dpMax[MAXN][2] ; int main() { scanf("%d", &N ) ; N <<= 1 ; vector<int> A(N) , B(N) ; for(int i = 0 ; i < N ; i++ ) scanf("%d", &A[i] ) ; for(int i = 0 ; i < N ; i++ ) scanf("%d", &B[i] ) ; dpMin[0][0] = dpMax[0][0] = 1 ; dpMin[0][1] = dpMax[0][1] = 0 ; for(int i = 1 ; i < N ; i++ ) { dpMin[i][0] = dpMin[i][1] = MAXN ; dpMax[i][0] = dpMax[i][1] = -1 ; //Testing if I'll put an A if( A[i] >= A[i-1] ) { dpMin[i][0] = dpMin[i-1][0] + 1 ; dpMax[i][0] = dpMax[i-1][0] + 1 ; } if( A[i] >= B[i-1] ) { dpMin[i][0] = min( dpMin[i][0] , 1 + dpMin[i-1][1] ) ; dpMax[i][0] = max( dpMax[i][0] , 1 + dpMax[i-1][1] ) ; } //Testing if I'll put a B if( B[i] >= A[i-1] ) { dpMin[i][1] = dpMin[i-1][0] ; dpMax[i][1] = dpMax[i-1][0] ; } if( B[i] >= B[i-1] ) { dpMin[i][1] = min(dpMin[i][1] , dpMin[i-1][1] ) ; dpMax[i][1] = max(dpMax[i][1] , dpMax[i-1][1] ) ; } } vector<int> ans(N) ; int aLeft = N>>1 ; for(int i = N-1 , toPut = -1 , afterMe = inf ; i >= 0 ; i--, toPut = -1 ) { if( A[i] <= afterMe && dpMin[i][0] <= aLeft && aLeft <= dpMax[i][0] ) toPut = 0 ; if( B[i] <= afterMe && dpMin[i][1] <= aLeft && aLeft <= dpMax[i][1] ) toPut = 1 ; if(toPut == -1 ) { printf("-1\n") ; return 0 ; } aLeft -= ( toPut == 0 ) ; afterMe = ( toPut == 0 ) ? A[i] : B[i] ; ans[i] = toPut ; } for(int i = 0 ; i < N ; i++ ) printf("%c", ( ans[i] == 0 ) ? 'A' : 'B' ) ; printf("\n") ; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 2 ms | 492 KB | Output is correct |
6 | Correct | 2 ms | 492 KB | Output is correct |
7 | Correct | 2 ms | 492 KB | Output is correct |
8 | Correct | 2 ms | 492 KB | Output is correct |
9 | Correct | 2 ms | 492 KB | Output is correct |
10 | Correct | 2 ms | 492 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 2 ms | 492 KB | Output is correct |
14 | Correct | 2 ms | 492 KB | Output is correct |
15 | Correct | 2 ms | 492 KB | Output is correct |
16 | Correct | 2 ms | 492 KB | Output is correct |
17 | Correct | 2 ms | 492 KB | Output is correct |
18 | Correct | 2 ms | 492 KB | Output is correct |
19 | Correct | 2 ms | 492 KB | Output is correct |
20 | Correct | 2 ms | 492 KB | Output is correct |
21 | Correct | 2 ms | 492 KB | Output is correct |
22 | Correct | 2 ms | 492 KB | Output is correct |
23 | Correct | 2 ms | 492 KB | Output is correct |
24 | Correct | 2 ms | 492 KB | Output is correct |
25 | Correct | 2 ms | 492 KB | Output is correct |
26 | Correct | 2 ms | 492 KB | Output is correct |
27 | Correct | 2 ms | 492 KB | Output is correct |
28 | Correct | 2 ms | 492 KB | Output is correct |
29 | Correct | 2 ms | 492 KB | Output is correct |
30 | Correct | 2 ms | 492 KB | Output is correct |
31 | Correct | 2 ms | 492 KB | Output is correct |
32 | Correct | 2 ms | 492 KB | Output is correct |
33 | Correct | 2 ms | 492 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 364 KB | Output is correct |
2 | Correct | 0 ms | 364 KB | Output is correct |
3 | Correct | 0 ms | 364 KB | Output is correct |
4 | Correct | 0 ms | 364 KB | Output is correct |
5 | Correct | 2 ms | 492 KB | Output is correct |
6 | Correct | 2 ms | 492 KB | Output is correct |
7 | Correct | 2 ms | 492 KB | Output is correct |
8 | Correct | 2 ms | 492 KB | Output is correct |
9 | Correct | 2 ms | 492 KB | Output is correct |
10 | Correct | 2 ms | 492 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 2 ms | 492 KB | Output is correct |
13 | Correct | 2 ms | 492 KB | Output is correct |
14 | Correct | 2 ms | 492 KB | Output is correct |
15 | Correct | 2 ms | 492 KB | Output is correct |
16 | Correct | 2 ms | 492 KB | Output is correct |
17 | Correct | 2 ms | 492 KB | Output is correct |
18 | Correct | 2 ms | 492 KB | Output is correct |
19 | Correct | 2 ms | 492 KB | Output is correct |
20 | Correct | 2 ms | 492 KB | Output is correct |
21 | Correct | 2 ms | 492 KB | Output is correct |
22 | Correct | 2 ms | 492 KB | Output is correct |
23 | Correct | 2 ms | 492 KB | Output is correct |
24 | Correct | 2 ms | 492 KB | Output is correct |
25 | Correct | 2 ms | 492 KB | Output is correct |
26 | Correct | 2 ms | 492 KB | Output is correct |
27 | Correct | 2 ms | 492 KB | Output is correct |
28 | Correct | 2 ms | 492 KB | Output is correct |
29 | Correct | 2 ms | 492 KB | Output is correct |
30 | Correct | 2 ms | 492 KB | Output is correct |
31 | Correct | 2 ms | 492 KB | Output is correct |
32 | Correct | 2 ms | 492 KB | Output is correct |
33 | Correct | 2 ms | 492 KB | Output is correct |
34 | Correct | 330 ms | 46316 KB | Output is correct |
35 | Correct | 370 ms | 44780 KB | Output is correct |
36 | Correct | 366 ms | 43884 KB | Output is correct |
37 | Correct | 371 ms | 44904 KB | Output is correct |
38 | Correct | 358 ms | 44780 KB | Output is correct |
39 | Correct | 353 ms | 44012 KB | Output is correct |
40 | Correct | 375 ms | 47724 KB | Output is correct |
41 | Correct | 350 ms | 45036 KB | Output is correct |
42 | Correct | 391 ms | 46444 KB | Output is correct |
43 | Correct | 396 ms | 48108 KB | Output is correct |
44 | Correct | 398 ms | 48104 KB | Output is correct |
45 | Correct | 403 ms | 48108 KB | Output is correct |
46 | Correct | 383 ms | 48236 KB | Output is correct |
47 | Correct | 380 ms | 47212 KB | Output is correct |
48 | Correct | 373 ms | 47084 KB | Output is correct |
49 | Correct | 386 ms | 47908 KB | Output is correct |
50 | Correct | 394 ms | 47212 KB | Output is correct |
51 | Correct | 400 ms | 47356 KB | Output is correct |
52 | Correct | 313 ms | 36332 KB | Output is correct |
53 | Correct | 309 ms | 36460 KB | Output is correct |
54 | Correct | 301 ms | 36588 KB | Output is correct |
55 | Correct | 331 ms | 36204 KB | Output is correct |
56 | Correct | 387 ms | 48236 KB | Output is correct |
57 | Correct | 343 ms | 43116 KB | Output is correct |
58 | Correct | 341 ms | 43244 KB | Output is correct |
59 | Correct | 346 ms | 43244 KB | Output is correct |
60 | Correct | 327 ms | 41068 KB | Output is correct |
61 | Correct | 348 ms | 43884 KB | Output is correct |
62 | Correct | 350 ms | 43372 KB | Output is correct |
63 | Correct | 347 ms | 44012 KB | Output is correct |
64 | Correct | 333 ms | 42476 KB | Output is correct |
65 | Correct | 346 ms | 43884 KB | Output is correct |