1895.md (11632B)
1 Source: https://codeforces.com/blog/entry/122034 2 3 [1895A - Treasure Chest](/contest/1895/problem/A "Educational Codeforces Round 157 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 x, y, k = map(int, input().split()) 16 if y < x: 17 print(x) 18 else: 19 print(y + max(0, y - x - k)) 20 ``` 21 22 [1895B - Points and Minimum Distance](/contest/1895/problem/B "Educational Codeforces Round 157 (Rated for Div. 2)") 23 24 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 25 26 **Tutorial** 27 28 Tutorial is loading... 29 30 **Solution (fcspartakm)** 31 32 ``` 33 #include <bits/stdc++.h> 34 35 using namespace std; 36 37 int n; 38 vector<int> a; 39 40 inline void read() { 41 cin >> n; 42 a.clear(); 43 for (int i = 0; i < 2 * n; i++) { 44 int x; 45 cin >> x; 46 a.pb(x); 47 } 48 } 49 inline void solve() { 50 sort(all(a)); 51 vector<pair<int, int> > pts; 52 for (int i = 0; i < n; i++) { 53 pts.pb(mp(a[i], a[i + n])); 54 } 55 int ans = 0; 56 for (int i = 1; i < n; i++) { 57 ans += abs(pts[i].ft - pts[i - 1].ft) + abs(pts[i].sc - pts[i - 1].sc); 58 } 59 cout << ans << endl; 60 for (int i = 0; i < n; i++) { 61 cout << pts[i].ft << ' ' << pts[i].sc << endl; 62 } 63 } 64 65 int main () { 66 int t; 67 cin >> t; 68 while (t--){ 69 read(); 70 solve(); 71 } 72 } 73 ``` 74 75 [1895C - Torn Lucky Ticket](/contest/1895/problem/C "Educational Codeforces Round 157 (Rated for Div. 2)") 76 77 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 78 79 **Tutorial** 80 81 Tutorial is loading... 82 83 **Solution (awoo)** 84 85 ``` 86 n = int(input()) 87 s = input().split() 88 ans = 0 89 cnt = [[0 for k in range(46)] for k in range(6)] 90 for y in s: 91 cnt[len(y)][sum([int(c) for c in y])] += 1 92 for L in s: 93 for lenr in range(len(L) % 2, len(L) + 1, 2): 94 l = len(L) + lenr 95 suml = sum([int(c) for c in L[:l // 2]]) 96 sumr = sum([int(c) for c in L[l // 2:]]) 97 if suml - sumr >= 0: 98 ans += cnt[lenr][suml - sumr] 99 for R in s: 100 for lenl in range(len(R) % 2, len(R), 2): 101 l = len(R) + lenl 102 suml = sum([int(c) for c in R[-l // 2:]]) 103 sumr = sum([int(c) for c in R[:-l // 2]]) 104 if suml - sumr >= 0: 105 ans += cnt[lenl][suml - sumr] 106 print(ans) 107 ``` 108 109 [1895D - XOR Construction](/contest/1895/problem/D "Educational Codeforces Round 157 (Rated for Div. 2)") 110 111 Idea: [AcidWrongGod](/profile/AcidWrongGod "International Master AcidWrongGod") 112 113 **Tutorial** 114 115 Tutorial is loading... 116 117 **Solution (Neon)** 118 119 ``` 120 #include <bits/stdc++.h> 121 122 using namespace std; 123 124 const int LOG = 20; 125 126 int main() { 127 ios::sync_with_stdio(false); cin.tie(0); 128 int n; 129 cin >> n; 130 vector<int> a(n); 131 for (int i = 1; i < n; ++i) { 132 cin >> a[i]; 133 a[i] ^= a[i - 1]; 134 } 135 vector<array<int, 2>> t({{-1, -1}}); 136 auto add = [&](int x) { 137 int v = 0; 138 for (int i = LOG - 1; i >= 0; --i) { 139 int j = (x >> i) & 1; 140 if (t[v][j] == -1) { 141 t[v][j] = t.size(); 142 t.push_back({-1, -1}); 143 } 144 v = t[v][j]; 145 } 146 }; 147 for (int x : a) add(x); 148 auto get = [&](int x) { 149 int v = 0; 150 for (int i = LOG - 1; i >= 0; --i) { 151 int j = (x >> i) & 1; 152 if (t[v][j ^ 1] != -1) j ^= 1; 153 x ^= j << i; 154 v = t[v][j]; 155 } 156 return x; 157 }; 158 for (int x = 0; x < n; ++x) { 159 if (get(x) == n - 1) { 160 for (int i : a) cout << (x ^ i) << ' '; 161 break; 162 } 163 } 164 } 165 ``` 166 167 [1895E - Infinite Card Game](/contest/1895/problem/E "Educational Codeforces Round 157 (Rated for Div. 2)") 168 169 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 170 171 **Tutorial** 172 173 Tutorial is loading... 174 175 **Solution (awoo)** 176 177 ``` 178 // 179 180 #include <bits/stdc++.h> 181 182 #define forn(i, n) for (int i = 0; i < int(n); i++) 183 184 using namespace std; 185 186 struct card{ 187 int x, y; 188 card() {} 189 card(int x, int y) : x(x), y(y) {} 190 }; 191 192 void dfs(int v, const vector<int> &g, vector<int> &res, vector<char> &used){ 193 if (used[v]) return; 194 used[v] = true; 195 dfs(g[v], g, res, used); 196 res[v] = -res[g[v]]; 197 } 198 199 void solve(){ 200 vector<vector<card>> a(2); 201 vector<vector<int>> prpos(2); 202 forn(z, 2){ 203 int n; 204 scanf("%d", &n); 205 a[z].resize(n); 206 forn(i, n) scanf("%d", &a[z][i].x); 207 forn(i, n) scanf("%d", &a[z][i].y); 208 sort(a[z].begin(), a[z].end(), [](const card &a, const card &b){ 209 return a.x > b.x; 210 }); 211 prpos[z].resize(n + 1, -1); 212 forn(i, n){ 213 if (prpos[z][i] == -1 || a[z][i].y > a[z][prpos[z][i]].y) 214 prpos[z][i + 1] = i; 215 else 216 prpos[z][i + 1] = prpos[z][i]; 217 } 218 } 219 int n = a[0].size(); 220 vector<int> g(n + a[1].size()); 221 forn(z, 2) forn(i, a[z].size()){ 222 int cnt = lower_bound(a[z ^ 1].begin(), a[z ^ 1].end(), card(a[z][i].y, -1), [](const card &a, const card &b){ 223 return a.x > b.x; 224 }) - a[z ^ 1].begin(); 225 g[i + z * n] = prpos[z ^ 1][cnt] == -1 ? -1 : prpos[z ^ 1][cnt] + (z ^ 1) * n; 226 } 227 vector<int> res(g.size()); 228 vector<char> used(g.size()); 229 forn(i, g.size()) if (g[i] == -1) res[i] = 1, used[i] = true; 230 int w = 0, l = 0; 231 forn(i, n){ 232 if (!used[i]) dfs(i, g, res, used); 233 w += res[i] == 1; 234 l += res[i] == -1; 235 } 236 printf("%d %d %d\n", w, n - l - w, l); 237 } 238 239 int main(){ 240 int t; 241 scanf("%d", &t); 242 while (t--) solve(); 243 } 244 ``` 245 246 [1895F - Fancy Arrays](/contest/1895/problem/F "Educational Codeforces Round 157 (Rated for Div. 2)") 247 248 Idea: [Neon](/profile/Neon "Candidate Master Neon") 249 250 **Tutorial** 251 252 Tutorial is loading... 253 254 **Solution (Neon)** 255 256 ``` 257 #include <bits/stdc++.h> 258 259 using namespace std; 260 261 #define forn(i, n) for (int i = 0; i < int(n); ++i) 262 263 const int MOD = 1e9 + 7; 264 const int N = 40; 265 266 using mat = array<array<int, N>, N>; 267 268 int add(int x, int y) { 269 x += y; 270 if (x >= MOD) x -= MOD; 271 if (x < 0) x += MOD; 272 return x; 273 } 274 275 int mul(int x, int y) { 276 return x * 1LL * y % MOD; 277 } 278 279 mat mul(mat x, mat y) { 280 mat res; 281 forn(i, N) forn(j, N) res[i][j] = 0; 282 forn(i, N) forn(j, N) forn(k, N) 283 res[i][j] = add(res[i][j], mul(x[i][k], y[k][j])); 284 return res; 285 } 286 287 template<class T> 288 T binpow(T x, int y, T e) { 289 T res = e; 290 while (y) { 291 if (y & 1) res = mul(res, x); 292 x = mul(x, x); 293 y >>= 1; 294 } 295 return res; 296 } 297 298 int main() { 299 int t; 300 cin >> t; 301 while (t--) { 302 int n, x, k; 303 cin >> n >> x >> k; 304 mat a, e; 305 forn(i, N) forn(j, N) a[i][j] = (i < x && abs(i - j) <= k); 306 forn(i, N) forn(j, N) e[i][j] = (i == j); 307 mat b = binpow(a, n - 1, e); 308 int ans = mul(x + k, binpow(2 * k + 1, n - 1, 1)); 309 forn(i, x) forn(j, x) ans = add(ans, -b[i][j]); 310 cout << ans << '\n'; 311 } 312 } 313 ``` 314 315 [1895G - Two Characters, Two Colors](/contest/1895/problem/G "Educational Codeforces Round 157 (Rated for Div. 2)") 316 317 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 318 319 **Tutorial** 320 321 Tutorial is loading... 322 323 **Solution (BledDest)** 324 325 ``` 326 #include<bits/stdc++.h> 327 328 using namespace std; 329 330 mt19937 rnd(42); 331 332 struct node 333 { 334 long long x; 335 int y; 336 int cnt; 337 int sum; 338 int push; 339 node* l; 340 node* r; 341 node() {}; 342 node(long long x, int y, int cnt, int sum, int push, node* l, node* r) : x(x), y(y), cnt(cnt), sum(sum), push(push), l(l), r(r) {}; 343 }; 344 345 typedef node* treap; 346 typedef pair<treap, treap> ptt; 347 348 int getSum(treap t) 349 { 350 return (t ? t->sum : 0); 351 } 352 353 int getCnt(treap t) 354 { 355 return (t ? t->cnt : 0); 356 } 357 358 treap fix(treap t) 359 { 360 if(!t) return t; 361 int p = t->push; 362 if(p != 0) 363 { 364 if(t->l) t->l->push += p; 365 if(t->r) t->r->push += p; 366 t->x += p; 367 t->push = 0; 368 } 369 t->sum = getSum(t->l) + t->cnt + getSum(t->r); 370 return t; 371 } 372 373 treap merge(treap a, treap b) 374 { 375 a = fix(a); 376 b = fix(b); 377 if(!a) return b; 378 if(!b) return a; 379 if(a->y > b->y) 380 { 381 a->r = merge(a->r, b); 382 return fix(a); 383 } 384 else 385 { 386 b->l = merge(a, b->l); 387 return fix(b); 388 } 389 } 390 391 bool hasKey(treap t, long long x) 392 { 393 t = fix(t); 394 if(!t) return false; 395 if(t->x == x) return true; 396 if(t->x < x) return hasKey(t->r, x); 397 return hasKey(t->l, x); 398 } 399 400 ptt splitKey(treap t, long long x) 401 { 402 t = fix(t); 403 if(!t) return make_pair(t, t); 404 if(t->x < x) 405 { 406 ptt p = splitKey(t->r, x); 407 t->r = p.first; 408 return make_pair(fix(t), p.second); 409 } 410 else 411 { 412 ptt p = splitKey(t->l, x); 413 t->l = p.second; 414 return make_pair(p.first, fix(t)); 415 } 416 } 417 418 long long kthMax(treap t, int k) 419 { 420 t = fix(t); 421 if(!t) return -1; 422 int sumR = getSum(t->r); 423 if(sumR >= k) return kthMax(t->r, k); 424 if(sumR + t->cnt >= k) return t->x; 425 return kthMax(t->l, k - sumR - t->cnt); 426 } 427 428 int getCntByKey(treap t, long long x) 429 { 430 t = fix(t); 431 if(!t) return 0; 432 if(t->x == x) return t->cnt; 433 if(t->x > x) return getCntByKey(t->l, x); 434 return getCntByKey(t->r, x); 435 } 436 437 treap increaseKey(treap t, long long x, int cnt) 438 { 439 t = fix(t); 440 if(!t) return t; 441 if(t->x == x) 442 { 443 t->cnt += cnt; 444 } 445 else if(t->x > x) 446 { 447 t->l = increaseKey(t->l, x, cnt); 448 } 449 else 450 { 451 t->r = increaseKey(t->r, x, cnt); 452 } 453 return fix(t); 454 } 455 456 treap insert(treap t, long long x, int y, int cnt) 457 { 458 t = fix(t); 459 if(!t || t->y < y) 460 { 461 ptt p = splitKey(t, x); 462 treap res = new node(x, y, cnt, cnt, 0, p.first, p.second); 463 return fix(res); 464 } 465 if(t->x > x) 466 t->l = insert(t->l, x, y, cnt); 467 else 468 t->r = insert(t->r, x, y, cnt); 469 return fix(t); 470 } 471 472 treap insertMain(treap t, long long x, int cnt) 473 { 474 if(hasKey(t, x)) 475 return increaseKey(t, x, cnt); 476 else 477 return insert(t, x, rnd(), cnt); 478 } 479 480 treap eraseKey(treap t, long long x) 481 { 482 t = fix(t); 483 if(!t) return NULL; 484 if(t->x > x) 485 { 486 t->l = eraseKey(t->l, x); 487 return fix(t); 488 } 489 if(t->x < x) 490 { 491 t->r = eraseKey(t->r, x); 492 return fix(t); 493 } 494 treap tnew = merge(t->l, t->r); 495 delete t; 496 return tnew; 497 } 498 499 ptt splitSum(treap t, int k) 500 { 501 t = fix(t); 502 if(!t) return make_pair(t, t); 503 if(k == 0) return make_pair(t, treap(NULL)); 504 long long x = kthMax(t, k); 505 int cnt = getCntByKey(t, x); 506 t = eraseKey(t, x); 507 ptt p = splitKey(t, x); 508 k -= getSum(p.second); 509 if(k > 0) p.second = merge(new node(x, rnd(), k, k, 0, NULL, NULL), p.second); 510 if(k < cnt) p.first = merge(p.first, new node(x, rnd(), cnt - k, cnt - k, 0, NULL, NULL)); 511 return p; 512 } 513 514 long long minKey(treap t) 515 { 516 t = fix(t); 517 if(!t) return 1e18; 518 if(t->l) return minKey(t->l); 519 return t->x; 520 } 521 522 treap decreaseUpToKLargest(treap t, int k, int& res) 523 { 524 if(!k) return t; 525 t = fix(t); 526 k = min(k, getSum(t)); 527 res = k; 528 ptt p = splitSum(t, k); 529 if(p.second) 530 { 531 p.second->push--; 532 for(int i = 0; i < 2; i++) 533 { 534 long long x = minKey(p.second); 535 int cntMin = getCntByKey(p.second, x); 536 p.second = eraseKey(p.second, x); 537 if(x != 0 && cntMin != 0) 538 p.first = insertMain(p.first, x, cntMin); 539 } 540 } 541 return merge(p.first, p.second); 542 } 543 544 void destroy(treap t) 545 { 546 if(!t) return; 547 if(t->l) destroy(t->l); 548 if(t->r) destroy(t->r); 549 delete t; 550 } 551 552 void solve() 553 { 554 int n; 555 cin >> n; 556 string s; 557 cin >> s; 558 vector<long long> r(n), b(n); 559 for(int i = 0; i < n; i++) cin >> r[i]; 560 for(int i = 0; i < n; i++) cin >> b[i]; 561 long long sum = 0; 562 for(int i = 0; i < n; i++) sum += r[i] + b[i]; 563 long long flow = 0; 564 treap t = NULL; 565 for(int i = 0; i < n; i++) 566 { 567 long long d = min(r[i], b[i]); 568 flow += d; 569 r[i] -= d; 570 b[i] -= d; 571 if(s[i] == '0') 572 { 573 int add = 0; 574 if(r[i] > 1e9) r[i] = 1e9; 575 t = decreaseUpToKLargest(t, r[i], add); 576 flow += add; 577 } 578 else 579 { 580 if(r[i] != 0) t = insertMain(t, r[i], 1); 581 } 582 } 583 cout << sum - flow << endl; 584 } 585 586 int main() 587 { 588 ios_base::sync_with_stdio(0); 589 cin.tie(0); 590 int t; 591 cin >> t; 592 for(int i = 0; i < t; i++) solve(); 593 } 594 ```