2203.md (11418B)
1 Source: https://codeforces.com/blog/entry/151612 2 3 [2203A - Towers of Boxes](/contest/2203/problem/A "Educational Codeforces Round 187 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 n, m, d = map(int, input().split()) 17 k = 1 + d // m 18 print((n + k - 1) // k) 19 ``` 20 21 [2203B - Beautiful Numbers](/contest/2203/problem/B "Educational Codeforces Round 187 (Rated for Div. 2)") 22 23 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 24 25 **Tutorial** 26 27 Tutorial is loading... 28 29 **Solution (Neon)** 30 31 ``` 32 #include <bits/stdc++.h> 33 34 using namespace std; 35 36 int main() { 37 int t; 38 cin >> t; 39 while (t--) { 40 string s; 41 cin >> s; 42 int sum = 0; 43 vector<int> a; 44 for (int i = 0; i < int(s.size()); ++i) { 45 int x = s[i] - '0'; 46 sum += x; 47 a.push_back(x - (i == 0)); 48 } 49 sort(a.begin(), a.end()); 50 int ans = 0; 51 while (sum > 9) { 52 sum -= a.back(); 53 a.pop_back(); 54 ++ans; 55 } 56 cout << ans << '\n'; 57 } 58 } 59 ``` 60 61 [2203C - Test Generator](/contest/2203/problem/C "Educational Codeforces Round 187 (Rated for Div. 2)") 62 63 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 64 65 **Tutorial** 66 67 Tutorial is loading... 68 69 **Solution (FelixArg)** 70 71 ``` 72 #include<bits/stdc++.h> 73 #define int long long 74 using namespace std; 75 76 bool get(int x, int a, int lim){ 77 int f = 0; 78 for (int i = 59; i >= 0; i--){ 79 f <<= 1; 80 if (((x >> i) & 1) == 1){ 81 f++; 82 } 83 if (((a >> i) & 1) == 1){ 84 f -= min(lim, f); 85 } 86 } 87 return (f == 0); 88 } 89 90 void solve(){ 91 int x, a; 92 cin >> x >> a; 93 94 if (!get(x, a, 1ll << 60)){ 95 cout << -1 << '\n'; 96 return; 97 } 98 99 int l = 0, r = (1ll << 60); 100 while(l <= r){ 101 int m = l + (r - l) / 2; 102 if (get(x, a, m)){ 103 r = m - 1; 104 } 105 else{ 106 l = m + 1; 107 } 108 } 109 110 cout << l << '\n'; 111 } 112 113 signed main() 114 { 115 #ifdef FELIX 116 auto _clock_start = chrono::high_resolution_clock::now(); 117 #endif 118 ios_base::sync_with_stdio(false); 119 cin.tie(0); 120 cout.tie(0); 121 122 int tests = 1; 123 cin >> tests; 124 for (int test = 0; test < tests; test++){ 125 solve(); 126 } 127 #ifdef FELIX 128 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 129 chrono::high_resolution_clock::now() 130 - _clock_start).count() << "ms." << endl; 131 #endif 132 return 0; 133 } 134 ``` 135 136 [2203D - Divisibility Game](/contest/2203/problem/D "Educational Codeforces Round 187 (Rated for Div. 2)") 137 138 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 139 140 **Tutorial** 141 142 Tutorial is loading... 143 144 **Solution (FelixArg)** 145 146 ``` 147 #include <bits/stdc++.h> 148 149 using namespace std; 150 151 int main() { 152 ios_base::sync_with_stdio(0); 153 cin.tie(0); 154 cout.tie(0); 155 156 int t; 157 cin >> t; 158 159 for (int test = 0; test < t; test++){ 160 int n, m; 161 cin >> n >> m; 162 163 vector<int> a(n), b(m); 164 for (int i = 0; i < n; i++){ 165 cin >> a[i]; 166 } 167 for (int i = 0; i < m; i++){ 168 cin >> b[i]; 169 } 170 171 int max_a = n + m + 1; 172 173 vector<int> cnt_b(max_a, 0), cnt_a(max_a, 0); 174 175 for (int i = 0; i < n; i++){ 176 cnt_a[a[i]]++; 177 } 178 179 for (int i = 0; i < m; i++){ 180 cnt_b[b[i]]++; 181 } 182 183 vector<int> cnt_del(max_a, 0); 184 185 int f = 0, s = 0, com = 0; 186 187 for (int i = 1; i < max_a; i++){ 188 for (int j = i; j < max_a; j += i){ 189 cnt_del[j] += cnt_a[i]; 190 } 191 } 192 193 for (int i = 1; i < max_a; i++){ 194 if (cnt_b[i] == 0){ 195 continue; 196 } 197 198 if (cnt_del[i] == 0){ 199 s += cnt_b[i]; 200 } 201 else if (cnt_del[i] == n){ 202 f += cnt_b[i]; 203 } 204 } 205 206 com = m - f - s; 207 208 bool turn = 0; 209 string win = ""; 210 211 while(1){ 212 if (turn == 0){ 213 if (com > 0){ 214 com--; 215 } 216 else if (f > 0){ 217 f--; 218 } 219 else{ 220 win = "Bob"; 221 break; 222 } 223 } 224 else{ 225 if (com > 0){ 226 com--; 227 } 228 else if (s > 0){ 229 s--; 230 } 231 else{ 232 win = "Alice"; 233 break; 234 } 235 } 236 turn = !turn; 237 } 238 239 cout << win << '\n'; 240 } 241 242 return 0; 243 } 244 ``` 245 246 [2203E - Probabilistic Card Game](/contest/2203/problem/E "Educational Codeforces Round 187 (Rated for Div. 2)") 247 248 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 249 250 **Tutorial** 251 252 Tutorial is loading... 253 254 **Solution 1 (awoo)** 255 256 ``` 257 #include <bits/stdc++.h> 258 #include "ext/pb_ds/assoc_container.hpp" 259 using namespace __gnu_pbds; 260 261 #define forn(i, n) for (int i = 0; i < int(n); i++) 262 263 using namespace std; 264 265 const int MOD = 998244353; 266 267 int mul(int a, int b){ 268 return a * 1ll * b % MOD; 269 } 270 271 int binpow(int a, int b){ 272 int res = 1; 273 while (b){ 274 if (b & 1) 275 res = mul(res, a); 276 a = mul(a, a); 277 b >>= 1; 278 } 279 return res; 280 } 281 282 template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; 283 284 int main() { 285 cin.tie(0); 286 ios::sync_with_stdio(false); 287 int m; 288 cin >> m; 289 vector<long long> a(m); 290 forn(i, m) cin >> a[i]; 291 auto xs = a; 292 sort(xs.begin(), xs.end()); 293 for (auto& x : a) x = lower_bound(xs.begin(), xs.end(), x) - xs.begin(); 294 295 vector<long long> f(m); 296 297 auto upd = [&](int x, long long val){ 298 for (int i = x; i < int(f.size()); i |= i + 1) 299 f[i] += val; 300 }; 301 auto get = [&](int x){ 302 long long sum = 0; 303 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 304 sum += f[i]; 305 return sum; 306 }; 307 308 long long sum = 0; 309 ordered_set<int> cur; 310 for (int x : a){ 311 cur.insert(x); 312 int n = cur.size(); 313 sum += xs[x]; 314 upd(x, xs[x]); 315 316 if (n < 3) continue; 317 318 auto getL = [&](int pos, auto it){ 319 if (it == cur.begin()) return 0ll; 320 return xs[*prev(it)] * 1ll * pos - get(*it - 1); 321 }; 322 323 auto getR = [&](int pos, auto it){ 324 if (next(it) == cur.end()) return 0ll; 325 return (sum - get(*it)) - xs[*next(it)] * 1ll * (n - pos - 1); 326 }; 327 328 int l = 0, r = n - 1; 329 int pos = n; 330 while (l <= r){ 331 int m = (l + r) / 2; 332 auto it = cur.find_by_order(m); 333 if (getL(m, it) >= getR(m, it)){ 334 pos = m; 335 r = m - 1; 336 } 337 else{ 338 l = m + 1; 339 } 340 } 341 342 long long ans = 1e18; 343 forn(_, 2){ 344 if (0 <= pos && pos < n){ 345 auto it = cur.find_by_order(pos); 346 ans = min(ans, max(getL(pos, it), getR(pos, it))); 347 } 348 --pos; 349 } 350 351 cout << mul(ans % MOD, binpow(n - 2, MOD - 2)) << '\n'; 352 } 353 return 0; 354 } 355 ``` 356 357 **Solution 2 (awoo)** 358 359 ``` 360 #include <bits/stdc++.h> 361 362 #define forn(i, n) for (int i = 0; i < int(n); i++) 363 364 using namespace std; 365 366 const long long INF64 = 1e18; 367 const int MOD = 998244353; 368 369 int mul(int a, int b){ 370 return a * 1ll * b % MOD; 371 } 372 373 int binpow(int a, int b){ 374 int res = 1; 375 while (b){ 376 if (b & 1) 377 res = mul(res, a); 378 a = mul(a, a); 379 b >>= 1; 380 } 381 return res; 382 } 383 384 int main() { 385 cin.tie(0); 386 ios::sync_with_stdio(false); 387 int m; 388 cin >> m; 389 vector<long long> a(m); 390 int n = m + 2; 391 forn(i, m) cin >> a[i]; 392 393 int p = sqrt(n) + 3; 394 auto xs = a; 395 xs.push_back(0); 396 sort(xs.begin(), xs.end()); 397 xs.push_back(xs.back() + 1); 398 vector<int> cntbl(n), rgh(n, -1); 399 rgh[0] = 0; 400 rgh[(n - 1) / p] = n - 1; 401 vector<long long> sumbl(n); 402 vector<int> cll(n, 0), clr(n, n - 1); 403 404 set<int> on({0, n - 1}); 405 int cnt = 0; 406 long long sum = 0; 407 forn(i, m){ 408 int x = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin(); 409 int bl = x / p; 410 411 ++cntbl[bl]; 412 sumbl[bl] += xs[x]; 413 rgh[bl] = max(rgh[bl], x); 414 sum += xs[x]; 415 ++cnt; 416 417 auto it = on.lower_bound(x); 418 clr[x] = *it; 419 cll[x] = *prev(it); 420 clr[*prev(it)] = cll[*it] = x; 421 on.insert(x); 422 423 if (cnt < 3) continue; 424 425 int lst = clr[0]; 426 int cntl = 0; 427 long long suml = 0; 428 429 auto getL = [&](int x){ return xs[cll[x]] * 1ll * cntl - suml; }; 430 auto getR = [&](int x){ return (sum - suml - xs[x]) - xs[clr[x]] * 1ll * (cnt - cntl - 1); }; 431 auto check = [&](int x){ 432 if (x == 0) return true; 433 if (x == n - 1) return false; 434 return getL(x) < getR(x); 435 }; 436 437 while (lst < n - 1){ 438 int bl = lst / p; 439 assert(rgh[bl] != -1); 440 if (!check(rgh[bl])) break; 441 cntl += cntbl[bl]; 442 suml += sumbl[bl]; 443 lst = clr[rgh[bl]]; 444 } 445 446 while (lst < n - 1){ 447 if (!check(lst)) break; 448 ++cntl; 449 suml += xs[lst]; 450 lst = clr[lst]; 451 } 452 453 x = lst; 454 long long ans = 1e18; 455 if (x != n - 1) 456 ans = min(ans, max(getL(x), getR(x))); 457 assert(x != 0); 458 x = cll[x]; 459 if (x != 0){ 460 --cntl; 461 suml -= xs[x]; 462 ans = min(ans, max(getL(x), getR(x))); 463 } 464 465 cout << mul(ans % MOD, binpow(cnt - 2, MOD - 2)) << '\n'; 466 } 467 return 0; 468 } 469 ``` 470 471 [2203F - Binary Search with One Swap](/contest/2203/problem/F "Educational Codeforces Round 187 (Rated for Div. 2)") 472 473 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 474 475 **Tutorial** 476 477 Tutorial is loading... 478 479 **Solution (BledDest)** 480 481 ``` 482 #include<bits/stdc++.h> 483 484 using namespace std; 485 486 vector<long long> ans; 487 int n; 488 vector<int> cnt; 489 490 void prepare_aux(int l, int r, vector<int>& a) 491 { 492 if(l > r) return; 493 int m = (l + r) / 2; 494 a[m] = r - l + 1; 495 if(l < m) prepare_aux(l, m - 1, a); 496 if(m < r) prepare_aux(m + 1, r, a); 497 } 498 499 vector<int> prepare(int len) 500 { 501 vector<int> a(len); 502 prepare_aux(0, len - 1, a); 503 return a; 504 } 505 506 int get_left(int len) 507 { 508 int m = (len - 1) / 2; 509 return m; 510 } 511 512 int get_right(int len) 513 { 514 int m = (len - 1) / 2; 515 return len - m - 1; 516 } 517 518 vector<long long> get(int x) 519 { 520 vector<long long> res(x + 1); 521 int m = (x - 1) / 2; 522 int left = m; 523 int right = x - m - 1; 524 vector<int> prepared = prepare(x); 525 //cout << x << endl; 526 // swap m with something to the left 527 { 528 for(int i = 0; i < m; i++) 529 { 530 int lost = abs(m - i); 531 //cout << i << " " << m << " " << lost << endl; 532 res[lost]++; 533 } 534 } 535 // swap m with something to the right 536 { 537 for(int i = 0; i < right; i++) 538 { 539 int lost = i + 1; 540 //cout << m << " " << i + m + 1 << " " << lost << endl; 541 res[lost]++; 542 } 543 } 544 // swap something to the left with something to the right 545 { 546 map<int, int> lost_left; 547 map<int, int> lost_right; 548 for(int i = 0; i < x; i++) 549 { 550 if(i == m) continue; 551 if(i < m) 552 { 553 int lost = get_right(prepared[i]) + 1; 554 lost_left[lost]++; 555 } 556 else 557 { 558 int lost = get_left(prepared[i]) + 1; 559 lost_right[lost]++; 560 } 561 } 562 for(auto p : lost_left) 563 for(auto p2 : lost_right) 564 { 565 //cerr << p.first << " " << p.second << endl; 566 //cerr << p2.first << " " << p2.second << endl; 567 res[p.first + p2.first] += p.second * 1ll * p2.second; 568 } 569 } 570 //cout << x << ":"; 571 //for(auto y : dp[x]) cout << " " << y; 572 //cout << endl; 573 return res; 574 } 575 576 void calc(int l, int r) 577 { 578 if(l > r) return; 579 int m = (l + r) / 2; 580 if(l < m) calc(l, m - 1); 581 if(m < r) calc(m + 1, r); 582 int len = r - l + 1; 583 cnt[len]++; 584 } 585 586 int main() 587 { 588 ios_base::sync_with_stdio(0); 589 cin.tie(0); 590 cin >> n; 591 ans.resize(n + 1); 592 cnt.resize(n + 1); 593 calc(0, n - 1); 594 for(int i = 1; i <= n; i++) 595 if(cnt[i] != 0) 596 { 597 auto g = get(i); 598 for(int j = 0; j <= i; j++) 599 ans[n - j] += cnt[i] * g[j]; 600 } 601 for(auto x : ans) cout << x << " "; 602 cout << "\n"; 603 return 0; 604 } 605 ```