# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211841 | 2020-03-21T14:02:50 Z | zimpha | Building 4 (JOI20_building4) | C++17 | 414 ms | 44920 KB |
#include <cstdio> #include <cassert> #include <vector> const int N = 1e6 + 10; char ret[N]; int val[N][2], f[N][2], g[N][2]; int main() { int n; scanf("%d", &n); for (int e = 0; e < 2; ++e) { for (int i = 0; i < n * 2; ++i) { scanf("%d", &val[i][e]); } } f[0][0] = g[0][0] = 1; f[0][1] = g[0][1] = 0; for (int i = 1; i < n * 2; ++i) { f[i][0] = +1e9, f[i][1] = +1e9; g[i][0] = -1e9, g[i][1] = -1e9; for (int x = 0; x < 2; ++x) for (int y = 0; y < 2; ++y) if (val[i][x] >= val[i - 1][y]) { int w = x == 0; if (g[i - 1][y] + w > g[i][x]) g[i][x] = g[i - 1][y] + w; if (f[i - 1][y] + w < f[i][x]) f[i][x] = f[i - 1][y] + w; } } int choose = 0; if (f[n * 2 - 1][0] > n || g[n * 2 - 1][0] < n) ++choose; if (f[n * 2 - 1][choose] > n || g[n * 2 - 1][choose] < n) { puts("-1"); return 0; } int need = n; for (int i = n * 2 - 1; i >= 0; --i) { ret[i] = choose + 'A'; need -= choose == 0; if (i) { bool found = false; for (int x = 0; x < 2; ++x) if (val[i][choose] >= val[i - 1][x]) { if (f[i - 1][x] <= need && need <= g[i - 1][x]) { choose = x; found = true; break; } } assert(found); } } ret[n * 2] = 0; puts(ret); return 0; }
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 | 4 ms | 384 KB | Output is correct |
4 | Correct | 4 ms | 384 KB | Output is correct |
5 | Correct | 6 ms | 512 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 6 ms | 512 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 6 ms | 512 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 | 7 ms | 512 KB | Output is correct |
15 | Correct | 6 ms | 512 KB | Output is correct |
16 | Correct | 6 ms | 512 KB | Output is correct |
17 | Correct | 6 ms | 512 KB | Output is correct |
18 | Correct | 7 ms | 512 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 5 ms | 512 KB | Output is correct |
21 | Correct | 5 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 512 KB | Output is correct |
23 | Correct | 6 ms | 384 KB | Output is correct |
24 | Correct | 6 ms | 512 KB | Output is correct |
25 | Correct | 5 ms | 512 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 7 ms | 512 KB | Output is correct |
28 | Correct | 6 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 | 5 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 | 512 KB | Output is correct |
6 | Correct | 6 ms | 512 KB | Output is correct |
7 | Correct | 6 ms | 512 KB | Output is correct |
8 | Correct | 6 ms | 512 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 6 ms | 512 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 | 7 ms | 512 KB | Output is correct |
15 | Correct | 6 ms | 512 KB | Output is correct |
16 | Correct | 6 ms | 512 KB | Output is correct |
17 | Correct | 6 ms | 512 KB | Output is correct |
18 | Correct | 7 ms | 512 KB | Output is correct |
19 | Correct | 6 ms | 512 KB | Output is correct |
20 | Correct | 5 ms | 512 KB | Output is correct |
21 | Correct | 5 ms | 384 KB | Output is correct |
22 | Correct | 5 ms | 512 KB | Output is correct |
23 | Correct | 6 ms | 384 KB | Output is correct |
24 | Correct | 6 ms | 512 KB | Output is correct |
25 | Correct | 5 ms | 512 KB | Output is correct |
26 | Correct | 6 ms | 512 KB | Output is correct |
27 | Correct | 7 ms | 512 KB | Output is correct |
28 | Correct | 6 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 | 414 ms | 25208 KB | Output is correct |
35 | Correct | 388 ms | 39800 KB | Output is correct |
36 | Correct | 394 ms | 31672 KB | Output is correct |
37 | Correct | 389 ms | 36216 KB | Output is correct |
38 | Correct | 340 ms | 33400 KB | Output is correct |
39 | Correct | 341 ms | 41208 KB | Output is correct |
40 | Correct | 354 ms | 27384 KB | Output is correct |
41 | Correct | 303 ms | 32956 KB | Output is correct |
42 | Correct | 376 ms | 26744 KB | Output is correct |
43 | Correct | 404 ms | 35832 KB | Output is correct |
44 | Correct | 409 ms | 36856 KB | Output is correct |
45 | Correct | 406 ms | 44920 KB | Output is correct |
46 | Correct | 362 ms | 34680 KB | Output is correct |
47 | Correct | 354 ms | 30968 KB | Output is correct |
48 | Correct | 354 ms | 29056 KB | Output is correct |
49 | Correct | 357 ms | 40316 KB | Output is correct |
50 | Correct | 393 ms | 27568 KB | Output is correct |
51 | Correct | 391 ms | 27640 KB | Output is correct |
52 | Correct | 280 ms | 33400 KB | Output is correct |
53 | Correct | 284 ms | 33512 KB | Output is correct |
54 | Correct | 245 ms | 32888 KB | Output is correct |
55 | Correct | 251 ms | 33144 KB | Output is correct |
56 | Correct | 361 ms | 43512 KB | Output is correct |
57 | Correct | 302 ms | 40056 KB | Output is correct |
58 | Correct | 306 ms | 40312 KB | Output is correct |
59 | Correct | 303 ms | 40316 KB | Output is correct |
60 | Correct | 289 ms | 38136 KB | Output is correct |
61 | Correct | 315 ms | 40856 KB | Output is correct |
62 | Correct | 312 ms | 40184 KB | Output is correct |
63 | Correct | 304 ms | 40568 KB | Output is correct |
64 | Correct | 301 ms | 38928 KB | Output is correct |
65 | Correct | 307 ms | 40572 KB | Output is correct |