# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
228342 | 2020-04-30T15:50:37 Z | wilwxk | Building 4 (JOI20_building4) | C++14 | 489 ms | 48272 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN = 1e6+5; int h[MAXN][2]; int dp[MAXN][2][2]; int ans[MAXN]; int n; int main() { scanf("%d", &n); for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][0]); for(int i = 1; i <= n*2; i++) scanf("%d", &h[i][1]); for(int i = 1; i <= n*2; i++) { for(int b = 0; b < 2; b++) { dp[i][b][0] = MAXN; dp[i][b][1] = -MAXN; for(int a = 0; a < 2; a++) { if(h[i-1][a] > h[i][b]) continue; dp[i][b][0] = min(dp[i][b][0], dp[i-1][a][0]+b); dp[i][b][1] = max(dp[i][b][1], dp[i-1][a][1]+b); } } // printf("%d > %d %d\n", i, dp[i][0][0], dp[i][0][1]); // printf("%d > %d %d\n", i, dp[i][1][0], dp[i][1][1]); } h[n*2+1][0] = h[n*2+1][1] = 1e9+9; int cnt = 0; int last = 0; for(int i = n*2; i >= 1; i--) { if(h[i][0] <= h[i+1][last]) { if(dp[i][0][0] <= n-cnt && dp[i][0][1] >= n-cnt) { ans[i] = 0; last = 0; continue; } } if(h[i][1] <= h[i+1][last]) { if(dp[i][1][0] <= n-cnt && dp[i][1][1] >= n-cnt) { ans[i] = 1; cnt++; last = 1; continue; } } printf("-1\n"); return 0; } for(int i = 1; i <= n*2; i++) printf("%c", 'A'+ans[i]); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 6 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 6 ms | 384 KB | Output is correct |
8 | Correct | 6 ms | 384 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 6 ms | 384 KB | Output is correct |
11 | Correct | 6 ms | 488 KB | Output is correct |
12 | Correct | 6 ms | 384 KB | Output is correct |
13 | Correct | 6 ms | 512 KB | Output is correct |
14 | Correct | 7 ms | 384 KB | Output is correct |
15 | Correct | 6 ms | 384 KB | Output is correct |
16 | Correct | 6 ms | 384 KB | Output is correct |
17 | Correct | 6 ms | 384 KB | Output is correct |
18 | Correct | 6 ms | 512 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 6 ms | 384 KB | Output is correct |
21 | Correct | 6 ms | 512 KB | Output is correct |
22 | Correct | 6 ms | 512 KB | Output is correct |
23 | Correct | 6 ms | 512 KB | Output is correct |
24 | Correct | 6 ms | 512 KB | Output is correct |
25 | Correct | 6 ms | 384 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 6 ms | 512 KB | Output is correct |
28 | Correct | 6 ms | 512 KB | Output is correct |
29 | Correct | 6 ms | 512 KB | Output is correct |
30 | Correct | 6 ms | 384 KB | Output is correct |
31 | Correct | 6 ms | 384 KB | Output is correct |
32 | Correct | 6 ms | 384 KB | Output is correct |
33 | Correct | 6 ms | 416 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 6 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 6 ms | 384 KB | Output is correct |
8 | Correct | 6 ms | 384 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 6 ms | 384 KB | Output is correct |
11 | Correct | 6 ms | 488 KB | Output is correct |
12 | Correct | 6 ms | 384 KB | Output is correct |
13 | Correct | 6 ms | 512 KB | Output is correct |
14 | Correct | 7 ms | 384 KB | Output is correct |
15 | Correct | 6 ms | 384 KB | Output is correct |
16 | Correct | 6 ms | 384 KB | Output is correct |
17 | Correct | 6 ms | 384 KB | Output is correct |
18 | Correct | 6 ms | 512 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 6 ms | 384 KB | Output is correct |
21 | Correct | 6 ms | 512 KB | Output is correct |
22 | Correct | 6 ms | 512 KB | Output is correct |
23 | Correct | 6 ms | 512 KB | Output is correct |
24 | Correct | 6 ms | 512 KB | Output is correct |
25 | Correct | 6 ms | 384 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 6 ms | 512 KB | Output is correct |
28 | Correct | 6 ms | 512 KB | Output is correct |
29 | Correct | 6 ms | 512 KB | Output is correct |
30 | Correct | 6 ms | 384 KB | Output is correct |
31 | Correct | 6 ms | 384 KB | Output is correct |
32 | Correct | 6 ms | 384 KB | Output is correct |
33 | Correct | 6 ms | 416 KB | Output is correct |
34 | Correct | 434 ms | 37400 KB | Output is correct |
35 | Correct | 462 ms | 44664 KB | Output is correct |
36 | Correct | 435 ms | 43896 KB | Output is correct |
37 | Correct | 437 ms | 44920 KB | Output is correct |
38 | Correct | 417 ms | 44792 KB | Output is correct |
39 | Correct | 409 ms | 44024 KB | Output is correct |
40 | Correct | 425 ms | 47480 KB | Output is correct |
41 | Correct | 371 ms | 45044 KB | Output is correct |
42 | Correct | 449 ms | 46456 KB | Output is correct |
43 | Correct | 476 ms | 48116 KB | Output is correct |
44 | Correct | 489 ms | 48120 KB | Output is correct |
45 | Correct | 465 ms | 48116 KB | Output is correct |
46 | Correct | 428 ms | 47988 KB | Output is correct |
47 | Correct | 423 ms | 47096 KB | Output is correct |
48 | Correct | 411 ms | 46964 KB | Output is correct |
49 | Correct | 420 ms | 47728 KB | Output is correct |
50 | Correct | 470 ms | 47224 KB | Output is correct |
51 | Correct | 455 ms | 47224 KB | Output is correct |
52 | Correct | 319 ms | 36344 KB | Output is correct |
53 | Correct | 330 ms | 36344 KB | Output is correct |
54 | Correct | 307 ms | 36344 KB | Output is correct |
55 | Correct | 297 ms | 36088 KB | Output is correct |
56 | Correct | 409 ms | 48272 KB | Output is correct |
57 | Correct | 364 ms | 43124 KB | Output is correct |
58 | Correct | 362 ms | 43384 KB | Output is correct |
59 | Correct | 367 ms | 43256 KB | Output is correct |
60 | Correct | 355 ms | 41132 KB | Output is correct |
61 | Correct | 383 ms | 43768 KB | Output is correct |
62 | Correct | 371 ms | 43100 KB | Output is correct |
63 | Correct | 379 ms | 43768 KB | Output is correct |
64 | Correct | 376 ms | 42228 KB | Output is correct |
65 | Correct | 375 ms | 43768 KB | Output is correct |