# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211617 | 2020-03-20T20:24:31 Z | khsoo01 | Building 4 (JOI20_building4) | C++11 | 428 ms | 29028 KB |
#include<bits/stdc++.h> using namespace std; const int N = 1000005, inf = 2e9; int n, a[N][2], s[N][2], e[N][2]; int main() { scanf("%d",&n); n *= 2; for(int j=0;j<2;j++) { for(int i=1;i<=n;i++) { scanf("%d",&a[i][j]); } } for(int i=1;i<=n;i++) { for(int j=0;j<2;j++) { s[i][j] = inf, e[i][j] = -inf; for(int k=0;k<2;k++) { if(e[i-1][k] < 0 || a[i-1][k] > a[i][j]) continue; s[i][j] = min(s[i][j], s[i-1][k] + (j==0)); e[i][j] = max(e[i][j], e[i-1][k] + (j==0)); } } } vector<int> ans; if(s[n][0] <= n/2 && n/2 <= e[n][0]) ans.push_back(0); else if(s[n][1] <= n/2 && n/2 <= e[n][1]) ans.push_back(1); else {puts("-1"); return 0;} int L = n/2; for(int i=n;i>1;i--) { int j = ans.back(); if(j == 0) L--; for(int k=0;k<2;k++) { if(e[i-1][k] < 0 || a[i-1][k] > a[i][j]) continue; if(s[i-1][k] <= L && L <= e[i-1][k]) { ans.push_back(k); break; } } } for(int i=n;i--;) { putchar('A' + ans[i]); } puts(""); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 6 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 384 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 | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 6 ms | 512 KB | Output is correct |
13 | Correct | 6 ms | 512 KB | Output is correct |
14 | Correct | 6 ms | 512 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 | 384 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 5 ms | 512 KB | Output is correct |
21 | Correct | 6 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 384 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 | 512 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 6 ms | 384 KB | Output is correct |
28 | Correct | 5 ms | 384 KB | Output is correct |
29 | Correct | 6 ms | 512 KB | Output is correct |
30 | Correct | 5 ms | 384 KB | Output is correct |
31 | Correct | 6 ms | 512 KB | Output is correct |
32 | Correct | 5 ms | 384 KB | Output is correct |
33 | Correct | 6 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Correct | 4 ms | 384 KB | Output is correct |
3 | Correct | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 6 ms | 384 KB | Output is correct |
6 | Correct | 6 ms | 384 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 | 384 KB | Output is correct |
10 | Correct | 5 ms | 384 KB | Output is correct |
11 | Correct | 6 ms | 512 KB | Output is correct |
12 | Correct | 6 ms | 512 KB | Output is correct |
13 | Correct | 6 ms | 512 KB | Output is correct |
14 | Correct | 6 ms | 512 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 | 384 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 5 ms | 512 KB | Output is correct |
21 | Correct | 6 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 384 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 | 512 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 6 ms | 384 KB | Output is correct |
28 | Correct | 5 ms | 384 KB | Output is correct |
29 | Correct | 6 ms | 512 KB | Output is correct |
30 | Correct | 5 ms | 384 KB | Output is correct |
31 | Correct | 6 ms | 512 KB | Output is correct |
32 | Correct | 5 ms | 384 KB | Output is correct |
33 | Correct | 6 ms | 512 KB | Output is correct |
34 | Correct | 405 ms | 23416 KB | Output is correct |
35 | Correct | 389 ms | 26848 KB | Output is correct |
36 | Correct | 384 ms | 26336 KB | Output is correct |
37 | Correct | 389 ms | 26848 KB | Output is correct |
38 | Correct | 359 ms | 26852 KB | Output is correct |
39 | Correct | 347 ms | 26984 KB | Output is correct |
40 | Correct | 374 ms | 28764 KB | Output is correct |
41 | Correct | 332 ms | 27564 KB | Output is correct |
42 | Correct | 397 ms | 28132 KB | Output is correct |
43 | Correct | 428 ms | 28892 KB | Output is correct |
44 | Correct | 424 ms | 28900 KB | Output is correct |
45 | Correct | 424 ms | 28896 KB | Output is correct |
46 | Correct | 384 ms | 28896 KB | Output is correct |
47 | Correct | 394 ms | 28872 KB | Output is correct |
48 | Correct | 403 ms | 28916 KB | Output is correct |
49 | Correct | 395 ms | 28828 KB | Output is correct |
50 | Correct | 410 ms | 28920 KB | Output is correct |
51 | Correct | 411 ms | 28916 KB | Output is correct |
52 | Correct | 304 ms | 29024 KB | Output is correct |
53 | Correct | 301 ms | 28892 KB | Output is correct |
54 | Correct | 266 ms | 28900 KB | Output is correct |
55 | Correct | 269 ms | 29028 KB | Output is correct |
56 | Correct | 384 ms | 28908 KB | Output is correct |
57 | Correct | 326 ms | 28772 KB | Output is correct |
58 | Correct | 326 ms | 28900 KB | Output is correct |
59 | Correct | 325 ms | 28900 KB | Output is correct |
60 | Correct | 320 ms | 27104 KB | Output is correct |
61 | Correct | 355 ms | 28992 KB | Output is correct |
62 | Correct | 330 ms | 28640 KB | Output is correct |
63 | Correct | 341 ms | 28900 KB | Output is correct |
64 | Correct | 322 ms | 27876 KB | Output is correct |
65 | Correct | 344 ms | 28896 KB | Output is correct |