1819.md (21598B)
1 Source: https://codeforces.com/blog/entry/115133 2 3 [1820A - Yura's New Name](/contest/1820/problem/A "Codeforces Round 866 (Div. 2)") 4 5 Author: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") 6 7 Preparation: [FairyWinx](/profile/FairyWinx "Grandmaster FairyWinx") 8 9 **Editorial** 10 11 Tutorial is loading... 12 13 **Solution** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 int main() { 21 int t; 22 cin >> t; 23 while (t--) { 24 string s; 25 cin >> s; 26 if (s == "^") { 27 cout << 1 << '\n'; 28 continue; 29 } 30 int ans = 0; 31 if (s[0] == '_') 32 ++ans; 33 if (s.back() == '_') 34 ++ans; 35 for (int i = 0; i < (int) s.size() - 1; ++i) { 36 if (s[i] == '_' && s[i + 1] == '_') 37 ++ans; 38 } 39 cout << ans << '\n'; 40 } 41 } 42 ``` 43 44 [1820B - JoJo's Incredible Adventures](/contest/1820/problem/B "Codeforces Round 866 (Div. 2)") 45 46 Author: [golikovnik](/profile/golikovnik "Grandmaster golikovnik") 47 48 Preparation: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") 49 50 **Editorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 using ll = long long; 61 62 int main() { 63 ios::sync_with_stdio(0); cin.tie(0); 64 65 int t = 1; 66 cin >> t; 67 while (t--) { 68 string s; cin >> s; s += s; 69 int k = 0, z = 0; 70 for (char c : s) { 71 z = c == '1' ? z+1 : 0; 72 k = max(k, z); 73 } 74 const int n = s.size() / 2; 75 76 if (k > n) { 77 cout << (ll)n*n << '\n'; 78 } else { 79 const ll side_a = (k+1)/2; 80 const ll side_b = (k+2)/2; 81 cout << side_a * side_b << '\n'; 82 } 83 } 84 } 85 ``` 86 87 [1819A - Constructive Problem](/contest/1819/problem/A "Codeforces Round 866 (Div. 1)") 88 89 Author: [TeaTime](/profile/TeaTime "Master TeaTime") 90 91 Preparation: [golikovnik](/profile/golikovnik "Grandmaster golikovnik") 92 93 **Editorial** 94 95 Tutorial is loading... 96 97 **Solution** 98 99 ``` 100 // Nikita Golikov, 2023 101 102 #include <bits/stdc++.h> 103 104 using namespace std; 105 106 using uint = unsigned int; 107 using ll = long long; 108 using ull = unsigned long long; 109 110 #ifdef GOLIKOV 111 #define debug(x) cerr << (#x) << ":\t" << (x) << endl 112 #else 113 #define debug(x) 238; 114 #endif 115 116 template <class A, class B> 117 bool smin(A& x, B&& y) { 118 if (y < x) { 119 x = y; 120 return true; 121 } 122 return false; 123 } 124 125 template <class A, class B> 126 bool smax(A& x, B&& y) { 127 if (x < y) { 128 x = y; 129 return true; 130 } 131 return false; 132 } 133 134 template <class T> 135 int calcMex(vector<T> v) { 136 sort(v.begin(), v.end()); 137 v.erase(unique(v.begin(), v.end()), v.end()); 138 int n = int(v.size()); 139 for (int i = 0; i < n; ++i) if (v[i] != i) return i; 140 return n; 141 } 142 143 bool solveTest() { 144 int n; cin >> n; 145 vector<int> a(n); 146 map<int, int> leftOcc, rightOcc; 147 for (int i = 0; i < n; ++i) { 148 cin >> a[i]; 149 rightOcc[a[i]] = i; 150 if (!leftOcc.count(a[i])) leftOcc[a[i]] = i; 151 } 152 int mex = calcMex(a); 153 if (leftOcc.count(mex + 1)) { 154 int L = leftOcc[mex + 1], R = rightOcc[mex + 1]; 155 for (int i = L; i <= R; ++i) { 156 a[i] = mex; 157 } 158 int mx = calcMex(a); 159 assert(mx <= mex + 1); 160 return mx == mex + 1; 161 } 162 for (int i = 0; i < n; ++i) { 163 assert(a[i] != mex); 164 if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) { 165 return true; 166 } 167 } 168 return false; 169 } 170 171 int main() { 172 #ifdef GOLIKOV 173 assert(freopen("in", "rt", stdin)); 174 auto _clock_start = chrono::high_resolution_clock::now(); 175 #endif 176 ios::sync_with_stdio(false); 177 cin.tie(nullptr); 178 179 int t; cin >> t; 180 while (t--) { 181 cout << (solveTest() ? "Yes" : "No") << '\n'; 182 } 183 184 #ifdef GOLIKOV 185 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 186 chrono::high_resolution_clock::now() 187 - _clock_start).count() << "ms." << endl; 188 #endif 189 return 0; 190 } 191 ``` 192 193 [1819B - The Butcher](/contest/1819/problem/B "Codeforces Round 866 (Div. 1)") 194 195 Author: [Tikhon228](/profile/Tikhon228 "Master Tikhon228") 196 197 Preparation: [Kon567889](/profile/Kon567889 "Master Kon567889") 198 199 **Editorial** 200 201 Tutorial is loading... 202 203 **Solution** 204 205 ``` 206 //#pragma GCC target("trapv") 207 #include <iostream> 208 #include <vector> 209 #include <algorithm> 210 #include <set> 211 #include <string> 212 #include <cmath> 213 #include <map> 214 #include <iostream> 215 #include <list> 216 #include <stack> 217 #include <cassert> 218 using namespace std; 219 220 typedef long long ll; 221 typedef long double ld; 222 223 #define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); 224 225 const ll INF = 1e9 * 1e9 + 100, SZ = 1100; 226 227 ll n; 228 vector<pair<ll, ll>> vec; 229 map<ll, pair<ll, ll>> blocks; 230 231 pair<ll, ll> solve() { 232 set<pair<ll, ll>> widest, longest; 233 234 for (size_t i = 0; i < vec.size(); i++) { 235 widest.insert({ vec[i].first, i }); 236 longest.insert({ vec[i].second, i }); 237 238 blocks[i] = vec[i]; 239 } 240 241 pair<ll, ll> ans = { -1, -1 }; 242 bool mode = 0; 243 ll prevw = INF, prevh = INF, prv = -1; 244 bool cringe = 0; 245 while (widest.size() != 0) { 246 if (mode == 0) { 247 ll cur = (*widest.rbegin()).first, sum = 0; 248 if (ans.second == -1) ans.second = cur; 249 prv = blocks[(*widest.rbegin()).second].second; 250 251 while (widest.size() > 0 && (*widest.rbegin()).first == cur) { 252 auto it = (--widest.end()); 253 longest.erase({blocks[it->second].second, it->second }); 254 sum += blocks[it->second].second; 255 widest.erase(it); 256 } 257 258 if (!cringe) ans.first = sum; 259 prv = sum; 260 if (prevw == INF) { 261 prevh = cur; 262 } else { 263 prevw -= sum; 264 if (prevh != cur) return { -1, -1 }; 265 } 266 } else { 267 ll cur = (*longest.rbegin()).first, sum = 0; 268 if (!cringe) { 269 ans.first = cur + prv; 270 cringe = 1; 271 } 272 273 while (longest.size() > 0 && (*longest.rbegin()).first == cur) { 274 auto it = (--longest.end()); 275 widest.erase({ blocks[it->second].first, it->second }); 276 sum += blocks[it->second].first; 277 longest.erase(it); 278 } 279 280 if (prevw == INF) { 281 prevw = cur; 282 prevh -= sum; 283 if (prevw != cur) return { -1, -1 }; 284 } else { 285 prevh -= sum; 286 if (prevw != cur) return { -1, -1 }; 287 } 288 } 289 290 mode ^= 1; 291 } 292 293 if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) { 294 return ans; 295 } else { 296 return { -1, -1 }; 297 } 298 } 299 300 signed main() { 301 fastInp; 302 303 ll t; 304 cin >> t; 305 306 while (t--) { 307 vec.clear(); 308 blocks.clear(); 309 cin >> n; 310 311 vec.resize(n); 312 for (auto& c : vec) cin >> c.first >> c.second; 313 314 vector<pair<ll, ll>> ans; 315 316 ans.push_back(solve()); 317 swap(ans.back().first, ans.back().second); 318 if (ans.back().first == -1) ans.pop_back(); 319 320 for (auto& c : vec) swap(c.first, c.second); 321 322 ans.push_back(solve()); 323 if (ans.back().first == -1) ans.pop_back(); 324 325 if (ans.size() == 2 && ans[0] == ans[1]) { 326 ans.pop_back(); 327 } 328 cout << ans.size() << "\n"; 329 330 for (auto c : ans) cout << c.first << " " << c.second << "\n"; 331 } 332 333 return 0; 334 } 335 ``` 336 337 [1819C - The Fox and the Complete Tree Traversal](/contest/1819/problem/C "Codeforces Round 866 (Div. 1)") 338 339 Author: [golikovnik](/profile/golikovnik "Grandmaster golikovnik") 340 341 Preparation: [DishonoredRighteous](/profile/DishonoredRighteous "Grandmaster DishonoredRighteous") 342 343 **Editorial** 344 345 Tutorial is loading... 346 347 **Solution** 348 349 ``` 350 // #pragma comment(linker, "/stack:200000000") 351 // #pragma GCC optimize("Ofast,no-stack-protector") 352 // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") 353 // #pragma GCC optimize("unroll-loops") 354 355 #include <stdio.h> 356 #include <bits/stdc++.h> 357 358 #ifdef PERVEEVM_LOCAL 359 #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl 360 #else 361 #define debug(x) 238 362 #endif 363 364 #define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0) 365 #define NAME "File" 366 367 using ll = long long; 368 using ld = long double; 369 370 #ifdef PERVEEVM_LOCAL 371 std::mt19937 rnd(238); 372 #else 373 std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count()); 374 #endif 375 376 template<typename T> 377 bool smin(T& a, const T& b) { 378 if (b < a) { 379 a = b; 380 return true; 381 } 382 return false; 383 } 384 385 template<typename T> 386 bool smax(T& a, const T& b) { 387 if (a < b) { 388 a = b; 389 return true; 390 } 391 return false; 392 } 393 394 const double PI = atan2(0.0, -1.0); 395 const int INF = 0x3f3f3f3f; 396 const ll LINF = (ll)2e18; 397 const int N = 200100; 398 399 std::vector<int> g[N]; 400 int d[N], par[N]; 401 bool onDiameter[N]; 402 403 void dfs(int v, int p, int depth) { 404 d[v] = depth; 405 par[v] = p; 406 407 for (auto to : g[v]) { 408 if (to != p) { 409 dfs(to, v, depth + 1); 410 } 411 } 412 } 413 414 void run() { 415 int n; 416 scanf("%d", &n); 417 418 for (int i = 0; i < n - 1; ++i) { 419 int from, to; 420 scanf("%d%d", &from, &to); 421 g[from - 1].push_back(to - 1); 422 g[to - 1].push_back(from - 1); 423 } 424 425 dfs(0, 0, 0); 426 int v1 = 0; 427 for (int i = 0; i < n; ++i) { 428 if (d[i] > d[v1]) { 429 v1 = i; 430 } 431 } 432 433 dfs(v1, v1, 0); 434 int v2 = v1; 435 for (int i = 0; i < n; ++i) { 436 if (d[i] > d[v2]) { 437 v2 = i; 438 } 439 } 440 441 std::vector<int> diameter; 442 for (int v = v2; v != v1; v = par[v]) { 443 onDiameter[v] = true; 444 diameter.push_back(v); 445 } 446 onDiameter[v1] = true; 447 diameter.push_back(v1); 448 std::reverse(diameter.begin(), diameter.end()); 449 450 for (int i = 0; i < n; ++i) { 451 if (onDiameter[i]) { 452 continue; 453 } 454 if (!onDiameter[par[i]]) { 455 printf("No\n"); 456 return; 457 } 458 } 459 460 printf("Yes\n"); 461 std::vector<int> ans; 462 for (int i = 0; i < (int)diameter.size(); i += 2) { 463 ans.push_back(diameter[i]); 464 if (i + 1 != (int)diameter.size()) { 465 for (auto to : g[diameter[i + 1]]) { 466 if (!onDiameter[to]) { 467 ans.push_back(to); 468 } 469 } 470 } 471 } 472 473 if (diameter.size() % 2 == 0) { 474 for (int i = (int)diameter.size() - 1; i > 0; i -= 2) { 475 ans.push_back(diameter[i]); 476 if (i - 1 >= 0) { 477 for (auto to : g[diameter[i - 1]]) { 478 if (!onDiameter[to]) { 479 ans.push_back(to); 480 } 481 } 482 } 483 } 484 } else { 485 for (int i = (int)diameter.size() - 1; i > 0; i -= 2) { 486 ans.push_back(diameter[i - 1]); 487 if (i - 2 >= 0) { 488 for (auto to : g[diameter[i - 2]]) { 489 if (!onDiameter[to]) { 490 ans.push_back(to); 491 } 492 } 493 } 494 } 495 } 496 497 assert((int)ans.size() == n); 498 for (auto i : ans) { 499 printf("%d ", i + 1); 500 } 501 printf("\n"); 502 } 503 504 int main(void) { 505 // freopen(NAME".in", "r", stdin); 506 // freopen(NAME".out", "w", stdout); 507 508 #ifdef PERVEEVM_LOCAL 509 auto start = std::chrono::high_resolution_clock::now(); 510 #endif 511 512 run(); 513 514 #ifdef PERVEEVM_LOCAL 515 auto end = std::chrono::high_resolution_clock::now(); 516 std::cerr << "Execution time: " 517 << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 518 << " ms" << std::endl; 519 #endif 520 521 return 0; 522 } 523 ``` 524 525 [1819D - Misha and Apples](/contest/1819/problem/D "Codeforces Round 866 (Div. 1)") 526 527 Author: [Um_nik](/profile/Um_nik "Legendary Grandmaster Um_nik") 528 529 Preparation: [dshindov](/profile/dshindov "Candidate Master dshindov") 530 531 **Editorial** 532 533 Tutorial is loading... 534 535 **Solution** 536 537 ``` 538 #include <bits/stdc++.h> 539 540 #include <exception> 541 542 using namespace std; 543 using ll = long long; 544 545 void solve() { 546 int n, m; 547 cin >> n >> m; 548 vector<vector<int>> apples(n); 549 for (int i = 0; i < n; ++i) { 550 int k; 551 cin >> k; 552 for (int j = 0; j < k; ++j) { 553 int x; 554 cin >> x; 555 apples[i].push_back(x); 556 } 557 } 558 // vector<int> last(m + 1, -1); 559 unordered_map<int, int> last; 560 auto get_last = [&](int i) { 561 if (!last.count(i)) { 562 return -1; 563 } else { 564 return last[i]; 565 } 566 }; 567 vector<char> can_zero(n + 1, false); 568 vector<int> prev(n + 1, 0); 569 can_zero[0] = true; 570 int oops = -1; 571 for (int i = 0; i < n; ++i) { 572 if (apples[i].empty()) { 573 can_zero[i + 1] = true; 574 last[0] = i; 575 } else { 576 int nearest_pair = get_last(0); 577 int new_oops = oops; 578 for (int x : apples[i]) { 579 nearest_pair = max(nearest_pair, get_last(x)); 580 new_oops = max(new_oops, get_last(x)); 581 last[x] = i; 582 } 583 if (nearest_pair != -1) { 584 int nearest_zero = prev[nearest_pair]; 585 if (oops < nearest_zero) { 586 can_zero[i + 1] = true; 587 } 588 } 589 oops = new_oops; 590 } 591 if (can_zero[i + 1]) { 592 prev[i + 1] = i + 1; 593 } else { 594 prev[i + 1] = prev[i]; 595 } 596 } 597 // vector<char> used(m + 1, false); 598 unordered_set<int> used; 599 vector<int> max_cnt(n + 1, 0); 600 int current_cnt = 0; 601 for (int i = n - 1; i >= 0; --i) { 602 bool fail = false; 603 if (apples[i].empty()) { 604 used.insert(0); 605 } 606 for (int x : apples[i]) { 607 if (used.count(x)) { 608 fail = true; 609 break; 610 } 611 used.insert(x); 612 ++current_cnt; 613 } 614 if (fail) { 615 break; 616 } 617 if (used.count(0)) { 618 max_cnt[i] = m; 619 } else { 620 max_cnt[i] = current_cnt; 621 } 622 } 623 int ans = 0; 624 for (int i = 0; i <= n; ++i) { 625 if (can_zero[i]) { 626 ans = max(ans, max_cnt[i]); 627 } 628 } 629 cout << ans << '\n'; 630 } 631 632 int main() { 633 cin.tie(nullptr)->sync_with_stdio(false); 634 int t = 1; 635 cin >> t; 636 while (t--) solve(); 637 } 638 ``` 639 640 [1819E - Roads in E City](/contest/1819/problem/E "Codeforces Round 866 (Div. 1)") 641 642 Author: [Tikhon228](/profile/Tikhon228 "Master Tikhon228") 643 644 Preparation: [grphil](/profile/grphil "Master grphil") 645 646 **Editorial** 647 648 Tutorial is loading... 649 650 **Solution** 651 652 ``` 653 #include <bits/stdc++.h> 654 655 #define x first 656 #define y second 657 658 using namespace std; 659 660 mt19937 rnd; 661 662 struct solve { 663 664 vector<pair<int, int>> r; 665 666 vector<vector<pair<int, int>>> s; 667 668 vector<int> ans; 669 670 int n, m; 671 672 static constexpr int rep = 45; 673 674 int dfs(int a, int p, int b) { 675 for (auto i : s[a]) { 676 if (i.x == b) { 677 return i.y; 678 } 679 if (i.x == p) { 680 continue; 681 } 682 683 int x = dfs(i.x, a, b); 684 685 if (x != -1) { 686 return x; 687 } 688 } 689 return -1; 690 } 691 692 solve() { 693 cin >> n >> m; 694 r.resize(m); 695 for (int i = 0; i < m; i++) { 696 cin >> r[i].x >> r[i].y; 697 r[i].x--; 698 r[i].y--; 699 } 700 701 s.resize(n); 702 ans.resize(m, -1); 703 int cnt = 0; 704 for (int i = 0; i < m; i++) { 705 rem(i); 706 for (int j = 0; j < rep; j++) { 707 if (!ask_end(i)) { 708 ans[i] = 1; 709 break; 710 } 711 } 712 if (ans[i] == 1) { 713 add(i); 714 cnt++; 715 s[r[i].x].emplace_back(r[i].y, i); 716 s[r[i].y].emplace_back(r[i].x, i); 717 } 718 } 719 720 assert(cnt == n - 1); 721 722 for (int i = 0; i < m; i++) { 723 if (ans[i] != -1) continue; 724 ans[i] = 1; 725 726 int c = dfs(r[i].x, -1, r[i].y); 727 rem(c); 728 add(i); 729 for (int j = 0; j < rep; j++) { 730 if (!ask_end(i)) { 731 ans[i] = 0; 732 break; 733 } 734 } 735 rem(i); 736 add(c); 737 } 738 cout << "!"; 739 for (int i = 0; i < m; i++) { 740 cout << ' ' << ans[i]; 741 } 742 cout << endl; 743 int x; 744 cin >> x; 745 if (x != 1) { 746 exit(1); 747 } 748 } 749 750 void rem(int x) { 751 cout << "- " << x + 1 << endl; 752 } 753 754 void add(int x) { 755 cout << "+ " << x + 1 << endl; 756 } 757 758 bool ask(int a) { 759 cout << "? " << a + 1 << endl; 760 // cerr << "? " << a + 1 << endl; 761 int x; 762 cin >> x; 763 return x == 1; 764 } 765 766 bool ask_end(int i) { 767 // cerr << "ask_end " << i << endl; 768 int a = r[i].x; 769 if (rnd() % 2) { 770 a = r[i].y; 771 } 772 return ask(a); 773 } 774 775 }; 776 777 int main() { 778 int t; 779 cin >> t; 780 for (int i = 0; i < t; i++) { 781 solve(); 782 } 783 } 784 ``` 785 786 [1819F - Willy-nilly, Crack, Into Release!](/contest/1819/problem/F "Codeforces Round 866 (Div. 1)") 787 788 Author: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") 789 790 Preparation: [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") 791 792 **Editorial** 793 794 Tutorial is loading... 795 796 **Solution** 797 798 ``` 799 #include <bits/stdc++.h> 800 801 using namespace std; 802 using pi = pair<int, int>; 803 using ll = long long; 804 805 const int Q = 1e5; 806 const int N = 20; 807 const int V = N*Q; 808 809 const ll LINF = 1e18; 810 811 struct MinMaxValue { 812 ll min_value; 813 ll max_value; 814 815 MinMaxValue operator * (const MinMaxValue& x) const { 816 if (x.max_value < 0 || max_value < 0) { 817 return MinMaxValue { 0, -1 }; 818 } 819 820 return MinMaxValue { 821 .min_value = x.min_value + min_value, 822 .max_value = x.max_value + max_value 823 }; 824 } 825 826 MinMaxValue operator + (const MinMaxValue& x) const { 827 if (x.max_value == -1) return *this; 828 if (max_value == -1) return x; 829 830 return MinMaxValue { 831 .min_value = min(x.min_value, min_value), 832 .max_value = max(x.max_value, max_value) 833 }; 834 } 835 836 MinMaxValue& operator += (const MinMaxValue& x) { 837 return *this = *this + x; 838 } 839 840 void Reset() { 841 min_value = 0; 842 max_value = -1; 843 } 844 }; 845 846 struct { 847 MinMaxValue dig, ver, hor; 848 int cnt; 849 int go[4]; 850 } nd[V]; 851 int vc = 0; 852 MinMaxValue dig[N+1], ver[N+1], hor[N+1]; 853 854 std::set<ll> words; 855 856 int NewVertex(int h) { 857 int* go = nd[vc].go; 858 go[0] = go[1] = go[2] = go[3] = -1; 859 nd[vc].dig = dig[h]; 860 nd[vc].hor = hor[h]; 861 nd[vc].ver = ver[h]; 862 nd[vc].cnt = 0; 863 return vc++; 864 } 865 866 tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) { 867 return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0) 868 : make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt); 869 } 870 871 void Calculate(int v, int h, int corner) { 872 auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1); 873 auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1); 874 auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1); 875 auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1); 876 877 nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3; 878 879 nd[v].dig.Reset(); 880 if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1; 881 if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1; 882 883 nd[v].hor = ver0 * dig2 * dig3 * ver1; 884 if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1; 885 886 nd[v].ver = hor0 * dig1 * dig3 * hor2; 887 if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2; 888 } 889 890 void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) { 891 if (h == 0) { 892 if (nd[v].cnt == 0) { 893 words.insert(msk_save); 894 } else { 895 words.erase(msk_save); 896 } 897 nd[v].cnt ^= 1; 898 } else { 899 UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save); 900 Calculate(v, h, corner); 901 } 902 } 903 904 bool near_symbols[256][256]; 905 906 MinMaxValue GetAnswer(int h) { 907 int v = 0; 908 909 if (nd[v].cnt == 0) { 910 return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value }; 911 } 912 913 MinMaxValue res; res.Reset(); 914 915 bool cycle_len2 = false; 916 if (nd[v].cnt <= 1) cycle_len2 = true; 917 if (nd[v].cnt == 2) { 918 string s, t; 919 920 for (ll msk = *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]); 921 for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]); 922 auto flag = near_symbols[s.back()][t.back()]; 923 924 if (s.substr(0, h-1) == t.substr(0, h-1) && flag) { 925 cycle_len2 = true; 926 } 927 928 int s_suf = 0, t_suf = 0; 929 while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf; 930 while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf; 931 932 if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1) 933 && s.back() == t[h - s_suf - 1] 934 && t.back() == s[h - t_suf - 1]) cycle_len2 = true; 935 } 936 937 if (cycle_len2) { 938 res.min_value = 2; 939 res.max_value = 2; 940 } 941 942 while (h != 0) { 943 const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3]; 944 const auto& dig0 = get<0>(GetState(v0, h-1)); 945 const auto& dig1 = get<0>(GetState(v1, h-1)); 946 const auto& dig2 = get<0>(GetState(v2, h-1)); 947 const auto& dig3 = get<0>(GetState(v3, h-1)); 948 949 if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) { 950 res += dig0 * dig1 * dig2 * dig3; 951 } 952 953 --h; 954 if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; } 955 if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; } 956 if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; } 957 if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; } 958 break; 959 } 960 return res; 961 } 962 963 int main() { 964 ios::sync_with_stdio(0); cin.tie(0); 965 966 int n, q; cin >> n >> q; 967 vector<ll> v(q); 968 969 for (int i = 0; i < 4; ++i) { 970 int j = (i + 1) % 4; 971 near_symbols['a' + i]['a' + j] = true; 972 near_symbols['a' + j]['a' + i] = true; 973 } 974 975 dig[0] = ver[0] = hor[0] = { 1, 1 }; 976 for (int i = 1; i <= n; ++i) { 977 dig[i] = hor[i-1] * dig[i-1] * ver[i-1]; 978 hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1]; 979 } 980 981 int m_root = NewVertex(n); // make_root 982 assert(m_root == 0); 983 984 for (int i = 0; i < q; ++i) { 985 string s; cin >> s; 986 for (int j = 0; j < n; ++j) { 987 v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j); 988 v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j); 989 } 990 991 int w = 0; 992 for (int j = 0; j < n; ++j) { 993 int& next = nd[w].go[(v[i] >> (2*j)) & 3]; 994 if (next == -1) next = NewVertex(n-j-1); 995 w = next; 996 } 997 } 998 999 for (ll msk : v) { 1000 UpdateCount(0, n, 0, msk, msk); 1001 auto [a, b] = GetAnswer(n); 1002 1003 if (a > b) { 1004 cout << -1 << '\n'; 1005 } else { 1006 cout << a << " " << b << '\n'; 1007 } 1008 } 1009 } 1010 ```