961.md (11392B)
1 Source: https://codeforces.com/blog/entry/58743 2 3 [961A - Tetris](/contest/961/problem/A "Educational Codeforces Round 41 (Rated for Div. 2)") 4 5 **Editorial** 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 #ifdef _DEBUG 18 freopen("input.txt", "r", stdin); 19 // freopen("output.txt", "w", stdout); 20 #endif 21 22 int n, m; 23 cin >> n >> m; 24 vector<int> cnt(n); 25 26 for (int i = 0; i < m; ++i) { 27 int col; 28 cin >> col; 29 ++cnt[col - 1]; 30 } 31 32 cout << *min_element(cnt.begin(), cnt.end()) << endl; 33 34 return 0; 35 } 36 ``` 37 38 [961B - Lecture Sleep](/contest/961/problem/B "Educational Codeforces Round 41 (Rated for Div. 2)") 39 40 **Editorial** 41 42 Tutorial is loading... 43 44 **Solution (Vovuh)** 45 46 ``` 47 #include <bits/stdc++.h> 48 49 using namespace std; 50 51 int main() { 52 #ifdef _DEBUG 53 freopen("input.txt", "r", stdin); 54 // freopen("output.txt", "w", stdout); 55 #endif 56 57 int n, k; 58 scanf("%d %d", &n, &k); 59 60 vector<int> a(n); 61 vector<int> t(n); 62 63 int overall = 0; 64 65 for (int i = 0; i < n; ++i) 66 scanf("%d", &a[i]); 67 for (int i = 0; i < n; ++i) 68 scanf("%d", &t[i]); 69 70 vector<int> pr(n); 71 for (int i = 0; i < n; ++i) { 72 if (i) pr[i] += pr[i - 1]; 73 if (t[i] == 0) pr[i] += a[i]; 74 else overall += a[i]; 75 } 76 77 int add = 0; 78 for (int i = k - 1; i < n; ++i) 79 add = max(add, pr[i] - (i >= k ? pr[i - k] : 0)); 80 81 printf("%d\n", overall + add); 82 83 return 0; 84 } 85 ``` 86 87 [961C - Chessboard](/contest/961/problem/C "Educational Codeforces Round 41 (Rated for Div. 2)") 88 89 **Editorial** 90 91 Tutorial is loading... 92 93 **Solution (Ajosteen)** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 const int N = 109; 101 102 int n; 103 string a[4][N]; 104 105 int main() { 106 cin >> n; 107 for(int k = 0; k < 4; ++k) 108 for(int i = 0; i < n; ++i){ 109 cin >> a[k][i]; 110 for(int j = 0; j < n; ++j) 111 a[k][i][j] -= '0'; 112 } 113 114 vector <int> v; 115 for(int k = 0; k < 4; ++k){ 116 int sum = 0; 117 for(int i = 0; i < n; ++i) 118 for(int j = 0; j < n; ++j) 119 if((i + j) % 2 != a[k][i][j]) 120 ++sum; 121 v.push_back(sum); 122 } 123 124 int res = int(1e9); 125 vector <int> perm; 126 for(int k = 0; k < 4; ++k) perm.push_back(k); 127 do{ 128 int sum = 0; 129 for(int k = 0; k < 4; ++k){ 130 int id = perm[k]; 131 if(k & 1) 132 sum += v[id]; 133 else 134 sum += n * n - v[id]; 135 } 136 137 res = min(res, sum); 138 }while(next_permutation(perm.begin(), perm.end())); 139 140 cout << res << endl; 141 } 142 ``` 143 144 [961D - Pair Of Lines](/contest/961/problem/D "Educational Codeforces Round 41 (Rated for Div. 2)") 145 146 **Editorial** 147 148 Tutorial is loading... 149 150 **Solution (adedalic)** 151 152 ``` 153 #include <bits/stdc++.h> 154 155 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 156 157 #define all(a) (a).begin(), (a).end() 158 #define sz(a) int(a.size()) 159 #define mp make_pair 160 161 #define x first 162 #define y second 163 164 using namespace std; 165 166 typedef long long li; 167 typedef pair<int, int> pt; 168 169 inline pt operator -(const pt &a, const pt &b) { 170 return {a.x - b.x, a.y - b.y}; 171 } 172 173 inline li cross(const pt &a, const pt &b) { 174 return a.x * 1ll * b.y - a.y * 1ll * b.x; 175 } 176 177 const int N = 200 * 1000 + 555; 178 179 int n; 180 pt p[N]; 181 182 inline bool read() { 183 if(!(cin >> n)) 184 return false; 185 186 fore(i, 0, n) 187 scanf("%d%d", &p[i].x, &p[i].y); 188 return true; 189 } 190 191 bool used[N]; 192 193 bool check() { 194 int i1 = -1, i2 = -1; 195 fore(i, 0, n) { 196 if(used[i]) 197 continue; 198 if(i1 == -1) 199 i1 = i; 200 else if(i2 == -1) 201 i2 = i; 202 } 203 if(i2 == -1) 204 return true; 205 206 fore(i, 0, n) { 207 if(used[i]) 208 continue; 209 if(cross(p[i2] - p[i1], p[i] - p[i1]) != 0) 210 return false; 211 } 212 return true; 213 } 214 215 bool check2(pt a, pt b) { 216 memset(used, 0, sizeof used); 217 fore(i, 0, n) 218 if(cross(b - a, p[i] - a) == 0) 219 used[i] = 1; 220 return check(); 221 } 222 223 inline void solve() { 224 if(n <= 2) { 225 puts("YES"); 226 return; 227 } 228 229 if(check2(p[0], p[1]) || check2(p[0], p[2]) || check2(p[1], p[2])) 230 puts("YES"); 231 else 232 puts("NO"); 233 } 234 235 int main(){ 236 if(read()) { 237 solve(); 238 } 239 return 0; 240 } 241 ``` 242 243 [961E - Tufurama](/contest/961/problem/E "Educational Codeforces Round 41 (Rated for Div. 2)") 244 245 **Editorial** 246 247 Tutorial is loading... 248 249 **Solution (Ajosteen)** 250 251 ``` 252 #include <bits/stdc++.h> 253 254 using namespace std; 255 256 const int N = 200 * 1000 + 9; 257 258 int n; 259 int a[N]; 260 int f[N]; 261 vector <int> v[N]; 262 263 void upd(int pos, int d){ 264 for(; pos < N; pos |= pos + 1) 265 f[pos] += d; 266 } 267 268 int get(int pos){ 269 int res = 0; 270 for(; pos >= 0; pos = (pos & (pos + 1)) - 1) 271 res += f[pos]; 272 return res; 273 } 274 275 int main() { 276 scanf("%d", &n); 277 for(int i = 0; i < n; ++i){ 278 scanf("%d", a + i); 279 --a[i]; 280 } 281 282 for(int i = 0; i < n; ++i){ 283 if(a[i] < N) 284 v[a[i]].push_back(i); 285 upd(i, 1); 286 } 287 288 long long res = 0; 289 for(int i = 0; i < n; ++i){ 290 int to = min(N - 1, a[i]); 291 res += get(to); 292 for(auto x : v[i]) 293 upd(x, -1); 294 } 295 296 for(int i = 0; i < n; ++i) 297 if(i <= a[i]) 298 --res; 299 assert(res % 2 == 0); 300 301 cout << res / 2 << endl; 302 } 303 ``` 304 305 [961F - k-substrings](/contest/961/problem/F "Educational Codeforces Round 41 (Rated for Div. 2)") 306 307 **Editorial** 308 309 Tutorial is loading... 310 311 **Alternative solution (jtnydv25)** 312 313 Comment 314 315 **Solution (adedalic, suffix array)** 316 317 ``` 318 #include <bits/stdc++.h> 319 320 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 321 322 #define all(a) (a).begin(), (a).end() 323 #define sz(a) int(a.size()) 324 #define mp make_pair 325 326 #define x first 327 #define y second 328 329 using namespace std; 330 331 typedef pair<int, int> pt; 332 333 const int LOGN = 21; 334 const int N = 1000 * 1000 + 555; 335 336 int n; 337 string s; 338 339 inline bool read() { 340 if(!(cin >> n)) 341 return false; 342 343 char buf[N]; 344 assert(scanf("%s", buf) == 1); 345 s = buf; 346 return true; 347 } 348 349 pair<pt, int> d[N], curP[N]; 350 int szd = 0; 351 352 int cnt[N], szcnt; 353 int rdp[N]; 354 355 inline void radix_sort() { 356 fore(k, 0, 2) { 357 szcnt = 0; 358 fore(i, 0, szd) { 359 int val = k == 0 ? d[i].x.y : d[i].x.x; 360 while(szcnt <= val) 361 cnt[szcnt++] = 0; 362 cnt[val]++; 363 } 364 int sum = 0; 365 fore(i, 0, szcnt) { 366 rdp[i] = sum; 367 sum += cnt[i]; 368 } 369 370 fore(i, 0, szd) { 371 int val = k == 0 ? d[i].x.y : d[i].x.x; 372 curP[rdp[val]++] = d[i]; 373 } 374 fore(i, 0, szd) 375 d[i] = curP[i]; 376 } 377 } 378 379 int c[N], id[N]; 380 int lcp[N]; 381 382 int lg[N]; 383 int st[LOGN][N]; 384 385 void precalc() { 386 s += '$'; 387 for(int len = 1; len < 2 * sz(s); len <<= 1) { 388 szd = 0; 389 fore(i, 0, sz(s)) { 390 int sh = len >> 1; 391 d[szd++] = {len == 1 ? mp((int)s[i], 0) : mp(c[i], c[(i + sh) % sz(s)]), i}; 392 } 393 radix_sort(); 394 395 c[d[0].y] = 0; 396 fore(i, 1, szd) 397 c[d[i].y] = c[d[i - 1].y] + (d[i - 1].x != d[i].x); 398 399 if(c[d[szd - 1].y] == sz(s) - 1) 400 break; 401 } 402 403 fore(i, 0, sz(s)) { 404 c[i]--; 405 if(c[i] >= 0) id[c[i]] = i; 406 } 407 s.pop_back(); 408 409 int l = 0; 410 fore(i1, 0, n) { 411 l = max(l - 1, 0); 412 if(c[i1] == n - 1) 413 continue; 414 415 int i2 = id[c[i1] + 1]; 416 while(i1 + l < n && i2 + l < n && s[i1 + l] == s[i2 + l]) 417 l++; 418 lcp[c[i1]] = l; 419 } 420 421 lg[0] = 0; 422 fore(i, 1, N) { 423 lg[i] = lg[i - 1]; 424 if((1 << (lg[i] + 1)) <= i) 425 lg[i]++; 426 } 427 428 fore(pw, 0, LOGN) { 429 if(pw == 0) { 430 fore(i, 0, n) 431 st[pw][i] = lcp[i]; 432 continue; 433 } 434 fore(i, 0, n) { 435 st[pw][i] = st[pw - 1][i]; 436 if(i + (1 << (pw - 1)) < n) 437 st[pw][i] = min(st[pw][i], st[pw - 1][i + (1 << (pw - 1))]); 438 } 439 } 440 } 441 442 inline int getMin(int l, int r) { 443 if(l >= r) swap(l, r); 444 445 int len = lg[r - l]; 446 return min(st[len][l], st[len][r - (1 << len)]); 447 } 448 449 inline bool eq(int i1, int i2, int l) { 450 if(i1 == i2) return true; 451 return getMin(c[i1], c[i2]) >= l; 452 } 453 454 int l[N], mx[N]; 455 456 inline void solve() { 457 precalc(); 458 459 fore(i, 0, n / 2) { 460 int c1 = i, c2 = n - 1 - i; 461 if(s[c1] != s[c2]) { 462 l[i] = -1; 463 continue; 464 } 465 int lf = 0, rg = min(c1, n - 1 - c2) + 1; 466 while(rg - lf > 1) { 467 int mid = (lf + rg) >> 1; 468 469 if(eq(c1 - mid, c2 - mid, 2 * mid + 1)) 470 lf = mid; 471 else 472 rg = mid; 473 } 474 l[i] = lf; 475 } 476 477 fore(i, 0, n / 2) { 478 if(l[i] < 0) 479 continue; 480 mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1); 481 } 482 fore(i, 1, n / 2) 483 mx[i] = max(mx[i], mx[i - 1] - 2); 484 485 fore(i, 0, (n + 1) / 2) { 486 if(i) printf(" "); 487 printf("%d", mx[i] == 0 ? -1 : mx[i]); 488 } 489 puts(""); 490 } 491 492 int main(){ 493 if(read()) { 494 solve(); 495 } 496 return 0; 497 } 498 ``` 499 500 **Solution (adedalic, hashes)** 501 502 ``` 503 #include <bits/stdc++.h> 504 505 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 506 507 #define all(a) (a).begin(), (a).end() 508 #define sz(a) int(a.size()) 509 #define mp make_pair 510 511 #define x first 512 #define y second 513 514 using namespace std; 515 516 typedef long long li; 517 518 const li MOD = li(1e18) + 3; 519 const li BASE = 1009; 520 521 inline li norm(li a) { 522 while(a >= MOD) 523 a -= MOD; 524 while(a < 0) 525 a += MOD; 526 return a; 527 } 528 529 inline li mul(li a, li b) { 530 li m = ((long double)(a) * b) / MOD; 531 return norm(a * b - m * MOD); 532 } 533 534 const int N = 1000 * 1000 + 555; 535 536 int n; 537 string s; 538 539 inline bool read() { 540 if(!(cin >> n)) 541 return false; 542 543 char buf[N]; 544 assert(scanf("%s", buf) == 1); 545 s = buf; 546 return true; 547 } 548 549 li h[N], pw[N]; 550 551 inline void precalc() { 552 h[0] = 0; 553 fore(i, 0, n) 554 h[i + 1] = norm(mul(h[i], BASE) + s[i] - 'a' + 1); 555 556 pw[0] = 1; 557 fore(i, 1, N) 558 pw[i] = mul(pw[i - 1], BASE); 559 } 560 561 inline li getHash(int l, int r) { 562 return norm(h[r] - mul(h[l], pw[r - l])); 563 } 564 565 inline bool eq(int i1, int i2, int l) { 566 if(i1 == i2) return true; 567 return getHash(i1, i1 + l) == getHash(i2, i2 + l); 568 } 569 570 int l[N], mx[N]; 571 572 inline void solve() { 573 precalc(); 574 575 fore(i, 0, n / 2) { 576 int c1 = i, c2 = n - 1 - i; 577 if(s[c1] != s[c2]) { 578 l[i] = -1; 579 continue; 580 } 581 int lf = 0, rg = min(c1, n - 1 - c2) + 1; 582 while(rg - lf > 1) { 583 int mid = (lf + rg) >> 1; 584 585 if(eq(c1 - mid, c2 - mid, 2 * mid + 1)) 586 lf = mid; 587 else 588 rg = mid; 589 } 590 l[i] = lf; 591 } 592 593 fore(i, 0, n / 2) { 594 if(l[i] < 0) 595 continue; 596 mx[i - l[i]] = max(mx[i - l[i]], 2 * l[i] + 1); 597 } 598 fore(i, 1, n / 2) 599 mx[i] = max(mx[i], mx[i - 1] - 2); 600 601 fore(i, 0, (n + 1) / 2) { 602 if(i) printf(" "); 603 if(mx[i] == 0) mx[i] = -1; 604 printf("%d", mx[i]); 605 } 606 puts(""); 607 } 608 609 int main(){ 610 if(read()) { 611 solve(); 612 } 613 return 0; 614 } 615 ``` 616 617 [961G - Partitions](/contest/961/problem/G "Educational Codeforces Round 41 (Rated for Div. 2)") 618 619 **Editorial** 620 621 Tutorial is loading... 622 623 **Solution (adedalic)** 624 625 ``` 626 #include <bits/stdc++.h> 627 628 using namespace std; 629 630 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 631 #define forn(i, n) fore(i, 0, n) 632 633 const int MOD = int(1e9) + 7; 634 635 inline int norm(int a) { 636 while(a >= MOD) 637 a -= MOD; 638 while(a < 0) 639 a += MOD; 640 return a; 641 } 642 643 inline int mul(int a, int b) { 644 return int((a * 1ll * b) % MOD); 645 } 646 647 inline int binPow(int a, int k) { 648 int ans = 1; 649 while(k > 0) { 650 if(k & 1) ans = mul(ans, a); 651 a = mul(a, a); 652 k >>= 1; 653 } 654 return ans; 655 } 656 657 const int N = 200 * 1000 + 555; 658 659 int f[N], inf[N]; 660 661 void precalc() { 662 f[0] = inf[0] = 1; 663 fore(i, 1, N) { 664 f[i] = mul(f[i - 1], i); 665 inf[i] = mul(inf[i - 1], binPow(i, MOD - 2)); 666 } 667 } 668 669 int n, k, w[N]; 670 671 inline bool read() { 672 if(!(cin >> n >> k)) 673 return false; 674 forn(i, n) 675 cin >> w[i]; 676 return true; 677 } 678 679 inline int c(int n, int k) { 680 if(k > n || n < 0) return 0; 681 if(k == 0 || n == k) return 1; 682 683 return mul(f[n], mul(inf[n - k], inf[k])); 684 } 685 686 inline int s(int n, int k) { 687 if(n == 0) return k == 0; 688 if(k == 0) return n == 0; 689 690 int ans = 0, sg[2] = {1, MOD - 1}; 691 forn(cnt, k) 692 ans = norm(ans + mul(sg[cnt & 1], mul(c(k, cnt), binPow(k - cnt, n)))); 693 return mul(ans, inf[k]); 694 } 695 696 inline void solve() { 697 int sum = 0; 698 forn(i, n) 699 sum = norm(sum + w[i]); 700 701 int s0 = s(n, k); 702 int s1 = mul(n - 1, s(n - 1, k)); 703 704 cout << mul(sum, norm(s0 + s1)) << endl; 705 } 706 707 int main() { 708 #ifdef _DEBUG 709 freopen("input.txt", "r", stdin); 710 #endif 711 precalc(); 712 713 assert(read()); 714 solve(); 715 716 #ifdef _DEBUG 717 cerr << "TIME = " << clock() << endl; 718 #endif 719 return 0; 720 } 721 ```