# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
728181 | 2023-04-22T03:53:05 Z | nguyentunglam | 건물 4 (JOI20_building4) | C++17 | 249 ms | 48336 KB |
#include<bits/stdc++.h> #define fi first #define se second #define endl "\n" #define ii pair<int, int> using namespace std; const int N = 1e6 + 10; int a[2][N], g[2][N], f[2][N], ans[N]; int cur, n; void trace(int type, int i) { ans[i] = type; cur += type; if (i == 1) return; if (a[type][i] >= a[0][i - 1] && cur + g[0][i - 1] <= n && n <= cur + f[0][i - 1]) trace(0, i - 1); else trace(1, i - 1); } int main() { #define task "" cin.tie(0) -> sync_with_stdio(0); if (fopen ("task.inp", "r")) { freopen ("task.inp", "r", stdin); freopen ("task.out", "w", stdout); } if (fopen (task".inp", "r")) { freopen (task".inp", "r", stdin); freopen (task".out", "w", stdout); } cin >> n; for(int i = 1; i <= n * 2; i++) cin >> a[0][i]; for(int i = 1; i <= n * 2; i++) cin >> a[1][i]; for(int i = 1; i <= n * 2; i++) { g[0][i] = g[1][i] = 1e9; for(int j = 0; j < 2; j++) for(int k = 0; k < 2; k++) if (a[j][i] >= a[k][i - 1]) { f[j][i] = max(f[j][i], f[k][i - 1] + j); g[j][i] = min(g[j][i], g[k][i - 1] + j); } } if (g[0][2 * n] <= n && n <= f[0][2 * n]) trace(0, 2 * n); else if (g[1][2 * n] <= n && n <= f[1][2 * n]) trace(1, 2 * n); else return cout << -1, 0; for(int i = 1; i <= 2 * n; i++) cout << (ans[i] == 1 ? "B" : "A"); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
12 | Correct | 2 ms | 468 KB | Output is correct |
13 | Correct | 2 ms | 468 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 1 ms | 468 KB | Output is correct |
16 | Correct | 2 ms | 548 KB | Output is correct |
17 | Correct | 2 ms | 468 KB | Output is correct |
18 | Correct | 2 ms | 468 KB | Output is correct |
19 | Correct | 2 ms | 468 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 468 KB | Output is correct |
22 | Correct | 1 ms | 468 KB | Output is correct |
23 | Correct | 2 ms | 472 KB | Output is correct |
24 | Correct | 2 ms | 468 KB | Output is correct |
25 | Correct | 1 ms | 468 KB | Output is correct |
26 | Correct | 2 ms | 468 KB | Output is correct |
27 | Correct | 1 ms | 476 KB | Output is correct |
28 | Correct | 1 ms | 468 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 1 ms | 468 KB | Output is correct |
31 | Correct | 1 ms | 468 KB | Output is correct |
32 | Correct | 2 ms | 468 KB | Output is correct |
33 | Correct | 2 ms | 468 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 340 KB | Output is correct |
3 | Correct | 0 ms | 340 KB | Output is correct |
4 | Correct | 0 ms | 340 KB | Output is correct |
5 | Correct | 1 ms | 340 KB | Output is correct |
6 | Correct | 1 ms | 468 KB | Output is correct |
7 | Correct | 2 ms | 468 KB | Output is correct |
8 | Correct | 1 ms | 468 KB | Output is correct |
9 | Correct | 1 ms | 468 KB | Output is correct |
10 | Correct | 1 ms | 468 KB | Output is correct |
11 | Correct | 2 ms | 468 KB | Output is correct |
12 | Correct | 2 ms | 468 KB | Output is correct |
13 | Correct | 2 ms | 468 KB | Output is correct |
14 | Correct | 1 ms | 468 KB | Output is correct |
15 | Correct | 1 ms | 468 KB | Output is correct |
16 | Correct | 2 ms | 548 KB | Output is correct |
17 | Correct | 2 ms | 468 KB | Output is correct |
18 | Correct | 2 ms | 468 KB | Output is correct |
19 | Correct | 2 ms | 468 KB | Output is correct |
20 | Correct | 2 ms | 468 KB | Output is correct |
21 | Correct | 2 ms | 468 KB | Output is correct |
22 | Correct | 1 ms | 468 KB | Output is correct |
23 | Correct | 2 ms | 472 KB | Output is correct |
24 | Correct | 2 ms | 468 KB | Output is correct |
25 | Correct | 1 ms | 468 KB | Output is correct |
26 | Correct | 2 ms | 468 KB | Output is correct |
27 | Correct | 1 ms | 476 KB | Output is correct |
28 | Correct | 1 ms | 468 KB | Output is correct |
29 | Correct | 1 ms | 468 KB | Output is correct |
30 | Correct | 1 ms | 468 KB | Output is correct |
31 | Correct | 1 ms | 468 KB | Output is correct |
32 | Correct | 2 ms | 468 KB | Output is correct |
33 | Correct | 2 ms | 468 KB | Output is correct |
34 | Correct | 219 ms | 42400 KB | Output is correct |
35 | Correct | 239 ms | 44500 KB | Output is correct |
36 | Correct | 223 ms | 43904 KB | Output is correct |
37 | Correct | 222 ms | 44772 KB | Output is correct |
38 | Correct | 224 ms | 44708 KB | Output is correct |
39 | Correct | 208 ms | 43996 KB | Output is correct |
40 | Correct | 223 ms | 47564 KB | Output is correct |
41 | Correct | 219 ms | 44936 KB | Output is correct |
42 | Correct | 237 ms | 46376 KB | Output is correct |
43 | Correct | 242 ms | 48180 KB | Output is correct |
44 | Correct | 244 ms | 48076 KB | Output is correct |
45 | Correct | 243 ms | 48036 KB | Output is correct |
46 | Correct | 231 ms | 48052 KB | Output is correct |
47 | Correct | 245 ms | 47136 KB | Output is correct |
48 | Correct | 209 ms | 46924 KB | Output is correct |
49 | Correct | 238 ms | 47720 KB | Output is correct |
50 | Correct | 245 ms | 47224 KB | Output is correct |
51 | Correct | 244 ms | 47156 KB | Output is correct |
52 | Correct | 176 ms | 36288 KB | Output is correct |
53 | Correct | 162 ms | 36300 KB | Output is correct |
54 | Correct | 151 ms | 36248 KB | Output is correct |
55 | Correct | 165 ms | 36004 KB | Output is correct |
56 | Correct | 249 ms | 48336 KB | Output is correct |
57 | Correct | 197 ms | 43012 KB | Output is correct |
58 | Correct | 203 ms | 43212 KB | Output is correct |
59 | Correct | 209 ms | 43180 KB | Output is correct |
60 | Correct | 190 ms | 41096 KB | Output is correct |
61 | Correct | 197 ms | 43728 KB | Output is correct |
62 | Correct | 192 ms | 43048 KB | Output is correct |
63 | Correct | 204 ms | 43760 KB | Output is correct |
64 | Correct | 193 ms | 42196 KB | Output is correct |
65 | Correct | 203 ms | 43668 KB | Output is correct |