1835.md (24440B)
1 Source: https://codeforces.com/blog/entry/117394 2 3 [1836A - Destroyer](/contest/1836/problem/A "Codeforces Round 880 (Div. 2)") 4 5 * Author: [kempusss](/profile/kempusss "Master kempusss") 6 * Developer: [kempusss](/profile/kempusss "Master kempusss") 7 * First solve: [Goonless](/profile/Goonless "Specialist Goonless") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 const int N = 1e6; 20 21 int main() 22 { 23 int cases; 24 scanf("%d", &cases); 25 26 while (cases--) { 27 int n; 28 scanf ("%d", &n); 29 30 vector <int> cnt(n + 1); 31 for (int i = 0; i < n; i++) { 32 int d; 33 scanf("%d", &d); 34 if (d < n) { 35 cnt[d]++; 36 } else { 37 cnt[n] = N; 38 } 39 } 40 41 bool good = true; 42 for (int i = 1; i <= n; i++) if (cnt[i] > cnt[i-1]) { 43 good = false; 44 break; 45 } 46 47 puts(good ? "YES" : "NO"); 48 } 49 } 50 ``` 51 52 [1836B - Astrophysicists](/contest/1836/problem/B "Codeforces Round 880 (Div. 2)") 53 54 * Author: [Fly_37](/profile/Fly_37 "Master Fly_37") 55 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 56 * First solve: [NTR_Lover](/profile/NTR_Lover "Specialist NTR_Lover") 57 58 **Tutorial** 59 60 Tutorial is loading... 61 62 **Solution** 63 64 ``` 65 #include "bits/stdc++.h" 66 using namespace std; 67 68 int main() 69 { 70 int t; 71 scanf ("%d", &t); 72 while (t--) { 73 long long n, k, g; 74 scanf ("%lld %lld %lld", &n, &k, &g); 75 76 long long stolen = min((g - 1) / 2 * n, k * g); 77 long long rest = (k * g - stolen) % g; 78 79 if (rest > 0) { 80 stolen -= (g - 1) / 2; 81 long long last = ((g - 1) / 2 + rest) % g; 82 83 if (last * 2 < g) { 84 stolen += last; 85 } else { 86 stolen -= g - last; 87 } 88 } 89 90 printf ("%lld\n", stolen); 91 } 92 } 93 ``` 94 95 [1836C - k-th equality](/contest/1836/problem/C "Codeforces Round 880 (Div. 2)") / [1835A - k-th equality](/contest/1835/problem/A "Codeforces Round 880 (Div. 1)") 96 97 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 98 * Developer: [w0nsh](/profile/w0nsh "Grandmaster w0nsh") 99 * First solve: [NTR_Lover](/profile/NTR_Lover "Specialist NTR_Lover") / [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") 100 101 **Tutorial** 102 103 Tutorial is loading... 104 105 **Solution** 106 107 ``` 108 #include <bits/stdc++.h> 109 110 int power(int a, int e) { 111 if (e == 0) return 1; 112 return e == 1 ? a : a * power(a, e-1); 113 } 114 115 void answer(int a, int b) { 116 std::cout << a << " + " << b << " = " << a+b << std::endl; 117 } 118 119 int main() { 120 using ll = long long; 121 122 int t; 123 std::cin >> t; 124 while (t--) { 125 126 int a, b, c; 127 ll k; 128 std::cin >> a >> b >> c >> k; 129 130 bool good = false; 131 132 for (int i = power(10, a-1); i < power(10, a); ++i) { 133 int left = std::max(power(10, b-1), power(10, c-1) - i); 134 int right = std::min(power(10, b)-1, power(10, c) - 1 - i); 135 if (left > right) continue; 136 137 int have = right - left + 1; 138 if (k <= have) { 139 answer(i, left + k - 1); 140 good = true; 141 break; 142 } 143 144 k -= have; 145 } 146 147 if (!good) std::cout << "-1" << std::endl; 148 } 149 150 return 0; 151 } 152 ``` 153 154 [1836D - Lottery](/contest/1836/problem/D "Codeforces Round 880 (Div. 2)") / [1835B - Lottery](/contest/1835/problem/B "Codeforces Round 880 (Div. 1)") 155 156 * Author: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990") 157 * Developer: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990") 158 * First solve: [Nobody.Emissary](/profile/Nobody.Emissary "Newbie Nobody.Emissary") / [ecnerwala](/profile/ecnerwala "Legendary Grandmaster ecnerwala") 159 160 **Tutorial** 161 162 Tutorial is loading... 163 164 **Solution** 165 166 ``` 167 #include <bits/stdc++.h> 168 169 #define forr(i, n) for (int i = 0; i < n; i++) 170 #define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter) 171 #define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter) 172 #define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; }) 173 #define testy() \ 174 int _tests; \ 175 cin >> _tests; \ 176 FOR(_test, 1, _tests) 177 #define CLEAR(tab) memset(tab, 0, sizeof(tab)) 178 #define CONTAIN(el, coll) (coll.find(el) != coll.end()) 179 #define FOR(i, a, b) for (int i = a; i <= b; i++) 180 #define FORD(i, a, b) for (int i = a; i >= b; i--) 181 #define MP make_pair 182 #define PB push_back 183 #define ff first 184 #define ss second 185 #define deb(X) X; 186 #define SIZE(coll) ((int)coll.size()) 187 188 #define M 1000000007 189 #define INF 1000000007LL 190 191 using namespace std; 192 193 long long n, m, k; 194 long long poz_l, poz_p; 195 vector<long long> v; 196 197 long long policz_ile(long long strzal) 198 { 199 while (poz_l < n && v[poz_l] < strzal) 200 poz_l++; 201 while (poz_p < n && v[poz_p] <= strzal) 202 poz_p++; 203 204 long long pocz = poz_p < k ? 0 : (strzal + v[poz_p - k]) / 2 + 1; 205 long long kon = poz_l + k - 1 >= n ? m : (v[poz_l + k - 1] + strzal - 1) / 2; 206 207 return max(0ll, kon - pocz + 1); 208 } 209 210 int solve() 211 { 212 cin >> n >> m >> k; 213 long long a; 214 forr(i, n) 215 { 216 cin >> a; 217 v.PB(a); 218 } 219 sort(v.begin(), v.end()); 220 v.PB(m + 1); 221 long long res = policz_ile(0), best = 0; 222 forr(i, n) 223 { 224 long long pocz = i == 0 ? max(0ll, v[i] - 2) : max(v[i] - 2, v[i - 1] + 3); 225 long long kon = min(m, v[i] + 2); 226 for (long long s = pocz; s <= kon; s++) 227 { 228 long long ile = policz_ile(s); 229 230 if (ile > res) 231 { 232 res = ile; 233 best = s; 234 } 235 } 236 } 237 cout << res << " " << best << '\n'; 238 239 return 0; 240 } 241 242 int main() 243 { 244 std::ios_base::sync_with_stdio(0); 245 cin.tie(0); 246 cout.tie(0); 247 248 solve(); 249 250 return 0; 251 } 252 ``` 253 254 [1836E - Twin Clusters](/contest/1836/problem/E "Codeforces Round 880 (Div. 2)") / [1835C - Twin Clusters](/contest/1835/problem/C "Codeforces Round 880 (Div. 1)") 255 256 * Author: [Anadi](/profile/Anadi "International Grandmaster Anadi"), [w0nsh](/profile/w0nsh "Grandmaster w0nsh") 257 * Developer: [Fly_37](/profile/Fly_37 "Master Fly_37") 258 * First solve: [GULAL_S_ZHENOY_UMNIKA](/profile/GULAL_S_ZHENOY_UMNIKA "Specialist GULAL_S_ZHENOY_UMNIKA") / [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik") 259 260 **Tutorial** 261 262 Tutorial is loading... 263 264 **Solution** 265 266 ``` 267 #include <bits/stdc++.h> 268 269 using namespace std; 270 271 void solve() 272 { 273 int k, n; 274 scanf("%d", &k); 275 276 n = 2 << k; 277 278 vector <long long> input(n + 1); 279 vector <int> memHighBits(1 << k, -1); 280 vector <pair <int, int> > memLowBits(1 << k, {-1, -1}); 281 282 auto addInterval = [&memLowBits, &input](int s, int e) { 283 const int remXor = input[e] ^ input[s - 1]; 284 auto &[os, oe] = memLowBits[remXor]; 285 286 if (os == -1) { 287 os = s, oe = e; 288 return false; 289 } 290 291 if (oe < s) { 292 printf("%d %d %d %d\n", os, oe, s, e); 293 } else { 294 printf("%d %d %d %d\n", min(s, os), max(s, os) - 1, oe + 1, e); 295 } 296 297 return true; 298 }; 299 300 memHighBits[0] = 0; 301 for (int i = 1; i <= n; ++i) { 302 scanf("%lld", &input[i]); 303 input[i] ^= input[i - 1]; 304 } 305 306 for (int i = 1; i <= n; ++i) { 307 if (memHighBits[input[i] >> k] != -1) { 308 if (addInterval(memHighBits[input[i] >> k] + 1, i)) { 309 break; 310 } 311 } 312 313 memHighBits[input[i] >> k] = i; 314 } 315 } 316 317 int main() 318 { 319 int cases; 320 scanf("%d", &cases); 321 322 while (cases--) { 323 solve(); 324 } 325 326 return 0; 327 } 328 ``` 329 330 [1836F - Doctor's Brown Hypothesis](/contest/1836/problem/F "Codeforces Round 880 (Div. 2)") / [1835D - Doctor's Brown Hypothesis](/contest/1835/problem/D "Codeforces Round 880 (Div. 1)") 331 332 * Author: [Okrut](/profile/Okrut "Grandmaster Okrut") 333 * Developer: [Okrut](/profile/Okrut "Grandmaster Okrut") 334 * First solve: None / [ksun48](/profile/ksun48 "Legendary Grandmaster ksun48") 335 336 **Tutorial** 337 338 Tutorial is loading... 339 340 **Solution** 341 342 ``` 343 #include<bits/stdc++.h> 344 using namespace std; 345 346 #define sz(s) (int)s.size() 347 #define all(s) s.begin(), s.end() 348 #define pb push_back 349 #define FOR(i, n) for(int i = 0; i < n; i++) 350 351 using vi = vector<int>; 352 using vvi = vector<vi>; 353 354 struct SCC { 355 int cnt = 0; 356 vi vis, scc_nr; 357 vvi scc_list, DAG; 358 359 SCC(){} 360 361 SCC(vvi & G){ 362 // G is 0 indexed! 363 int n = sz(G); 364 vvi G_rev(n); 365 vis = scc_nr = vi(n); 366 367 vi postorder; 368 for(int i = 0; i < n; i++) 369 if(!vis[i]) 370 dfs_post(i, G, G_rev, postorder); 371 372 vis = vi(n); 373 while(sz(postorder)){ 374 auto akt = postorder.back(); 375 postorder.pop_back(); 376 if(!vis[akt]){ 377 DAG.emplace_back(); 378 scc_list.emplace_back(); 379 dfs_rev(akt, G_rev); 380 cnt++; 381 } 382 } 383 384 // optional 385 for(int i = 0; i < sz(DAG); i++){ 386 sort(all(DAG[i])); 387 DAG[i].resize(unique(all(DAG[i])) - DAG[i].begin()); 388 } 389 } 390 391 void dfs_post(int start, vvi & G, vvi & G_rev, vi & postorder){ 392 vis[start] = 1; 393 for(auto & u : G[start]){ 394 G_rev[u].pb(start); 395 if(!vis[u]) 396 dfs_post(u, G, G_rev, postorder); 397 } 398 399 postorder.pb(start); 400 } 401 402 void dfs_rev(int start, vvi & G_rev){ 403 vis[start] = true; 404 scc_list.back().pb(start); 405 scc_nr[start] = cnt; 406 407 for(auto & u : G_rev[start]) 408 if(!vis[u]) 409 dfs_rev(u, G_rev); 410 else if(scc_nr[u] != cnt) 411 DAG[scc_nr[u]].pb(cnt); 412 } 413 }; 414 415 int main() 416 { 417 ios::sync_with_stdio(0); 418 cin.tie(0); 419 420 long long n, m, k; 421 cin >> n >> m >> k; 422 423 vvi G(n); 424 425 set<pair<int, int>> edges; 426 for (int i = 0; i < m; i++) 427 { 428 int a, b; 429 cin >> a >> b; 430 a--, b--; 431 G[a].pb(b); 432 edges.insert({a, b}); 433 } 434 435 SCC scc(G); 436 vi coloring(n, -1); 437 438 auto try_coloring = [&](int num_col, const vi& group) 439 { 440 vi visited; 441 function<bool(int)> dfs = [&](int start){ 442 visited.pb(start); 443 444 bool good_coloring = true; 445 for (auto & u : G[start]) 446 { 447 if (scc.scc_nr[u] != scc.scc_nr[start]) 448 { 449 continue; 450 } 451 if (coloring[u] == -1) 452 { 453 coloring[u] = (coloring[start] + 1) % num_col; 454 good_coloring &= dfs(u); 455 } 456 else 457 { 458 good_coloring &= coloring[u] == (coloring[start] + 1) % num_col; 459 } 460 461 if (not good_coloring) 462 { 463 break; 464 } 465 } 466 467 return good_coloring; 468 }; 469 470 coloring[group[0]] = 0; 471 if (not dfs(group[0])) 472 { 473 for (auto & u : visited) 474 { 475 coloring[u] = -1; 476 } 477 return vvi(); 478 } 479 else 480 { 481 vvi ret(num_col); 482 for (auto & u : visited) 483 { 484 ret[coloring[u]].push_back(u); 485 } 486 return ret; 487 } 488 }; 489 490 long long ans = 0; 491 vi depths(n, -1); 492 493 for (vi& group : scc.scc_list) 494 { 495 n = sz(group); 496 497 if (n == 1 and edges.count({group[0], group[0]}) == 0) 498 { 499 continue; 500 } 501 int gcd = -1; 502 function<void(int)> dfs_depths = [&](int start) 503 { 504 for (auto & u : G[start]) 505 { 506 if (scc.scc_nr[u] != scc.scc_nr[start]) 507 { 508 continue; 509 } 510 511 if (depths[u] == -1) 512 { 513 depths[u] = depths[start] + 1; 514 dfs_depths(u); 515 } 516 else { 517 int diff = abs(depths[u] - (depths[start] + 1)); 518 if (diff) 519 { 520 if (gcd == -1) 521 { 522 gcd = diff; 523 } 524 else 525 { 526 gcd = __gcd(gcd, diff); 527 } 528 } 529 } 530 } 531 }; 532 533 depths[group[0]] = 0; 534 dfs_depths(group[0]); 535 assert(gcd != -1); 536 537 vvi by_color = try_coloring(gcd, group); 538 539 assert(sz(by_color) != 0); 540 if (k % gcd == 0) 541 { 542 FOR (i, gcd) 543 { 544 ans += sz(by_color[i]) + 1ll * sz(by_color[i]) * (sz(by_color[i]) - 1) / 2; 545 } 546 } 547 else if (k % gcd * 2 == gcd) 548 { 549 FOR (i, gcd / 2) 550 { 551 ans += 1ll * sz(by_color[i]) * sz(by_color[i + gcd / 2]); 552 } 553 } 554 } 555 cout << ans << '\n'; 556 } 557 ``` 558 559 [1835E - Old Mobile](/contest/1835/problem/E "Codeforces Round 880 (Div. 1)") 560 561 * Author: [Fly_37](/profile/Fly_37 "Master Fly_37") 562 * Developer: [maras](/profile/maras "Master maras") 563 * First solve: [tourist](/profile/tourist "Legendary Grandmaster tourist") 564 565 **Tutorial** 566 567 Tutorial is loading... 568 569 **Solution** 570 571 ``` 572 #include <bits/stdc++.h> 573 574 using namespace std; 575 576 constexpr int MAX_M = 1000 + 7; 577 constexpr int PRECISION = 9; 578 constexpr long long MOD = 1e9 + 7; 579 580 long long mod_inv[MAX_M]; 581 long long DP[MAX_M][MAX_M][2][2]; 582 long long DPprob[MAX_M][MAX_M][2][2]; 583 bool updated[MAX_M][MAX_M][2][2]; 584 // DP[correct][incorrect][backspace][bad suffix] 585 586 long long calc_mod_inv(long long n) 587 { 588 long long res = 1; 589 long long exp = MOD - 2; 590 591 while (exp) 592 { 593 if (exp & 1) 594 { 595 res = (res * n) % MOD; 596 } 597 598 exp >>= 1; 599 n = (n * n) % MOD; 600 } 601 602 return res; 603 } 604 605 void calc_DP(int digits, int needed) 606 { 607 DP[0][0][0][0] = 0; 608 DPprob[0][0][0][0] = 1; 609 610 struct ID 611 { 612 int x, y, z, s; 613 }; 614 615 queue <ID> dp_queue; 616 dp_queue.push({0, 0, 0, 0}); 617 618 while(!dp_queue.empty()) 619 { 620 auto [x, y, z, s] = dp_queue.front(); 621 dp_queue.pop(); 622 623 if (updated[x][y][z][s]) 624 { 625 continue; 626 } 627 628 updated[x][y][z][s] = true; 629 630 long long left = digits + 1 - x - y - z; 631 long long corr = needed - x; 632 long long incorr = digits - needed - y; 633 long long prob = DPprob[x][y][z][s]; 634 635 if (corr == 0 and s == 0) 636 { 637 // done 638 continue; 639 } 640 641 // correct suffix 642 if (s == 0) 643 { 644 if (corr > 0) 645 { 646 // found the one correct digit (no need to delete) 647 long long opt_prob = (prob * mod_inv[left]) % MOD; 648 DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD; 649 DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + DP[x][y][z][0] * mod_inv[left]) % MOD; 650 651 // found a needed but currently wrong digit (needs to be deleted) 652 if (corr > 1) 653 { 654 if (z == 0) // if backspace is not known, the suffix is bad 655 { 656 long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD; 657 DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD; 658 659 DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD; 660 dp_queue.push({x + 1, y, z, 1}); 661 } 662 else // if backspace is known, the suffix can be instantly repaired 663 { 664 long long opt_prob = ((prob * (corr - 1) % MOD) * mod_inv[left]) % MOD; 665 DPprob[x + 1][y][z][0] = (DPprob[x + 1][y][z][0] + opt_prob) % MOD; 666 DP[x + 1][y][z][0] = (DP[x + 1][y][z][0] + ((corr - 1) * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD; 667 } 668 } 669 670 dp_queue.push({x + 1, y, z, 0}); 671 } 672 673 if (incorr > 0) 674 { 675 // found an incorrect digit 676 if (z == 0) 677 { 678 long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD; 679 DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD; 680 DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD; 681 dp_queue.push({x, y + 1, z, 1}); 682 } 683 else // suffix can be repaired 684 { 685 long long opt_prob = ((prob * incorr % MOD) * mod_inv[left]) % MOD; 686 DPprob[x][y + 1][z][0] = (DPprob[x][y + 1][z][0] + opt_prob) % MOD; 687 DP[x][y + 1][z][0] = (DP[x][y + 1][z][0] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][0] + 2 * opt_prob) % MOD; 688 dp_queue.push({x, y + 1, z, 0}); 689 } 690 } 691 692 if (z == 0) 693 { 694 if (x > 0) // deleted correct digit 695 { 696 long long opt_prob = prob * mod_inv[left] % MOD; 697 DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD; 698 DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + 2 * opt_prob) % MOD; 699 } 700 else // deleted nothing 701 { 702 long long opt_prob = prob * mod_inv[left] % MOD; 703 DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD; 704 DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][0] + opt_prob) % MOD; 705 } 706 707 dp_queue.push({x, y, 1, 0}); 708 } 709 } 710 711 if (s == 1) 712 { 713 if (corr > 0) 714 { 715 // found a needed but currently wrong digit (needs to be deleted) 716 long long opt_prob = (prob * corr % MOD) * mod_inv[left] % MOD; 717 DPprob[x + 1][y][z][1] = (DPprob[x + 1][y][z][1] + opt_prob) % MOD; 718 DP[x + 1][y][z][1] = (DP[x + 1][y][z][1] + (corr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD; 719 dp_queue.push({x + 1, y, z, 1}); 720 } 721 722 if (incorr > 0) 723 { 724 // found an incorrect digit 725 long long opt_prob = (prob * incorr % MOD) * mod_inv[left] % MOD; 726 DPprob[x][y + 1][z][1] = (DPprob[x][y + 1][z][1] + opt_prob) % MOD; 727 DP[x][y + 1][z][1] = (DP[x][y + 1][z][1] + (incorr * mod_inv[left] % MOD) * DP[x][y][z][1] + 2 * opt_prob) % MOD; 728 dp_queue.push({x, y + 1, z, 1}); 729 } 730 731 if (z == 0) 732 { 733 // deleted bad suffix 734 long long opt_prob = prob * mod_inv[left] % MOD; 735 DPprob[x][y][1][0] = (DPprob[x][y][1][0] + opt_prob) % MOD; 736 DP[x][y][1][0] = (DP[x][y][1][0] + mod_inv[left] * DP[x][y][0][1]) % MOD; 737 dp_queue.push({x, y, 1, 0}); 738 } 739 } 740 } 741 } 742 743 int main() 744 { 745 ios::sync_with_stdio(0); 746 cin.tie(0); 747 cout.tie(0); 748 749 mod_inv[0] = 1; 750 for (int i = 1; i < MAX_M; ++i) { 751 mod_inv[i] = calc_mod_inv(i); 752 assert (mod_inv[i] * i % MOD == 1); 753 } 754 755 int n, m; 756 cin >> n >> m; 757 758 set <int> different_digits; 759 760 for (int i = 0; i < n; ++i) 761 { 762 int p; 763 cin >> p; 764 765 different_digits.insert(p); 766 } 767 768 int needed = different_digits.size(); 769 770 calc_DP(m, needed); 771 772 long long result = 0; 773 774 for (int i = 0; i <= MAX_M; ++i) 775 { 776 result = (result + DP[needed][i][0][0]) % MOD; 777 result = (result + DP[needed][i][1][0]) % MOD; 778 } 779 780 cout << (result + n) % MOD << "\n"; 781 782 return 0; 783 } 784 ``` 785 786 [1835F - Good Graph](/contest/1835/problem/F "Codeforces Round 880 (Div. 1)") 787 788 * Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 789 * Developer: [Arti1990](/profile/Arti1990 "Candidate Master Arti1990") 790 * First solve: [rainboy](/profile/rainboy "Candidate Master rainboy") 791 792 **Tutorial** 793 794 Tutorial is loading... 795 796 **Solution** 797 798 ``` 799 #include <bits/stdc++.h> 800 801 #define forr(i, n) for (int i = 0; i < n; i++) 802 #define FOREACH(iter, coll) for (auto iter = coll.begin(); iter != coll.end(); ++iter) 803 #define FOREACHR(iter, coll) for (auto iter = coll.rbegin(); iter != coll.rend(); ++iter) 804 #define lbound(P, K, FUN) ({auto SSS=P, PPP = P-1, KKK=(K)+1; while(PPP+1!=KKK) {SSS = (PPP+(KKK-PPP)/2); if(FUN(SSS)) KKK = SSS; else PPP = SSS;} PPP; }) 805 #define testy() \ 806 int _tests; \ 807 cin >> _tests; \ 808 FOR(_test, 1, _tests) 809 #define CLEAR(tab) memset(tab, 0, sizeof(tab)) 810 #define CONTAIN(el, coll) (coll.find(el) != coll.end()) 811 #define FOR(i, a, b) for (int i = a; i <= b; i++) 812 #define FORD(i, a, b) for (int i = a; i >= b; i--) 813 #define MP make_pair 814 #define PB push_back 815 #define ff first 816 #define ss second 817 #define deb(X) X; 818 #define SIZE(coll) ((int)coll.size()) 819 820 using namespace std; 821 822 const int MXN = 1007; 823 int n, m; 824 vector<int> G[MXN]; 825 bitset<MXN> bs[MXN], edge[MXN]; 826 827 // MATCHING 828 829 const int MXM = 1007 * 2; 830 int skojX[MXM], skojY[MXM]; 831 bool vis[MXM]; 832 833 bool dfs_m(int x) 834 { 835 vis[x] = 1; 836 FOREACH(it, G[x]) 837 if (!skojY[*it] || (!vis[skojY[*it]] && dfs_m(skojY[*it]))) 838 { 839 skojX[x] = *it; 840 skojY[*it] = x; 841 return 1; 842 } 843 return 0; 844 } 845 846 bool skoj() 847 { 848 int czy = 1; 849 int res = 0; 850 while (czy) 851 { 852 czy = 0; 853 CLEAR(vis); 854 FOR(i, 1, n) 855 if (!vis[i] && !skojX[i] && dfs_m(i)) 856 { 857 czy = 1; 858 res++; 859 } 860 } 861 return res == n; 862 } 863 864 // END OF MATCHING 865 866 void dfs(int nr, bitset<MXN> &visited, bitset<MXN> &to_visit) 867 { 868 visited[nr] = 1; 869 to_visit[nr] = 0; 870 to_visit = to_visit | (edge[nr] & (~visited)); 871 for (int i = to_visit._Find_first(); i < SIZE(to_visit); i = to_visit._Find_next(i)) 872 dfs(i, visited, to_visit); 873 } 874 875 int solve() 876 { 877 cin >> n >> m; 878 forr(i, m) 879 { 880 int a, b; 881 cin >> a >> b; 882 G[a].PB(b); 883 } 884 885 int rres = skoj(); 886 if (rres) 887 { 888 FOR(i, 1, n) 889 { 890 for (auto j : G[i]) 891 { 892 edge[i][skojY[j]] = 1; 893 } 894 } 895 unordered_map<bitset<MXN>, vector<int>> mapa; 896 vector<pair<int, int>> vec, res; 897 FOR(i, 1, n) 898 { 899 bitset<MXN> to_visit; 900 dfs(i, bs[i], to_visit); 901 mapa[bs[i]].PB(i); 902 } 903 904 for (auto p : mapa) 905 { 906 vector<int> l = p.ss; 907 vec.PB({bs[l[0]].count(), l[0]}); 908 if (l.size() == 1) 909 { 910 res.PB({l[0], l[0]}); 911 continue; 912 } 913 for (int i = 0; i < SIZE(l); i++) 914 { 915 res.PB({l[i], l[i]}); 916 res.PB({l[i], l[(i + 1) % SIZE(l)]}); 917 } 918 } 919 sort(vec.begin(), vec.end()); 920 forr(i, SIZE(vec)) 921 { 922 int nr = vec[i].ss; 923 bitset<MXN> b; 924 for (int j = i - 1; j >= 0; j--) 925 if (vec[j].ff < vec[i].ff) 926 { 927 int nr2 = vec[j].ss; 928 if (bs[nr][nr2] && !b[nr2]) 929 { 930 b |= bs[nr2]; 931 res.PB({nr, nr2}); 932 } 933 } 934 } 935 936 cout << "YES" << '\n'; 937 cout << res.size() << '\n'; 938 for (auto p : res) 939 cout << p.ff << " " << p.ss + n << '\n'; 940 } 941 else 942 { 943 CLEAR(vis); 944 FOR(i, 1, n) 945 { 946 if (skojX[i] == 0) 947 { 948 dfs_m(i); 949 break; 950 } 951 } 952 vector<int> v; 953 FOR(i, 1, n) 954 { 955 if (vis[i]) 956 v.PB(i); 957 } 958 cout << "NO" << '\n'; 959 cout << v.size() << '\n'; 960 for (auto el : v) 961 cout << el << " "; 962 cout << '\n'; 963 } 964 965 return 0; 966 } 967 968 int main() 969 { 970 std::ios_base::sync_with_stdio(0); 971 cin.tie(0); 972 cout.tie(0); 973 974 solve(); 975 976 return 0; 977 } 978 ```