# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
211604 | 2020-03-20T19:21:13 Z | mieszko11b | Building 4 (JOI20_building4) | C++14 | 424 ms | 26128 KB |
#include <bits/stdc++.h> using namespace std; using ii = pair<int, int>; #define X first #define Y second int n; ii dp[1000007][2]; int a[1000007], b[1000007]; ii merge(ii a, ii b) { return {min(a.X, b.X), max(a.Y, b.Y)}; } ii addone(ii a) { return {a.X + 1, a.Y + 1}; } int main() { scanf("%d", &n); n *= 2; for(int i = 1 ; i <= n ; i++) scanf("%d", &a[i]); for(int i = 1 ; i <= n ; i++) scanf("%d", &b[i]); dp[1][0] = {1, 1}; dp[1][1] = {0, 0}; for(int i = 2 ; i <= n ; i++) { dp[i][0] = dp[i][1] = {1e9, -1e9}; if(a[i] >= a[i - 1]) dp[i][0] = merge(dp[i][0], addone(dp[i - 1][0])); if(a[i] >= b[i - 1]) dp[i][0] = merge(dp[i][0], addone(dp[i - 1][1])); if(b[i] >= a[i - 1]) dp[i][1] = merge(dp[i][1], dp[i - 1][0]); if(b[i] >= b[i - 1]) dp[i][1] = merge(dp[i][1], dp[i - 1][1]); } string res; int ac = 1; if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y)) ac = 2; if(!(dp[n][0].X <= n / 2 && n / 2 <= dp[n][0].Y) && !(dp[n][1].X <= n / 2 && n / 2 <= dp[n][1].Y)) { printf("-1\n"); return 0; } //~ cout << dp[n - 1][0].X << " "<< dp[n - 1][0].Y << endl; res += (ac == 1 ? 'A' : 'B'); int c = n / 2; for(int i = n ; i >= 2 ; i--) { //~ cout << n << " " << c << endl; int aac = 1; if(ac == 1) c--; if(!(dp[i - 1][0].X <= c && c <= dp[i - 1][0].Y && ((ac == 1 && a[i] >= a[i - 1]) || (ac == 2 && b[i] >= a[i - 1])))) aac = 2; ac = aac; res += (ac == 1 ? 'A' : 'B'); } reverse(res.begin(), res.end()); printf("%s\n", res.c_str()); 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 | 384 KB | Output is correct |
6 | Correct | 6 ms | 384 KB | Output is correct |
7 | Correct | 6 ms | 512 KB | Output is correct |
8 | Correct | 6 ms | 384 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 5 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 384 KB | Output is correct |
12 | Correct | 6 ms | 384 KB | Output is correct |
13 | Correct | 6 ms | 384 KB | Output is correct |
14 | Correct | 7 ms | 384 KB | Output is correct |
15 | Correct | 6 ms | 512 KB | Output is correct |
16 | Correct | 6 ms | 384 KB | Output is correct |
17 | Correct | 6 ms | 512 KB | Output is correct |
18 | Correct | 6 ms | 384 KB | Output is correct |
19 | Correct | 6 ms | 384 KB | Output is correct |
20 | Correct | 5 ms | 384 KB | Output is correct |
21 | Correct | 7 ms | 384 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 | 512 KB | Output is correct |
26 | Correct | 6 ms | 384 KB | Output is correct |
27 | Correct | 5 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 | 384 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 | 384 KB | Output is correct |
6 | Correct | 6 ms | 384 KB | Output is correct |
7 | Correct | 6 ms | 512 KB | Output is correct |
8 | Correct | 6 ms | 384 KB | Output is correct |
9 | Correct | 6 ms | 512 KB | Output is correct |
10 | Correct | 5 ms | 512 KB | Output is correct |
11 | Correct | 6 ms | 384 KB | Output is correct |
12 | Correct | 6 ms | 384 KB | Output is correct |
13 | Correct | 6 ms | 384 KB | Output is correct |
14 | Correct | 7 ms | 384 KB | Output is correct |
15 | Correct | 6 ms | 512 KB | Output is correct |
16 | Correct | 6 ms | 384 KB | Output is correct |
17 | Correct | 6 ms | 512 KB | Output is correct |
18 | Correct | 6 ms | 384 KB | Output is correct |
19 | Correct | 6 ms | 384 KB | Output is correct |
20 | Correct | 5 ms | 384 KB | Output is correct |
21 | Correct | 7 ms | 384 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 | 512 KB | Output is correct |
26 | Correct | 6 ms | 384 KB | Output is correct |
27 | Correct | 5 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 | 384 KB | Output is correct |
34 | Correct | 422 ms | 23544 KB | Output is correct |
35 | Correct | 385 ms | 24068 KB | Output is correct |
36 | Correct | 379 ms | 23728 KB | Output is correct |
37 | Correct | 389 ms | 24268 KB | Output is correct |
38 | Correct | 353 ms | 24112 KB | Output is correct |
39 | Correct | 352 ms | 24368 KB | Output is correct |
40 | Correct | 370 ms | 25964 KB | Output is correct |
41 | Correct | 318 ms | 24624 KB | Output is correct |
42 | Correct | 378 ms | 25268 KB | Output is correct |
43 | Correct | 422 ms | 25968 KB | Output is correct |
44 | Correct | 424 ms | 25964 KB | Output is correct |
45 | Correct | 413 ms | 25888 KB | Output is correct |
46 | Correct | 373 ms | 25968 KB | Output is correct |
47 | Correct | 366 ms | 26000 KB | Output is correct |
48 | Correct | 363 ms | 25964 KB | Output is correct |
49 | Correct | 361 ms | 25964 KB | Output is correct |
50 | Correct | 400 ms | 25964 KB | Output is correct |
51 | Correct | 397 ms | 25964 KB | Output is correct |
52 | Correct | 281 ms | 25964 KB | Output is correct |
53 | Correct | 292 ms | 25964 KB | Output is correct |
54 | Correct | 264 ms | 25964 KB | Output is correct |
55 | Correct | 266 ms | 25964 KB | Output is correct |
56 | Correct | 359 ms | 25964 KB | Output is correct |
57 | Correct | 313 ms | 25836 KB | Output is correct |
58 | Correct | 321 ms | 25964 KB | Output is correct |
59 | Correct | 318 ms | 26128 KB | Output is correct |
60 | Correct | 299 ms | 24368 KB | Output is correct |
61 | Correct | 321 ms | 25964 KB | Output is correct |
62 | Correct | 314 ms | 25580 KB | Output is correct |
63 | Correct | 317 ms | 26092 KB | Output is correct |
64 | Correct | 310 ms | 25008 KB | Output is correct |
65 | Correct | 321 ms | 25964 KB | Output is correct |