# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
258784 | 2020-08-06T14:40:21 Z | amoo_safar | Building 4 (JOI20_building4) | C++17 | 641 ms | 50108 KB |
// Zende bad Shoma nasime faghat ! #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef long long ll; typedef long double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 1e6 + 10; const ll Inf = 2242545357980376863LL; const ll Log = 30; int n, A[2][N]; int O[2][N]; int mk[N]; int main(){ scanf("%d", &n); n += n; for(int it = 0; it < 2; it ++){ for(int i = 0; i < n; i++){ scanf("%d", A[it] + i); O[it][i] = true; } } for(int i = 1; i < n; i++){ for(int lv = 0; lv < 2; lv ++){ O[lv][i] &= (A[0][i - 1] <= A[lv][i] && O[0][i - 1]) || (A[1][i - 1] <= A[lv][i] && O[1][i - 1]); } } for(int i = n - 2; i >= 0; i--){ for(int lv = 0; lv < 2; lv ++){ O[lv][i] &= (A[0][i + 1] >= A[lv][i] && O[0][i + 1]) || (A[1][i + 1] >= A[lv][i] && O[1][i + 1]); } } for(int i = 0; i < n; i++) if(!O[0][i] && !O[1][i]) return !printf("-1\n"); int sm = 0; for(int i = 0; i < n; i++){ if(O[0][i] && !O[1][i]) sm ++; else if(!O[0][i] && O[1][i]) sm --; else { if(A[0][i] <= A[1][i]) sm ++; else sm --; } } bool flg = false; if(sm < 0){ sm = -sm; swap(A[0], A[1]); swap(O[0], O[1]); flg = true; } int po = 0; int Sm = 0; vector<pll> V; //cerr << "# " << sm << '\n'; for(int i = 0; i < n; ){ if(O[0][i] && !O[1][i]){ po ++; i = po; continue; } if(!O[0][i] && O[1][i]){ po ++; i = po; continue; } while((po + 1 < n) && (O[0][po + 1] && O[1][po + 1]) && (max(A[0][po], A[1][po]) > min(A[0][po + 1], A[1][po + 1])) ) po ++; //cerr << "! " << i << ' ' << po << '\n'; int nw = 0, mn = 0, v, idx = po + 1; for(int j = po; j >= i; j--){ v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) ); nw -= 2 * v; if(nw < mn){ idx = j; mn = nw; } } if(mn < 0){ Sm += mn; V.pb({po, idx}); } po ++; i = po; } //cerr << Sm << '\n'; if(Sm + sm > 0) return !printf("-1\n"); //debug(V.size()); for(auto [P, i] : V){ int v; for(int j = P; j >= i; j--){ if(sm == 0) break; v = (A[0][j] == A[1][j] ? (flg ? -1 : +1) : (A[0][j] < A[1][j] ? +1 : -1) ); sm -= 2 * v; mk[j] = 1; } } if(flg){ swap(A[0], A[1]); swap(O[0], O[1]); } int out = 0; vector<int> I; for(int i = 0; i < n; i++){ //if(mk[i]) debug(i); int mn; if(!O[0][i]) mn = 1; else if(!O[1][i]) mn = 0; else mn = (A[0][i] <= A[1][i] ? 0 : 1); if(mk[i]) mn = 1 - mn; if(mn == 0) out ++, printf("A"); if(mn == 1) out --, printf("B"); I.pb(A[mn][i]); } for(int i = 0; i + 1 < n; i++) assert(I[i] <= I[i + 1]); assert(out == 0); printf("\n"); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 15 ms | 16000 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 16 ms | 16128 KB | Output is correct |
9 | Correct | 21 ms | 16128 KB | Output is correct |
10 | Correct | 21 ms | 16128 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 560 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
15 | Correct | 18 ms | 16128 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 2 ms | 512 KB | Output is correct |
18 | Correct | 21 ms | 16128 KB | Output is correct |
19 | Correct | 3 ms | 512 KB | Output is correct |
20 | Correct | 2 ms | 512 KB | Output is correct |
21 | Correct | 2 ms | 512 KB | Output is correct |
22 | Correct | 2 ms | 640 KB | Output is correct |
23 | Correct | 2 ms | 512 KB | Output is correct |
24 | Correct | 16 ms | 16128 KB | Output is correct |
25 | Correct | 2 ms | 512 KB | Output is correct |
26 | Correct | 2 ms | 512 KB | Output is correct |
27 | Correct | 2 ms | 512 KB | Output is correct |
28 | Correct | 2 ms | 512 KB | Output is correct |
29 | Correct | 2 ms | 512 KB | Output is correct |
30 | Correct | 2 ms | 512 KB | Output is correct |
31 | Correct | 2 ms | 512 KB | Output is correct |
32 | Correct | 2 ms | 512 KB | Output is correct |
33 | Correct | 2 ms | 512 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 1 ms | 384 KB | Output is correct |
3 | Correct | 15 ms | 16000 KB | Output is correct |
4 | Correct | 1 ms | 384 KB | Output is correct |
5 | Correct | 3 ms | 512 KB | Output is correct |
6 | Correct | 2 ms | 512 KB | Output is correct |
7 | Correct | 2 ms | 512 KB | Output is correct |
8 | Correct | 16 ms | 16128 KB | Output is correct |
9 | Correct | 21 ms | 16128 KB | Output is correct |
10 | Correct | 21 ms | 16128 KB | Output is correct |
11 | Correct | 2 ms | 512 KB | Output is correct |
12 | Correct | 3 ms | 560 KB | Output is correct |
13 | Correct | 3 ms | 512 KB | Output is correct |
14 | Correct | 2 ms | 512 KB | Output is correct |
15 | Correct | 18 ms | 16128 KB | Output is correct |
16 | Correct | 3 ms | 512 KB | Output is correct |
17 | Correct | 2 ms | 512 KB | Output is correct |
18 | Correct | 21 ms | 16128 KB | Output is correct |
19 | Correct | 3 ms | 512 KB | Output is correct |
20 | Correct | 2 ms | 512 KB | Output is correct |
21 | Correct | 2 ms | 512 KB | Output is correct |
22 | Correct | 2 ms | 640 KB | Output is correct |
23 | Correct | 2 ms | 512 KB | Output is correct |
24 | Correct | 16 ms | 16128 KB | Output is correct |
25 | Correct | 2 ms | 512 KB | Output is correct |
26 | Correct | 2 ms | 512 KB | Output is correct |
27 | Correct | 2 ms | 512 KB | Output is correct |
28 | Correct | 2 ms | 512 KB | Output is correct |
29 | Correct | 2 ms | 512 KB | Output is correct |
30 | Correct | 2 ms | 512 KB | Output is correct |
31 | Correct | 2 ms | 512 KB | Output is correct |
32 | Correct | 2 ms | 512 KB | Output is correct |
33 | Correct | 2 ms | 512 KB | Output is correct |
34 | Correct | 409 ms | 16120 KB | Output is correct |
35 | Correct | 476 ms | 20072 KB | Output is correct |
36 | Correct | 453 ms | 19760 KB | Output is correct |
37 | Correct | 441 ms | 20072 KB | Output is correct |
38 | Correct | 423 ms | 32212 KB | Output is correct |
39 | Correct | 392 ms | 26596 KB | Output is correct |
40 | Correct | 641 ms | 30544 KB | Output is correct |
41 | Correct | 413 ms | 23104 KB | Output is correct |
42 | Correct | 505 ms | 20844 KB | Output is correct |
43 | Correct | 477 ms | 21440 KB | Output is correct |
44 | Correct | 459 ms | 21472 KB | Output is correct |
45 | Correct | 535 ms | 21512 KB | Output is correct |
46 | Correct | 443 ms | 33232 KB | Output is correct |
47 | Correct | 497 ms | 27416 KB | Output is correct |
48 | Correct | 414 ms | 27360 KB | Output is correct |
49 | Correct | 414 ms | 30672 KB | Output is correct |
50 | Correct | 591 ms | 21424 KB | Output is correct |
51 | Correct | 594 ms | 21468 KB | Output is correct |
52 | Correct | 362 ms | 29920 KB | Output is correct |
53 | Correct | 357 ms | 29976 KB | Output is correct |
54 | Correct | 330 ms | 50108 KB | Output is correct |
55 | Correct | 337 ms | 45372 KB | Output is correct |
56 | Correct | 414 ms | 23024 KB | Output is correct |
57 | Correct | 383 ms | 28128 KB | Output is correct |
58 | Correct | 357 ms | 28204 KB | Output is correct |
59 | Correct | 374 ms | 30148 KB | Output is correct |
60 | Correct | 338 ms | 28400 KB | Output is correct |
61 | Correct | 359 ms | 29532 KB | Output is correct |
62 | Correct | 410 ms | 29380 KB | Output is correct |
63 | Correct | 485 ms | 29804 KB | Output is correct |
64 | Correct | 368 ms | 29024 KB | Output is correct |
65 | Correct | 345 ms | 29544 KB | Output is correct |