985.md (10460B)
1 Source: https://codeforces.com/blog/entry/59623 2 3 [985A - Chess Placing](/contest/985/problem/A "Educational Codeforces Round 44 (Rated for Div. 2)") 4 5 **Tutorial** 6 7 Tutorial is loading... 8 9 **Solution (Vovuh)** 10 11 ``` 12 #include <bits/stdc++.h> 13 14 using namespace std; 15 16 int main() { 17 int n; 18 cin >> n; 19 vector<int> pos(n / 2); 20 for (int i = 0; i < n / 2; ++i) 21 cin >> pos[i]; 22 sort(pos.begin(), pos.end()); 23 24 int ans1 = 0, ans2 = 0; 25 for (int i = 0; i < n / 2; ++i) { 26 ans1 += abs(pos[i] - (i * 2 + 1)); 27 ans2 += abs(pos[i] - (i * 2 + 2)); 28 } 29 30 cout << min(ans1, ans2) << endl; 31 32 return 0; 33 } 34 ``` 35 36 [985B - Switches and Lamps](/contest/985/problem/B "Educational Codeforces Round 44 (Rated for Div. 2)") 37 38 **Tutorial** 39 40 Tutorial is loading... 41 42 **Solution (Vovuh)** 43 44 ``` 45 #include <bits/stdc++.h> 46 47 using namespace std; 48 49 int main() { 50 int n, m; 51 cin >> n >> m; 52 vector<string> s(n); 53 vector<int> cnt(m); 54 for (int i = 0; i < n; ++i) { 55 cin >> s[i]; 56 for (int j = 0; j < m; ++j) 57 if (s[i][j] == '1') ++cnt[j]; 58 } 59 60 for (int i = 0; i < n; ++i) { 61 bool ok = true; 62 for (int j = 0; j < m; ++j) { 63 if (s[i][j] == '1' && cnt[j] == 1) 64 ok = false; 65 } 66 if (ok) { 67 puts("YES"); 68 return 0; 69 } 70 } 71 72 puts("NO"); 73 74 return 0; 75 } 76 ``` 77 78 [985C - Liebig's Barrels](/contest/985/problem/C "Educational Codeforces Round 44 (Rated for Div. 2)") 79 80 **Tutorial** 81 82 Tutorial is loading... 83 84 **Solution (adedalic)** 85 86 ``` 87 #include<bits/stdc++.h> 88 89 using namespace std; 90 91 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 92 93 typedef long long li; 94 95 int n, k, l, m; 96 vector<li> a; 97 98 inline bool read() { 99 if(!(cin >> n >> k >> l)) 100 return false; 101 m = n * k; 102 a.assign(m, 0); 103 fore(i, 0, m) 104 assert(scanf("%lld", &a[i]) == 1); 105 return true; 106 } 107 108 inline void solve() { 109 sort(a.begin(), a.end()); 110 int rg = int(upper_bound(a.begin(), a.end(), a[0] + l) - a.begin()); 111 112 if(rg < n) { 113 puts("0"); 114 return; 115 } 116 li ans = 0; 117 118 int u = 0; 119 fore(i, 0, n) { 120 ans += a[u++]; 121 122 fore(j, 0, k - 1) { 123 if(rg - u > n - i - 1) 124 u++; 125 else 126 break; 127 } 128 } 129 cout << ans << endl; 130 } 131 132 int main() { 133 #ifdef _DEBUG 134 freopen("input.txt", "r", stdin); 135 int tt = clock(); 136 #endif 137 cerr << fixed << setprecision(15); 138 139 if(read()) { 140 solve(); 141 142 #ifdef _DEBUG 143 cerr << "TIME = " << clock() - tt << endl; 144 tt = clock(); 145 #endif 146 } 147 return 0; 148 } 149 ``` 150 151 [985D - Sand Fortress](/contest/985/problem/D "Educational Codeforces Round 44 (Rated for Div. 2)") 152 153 **Tutorial** 154 155 Tutorial is loading... 156 157 **Solution (PikMike)** 158 159 ``` 160 #include <bits/stdc++.h> 161 162 #define forn(i, n) for (int i = 0; i < int(n); i++) 163 164 typedef long long li; 165 166 using namespace std; 167 168 const int INF = 2e9; 169 li n, h; 170 171 bool check(li maxh){ 172 li k = min(h, maxh); 173 li cnt = maxh * maxh - k * (k - 1) / 2; 174 return (cnt <= n); 175 } 176 177 li get(li maxh){ 178 li k = min(h, maxh); 179 li cnt = maxh * maxh - k * (k - 1) / 2; 180 li len = (2 * maxh - 1) - (k - 1); 181 n -= cnt; 182 return len + (n + maxh - 1) / maxh; 183 } 184 185 int main() { 186 scanf("%lld%lld", &n, &h); 187 li l = 1, r = INF; 188 189 while (l < r - 1){ 190 li m = (l + r) / 2; 191 192 if (check(m)) 193 l = m; 194 else 195 r = m; 196 } 197 198 printf("%lld\n", check(r) ? get(r) : get(l)); 199 return 0; 200 } 201 ``` 202 203 [985E - Pencils and Boxes](/contest/985/problem/E "Educational Codeforces Round 44 (Rated for Div. 2)") 204 205 **Tutorial** 206 207 Tutorial is loading... 208 209 **Solution (PikMike)** 210 211 ``` 212 #include <bits/stdc++.h> 213 214 using namespace std; 215 216 #define forn(i, n) for(int i = 0; i < int(n); i++) 217 218 const int N = 500 * 1000 + 13; 219 220 int f[N]; 221 222 void upd(int x){ 223 for (int i = x; i < N; i |= i + 1) 224 ++f[i]; 225 } 226 227 int sum(int x){ 228 int res = 0; 229 for (int i = x; i >= 0; i = (i & (i + 1)) - 1) 230 res += f[i]; 231 return res; 232 } 233 234 int get(int l, int r){ 235 if (l > r) return 0; 236 return sum(r) - sum(l - 1); 237 } 238 239 int main(){ 240 int n, k, dif; 241 scanf("%d%d%d", &n, &k, &dif); 242 vector<int> a(n); 243 forn(i, n) 244 scanf("%d", &a[i]); 245 sort(a.begin(), a.end()); 246 247 vector<int> dp(n + 1, 0); 248 249 dp[0] = 1; 250 upd(0); 251 252 int l = 0; 253 forn(i, n){ 254 while (l < i && a[i] - a[l] > dif) 255 ++l; 256 dp[i + 1] = (get(l, i - k + 1) >= 1); 257 if (dp[i + 1]) upd(i + 1); 258 } 259 260 puts(dp[n] ? "YES" : "NO"); 261 } 262 ``` 263 264 [985F - Isomorphic Strings](/contest/985/problem/F "Educational Codeforces Round 44 (Rated for Div. 2)") 265 266 **Tutorial** 267 268 Tutorial is loading... 269 270 **Solution (adedalic)** 271 272 ``` 273 #include <bits/stdc++.h> 274 275 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 276 #define sz(a) int(a.size()) 277 278 #define x first 279 #define y second 280 281 using namespace std; 282 283 const int B = 2; 284 285 typedef array<int, B> ht; 286 287 ht MOD, BASE; 288 289 inline int norm(int a, const int &MOD) { 290 while(a >= MOD) 291 a -= MOD; 292 while(a < 0) 293 a += MOD; 294 return a; 295 } 296 297 inline int mul(int a, int b, const int &MOD) { 298 return int(a * 1ll * b % MOD); 299 } 300 301 inline ht operator +(const ht &a, const ht &b) { 302 ht ans; 303 fore(i, 0, sz(ans)) 304 ans[i] = norm(a[i] + b[i], MOD[i]); 305 return ans; 306 } 307 308 inline ht operator -(const ht &a, const ht &b) { 309 ht ans; 310 fore(i, 0, sz(ans)) 311 ans[i] = norm(a[i] - b[i], MOD[i]); 312 return ans; 313 } 314 315 inline ht operator *(const ht &a, const ht &b) { 316 ht ans; 317 fore(i, 0, sz(ans)) 318 ans[i] = mul(a[i], b[i], MOD[i]); 319 return ans; 320 } 321 322 int CMODS[] = {int(1e9) + 7, int(1e9) + 9, int(1e9) + 21, int(1e9) + 33, int(1e9) + 87, int(1e9) + 93, int(1e9) + 97, int(1e9) + 103}; 323 int CBASE[] = {1009, 1013, 1019, 1021}; 324 325 const int N = 200 * 1000 + 555; 326 327 int n, m; 328 char s[N]; 329 int x[N], y[N], len[N]; 330 331 inline bool read() { 332 if(!(cin >> n >> m)) 333 return false; 334 assert(scanf("%s", s) == 1); 335 336 fore(i, 0, m) { 337 assert(scanf("%d%d%d", &x[i], &y[i], &len[i]) == 3); 338 x[i]--, y[i]--; 339 } 340 return true; 341 } 342 void setMods() { 343 mt19937 rnd; 344 unsigned int seed = n; 345 fore(i, 0, n) 346 seed = (seed * 3) + s[i]; 347 fore(i, 0, m) { 348 seed = (seed * 3) + x[i]; 349 seed = (seed * 3) + y[i]; 350 seed = (seed * 3) + len[i]; 351 } 352 rnd.seed(seed); 353 354 set<int> mids; 355 while(sz(mids) < sz(MOD)) 356 mids.insert(rnd() % 8); 357 vector<int> vmids(mids.begin(), mids.end()); 358 fore(i, 0, sz(MOD)) { 359 MOD[i] = CMODS[vmids[i]]; 360 BASE[i] = CBASE[i]; 361 } 362 } 363 364 ht pBase[N]; 365 ht ph[27][N]; 366 vector<int> ord[N]; 367 368 ht getHash(int id, int l, int r) { 369 return ph[id][r] - ph[id][l] * pBase[r - l]; 370 } 371 372 inline void solve() { 373 setMods(); 374 375 pBase[0] = {1, 1}; 376 fore(i, 1, N) 377 pBase[i] = pBase[i - 1] * BASE; 378 379 fore(c, 0, 26) { 380 ph[c][0] = {0, 0}; 381 fore(i, 0, n) { 382 int val = (s[i] == c + 'a'); 383 ph[c][i + 1] = ph[c][i] * BASE + ht{val, val}; 384 } 385 } 386 387 vector<int> curOrd(26, 0); 388 iota(curOrd.begin(), curOrd.end(), 0); 389 for(int i = n - 1; i >= 0; i--) { 390 ord[i] = curOrd; 391 auto it = find(ord[i].begin(), ord[i].end(), int(s[i] - 'a')); 392 ord[i].erase(it); 393 ord[i].insert(ord[i].begin(), int(s[i] - 'a')); 394 curOrd = ord[i]; 395 } 396 397 fore(q, 0, m) { 398 int s1 = x[q], s2 = y[q]; 399 bool ok = true; 400 401 fore(i, 0, 26) { 402 if(getHash(ord[s1][i], s1, s1 + len[q]) != 403 getHash(ord[s2][i], s2, s2 + len[q])) { 404 ok = false; 405 break; 406 } 407 } 408 puts(ok ? "YES" : "NO"); 409 } 410 } 411 412 int main(){ 413 #ifdef _DEBUG 414 freopen("input.txt", "r", stdin); 415 //freopen("output.txt", "w", stdout); 416 #endif 417 if(read()) { 418 solve(); 419 } 420 return 0; 421 } 422 ``` 423 424 [985G - Team Players](/contest/985/problem/G "Educational Codeforces Round 44 (Rated for Div. 2)") 425 426 **Tutorial** 427 428 Tutorial is loading... 429 430 **Solution (adedalic)** 431 432 ``` 433 #include <bits/stdc++.h> 434 435 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 436 #define sz(a) int(a.size()) 437 438 using namespace std; 439 440 typedef unsigned long long uli; 441 442 const int N = 200 * 1000 + 555; 443 444 int n, m; 445 uli a, b, c; 446 vector<int> g[N]; 447 448 inline bool read() { 449 if(!(cin >> n >> m)) 450 return false; 451 assert(cin >> a >> b >> c); 452 fore(i, 0, m) { 453 int u, v; 454 assert(scanf("%d%d", &u, &v) == 2); 455 456 g[u].push_back(v); 457 g[v].push_back(u); 458 } 459 return true; 460 } 461 462 vector<uli> ps[N]; 463 464 inline uli getSum(int v, int l, int r) { 465 return ps[v][r] - ps[v][l]; 466 } 467 468 const int MX = 700; 469 int id[N]; 470 471 const int B = 1111; 472 bitset<N> has[B]; 473 int szh = 0; 474 475 inline void solve() { 476 memset(id, -1, sizeof id); 477 szh = 0; 478 fore(v, 0, n) { 479 sort(g[v].begin(), g[v].end()); 480 481 ps[v].assign(sz(g[v]) + 1, 0); 482 fore(i, 0, sz(g[v])) 483 ps[v][i + 1] = ps[v][i] + g[v][i]; 484 485 if(sz(g[v]) >= MX) { 486 assert(szh < B); 487 id[v] = szh++; 488 489 for(int to : g[v]) 490 has[id[v]][to] = 1; 491 } 492 } 493 494 uli all = 0; 495 fore(v, 0, n) { 496 uli lw = v, gr = n - v - 1; 497 all += a * v * (gr * (gr - 1) / 2); 498 all += b * v * (lw * gr); 499 all += c * v * (lw * (lw - 1) / 2); 500 } 501 502 uli sub1 = 0; 503 fore(v, 0, n) { 504 for(int to : g[v]) { 505 if(to > v) 506 break; 507 508 uli cnt = to; 509 uli sum = cnt * (cnt - 1) / 2; 510 sub1 += a * sum + cnt * (b * to + c * v); 511 512 cnt = v - to - 1; 513 sum = (2 * to + cnt + 1) * cnt / 2; 514 sub1 += b * sum + cnt * (a * to + c * v); 515 } 516 517 uli sum = 0; 518 fore(i, 0, sz(g[v])) { 519 if(g[v][i] > v) 520 break; 521 522 uli cnt = i; 523 sub1 -= a * sum + cnt * (b * g[v][i] + c * v); 524 sum += g[v][i]; 525 } 526 } 527 all -= sub1; 528 529 uli sub2 = 0; 530 uli cntE = 0, sumE = 0; 531 fore(v, 0, n) { 532 sub2 += sumE + cntE * c * v; 533 for(int to : g[v]) { 534 if(to > v) 535 break; 536 537 cntE++; 538 sumE += a * to + b * v; 539 } 540 } 541 542 fore(v, 0, n) { 543 for(int to : g[v]) { 544 if(to > v) 545 break; 546 547 int pos = int(lower_bound(g[to].begin(), g[to].end(), to) - g[to].begin()); 548 sub2 -= a * getSum(to, 0, pos) + pos * (b * to + c * v); 549 550 int pos2 = int(lower_bound(g[to].begin(), g[to].end(), v) - g[to].begin()); 551 sub2 -= b * getSum(to, pos, pos2) + (pos2 - pos) * (a * to + c * v); 552 } 553 } 554 555 vector<char> curh(n + 5, 0); 556 fore(v, 0, n) { 557 if(id[v] == -1) { 558 fore(i2, 0, sz(g[v])) { 559 int u2 = g[v][i2]; 560 if(u2 > v) 561 break; 562 563 if(id[u2] != -1) { 564 fore(i1, 0, i2) { 565 int u1 = g[v][i1]; 566 if(has[id[u2]][u1]) 567 sub2 += a * u1 + b * u2 + c * v; 568 } 569 } else { 570 for(int to : g[u2]) { 571 if(to > u2) 572 break; 573 curh[to] = 1; 574 } 575 fore(i1, 0, i2) { 576 int u1 = g[v][i1]; 577 if(curh[u1]) 578 sub2 += a * u1 + b * u2 + c * v; 579 } 580 for(int to : g[u2]) { 581 if(to > u2) 582 break; 583 curh[to] = 0; 584 } 585 } 586 } 587 } else { 588 fore(u2, 0, v) { 589 if(!has[id[v]][u2]) 590 continue; 591 for(int u1 : g[u2]) { 592 if(u1 > u2) 593 break; 594 if(has[id[v]][u1]) 595 sub2 += a * u1 + b * u2 + c * v; 596 } 597 } 598 } 599 } 600 all -= sub2; 601 cout << all << endl; 602 } 603 604 int main(){ 605 #ifdef _DEBUG 606 freopen("input.txt", "r", stdin); 607 int tt = clock(); 608 #endif 609 cout << fixed << setprecision(10); 610 611 if(read()) { 612 solve(); 613 #ifdef _DEBUG 614 cerr << "TIME = " << clock() - tt << endl; 615 #endif 616 } 617 return 0; 618 } 619 ```