1362.md (14222B)
1 Source: https://codeforces.com/blog/entry/78355 2 3 [1362A - Johnny and Ancient Computer](/contest/1362/problem/A "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!") 4 5 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 typedef long long LL; 19 20 LL getR(LL a){ 21 while(a % 2 == 0) 22 a /= 2; 23 return a; 24 } 25 26 void solve(){ 27 LL a, b; 28 scanf("%lld %lld", &a, &b); 29 if(a > b) swap(a, b); 30 31 LL r = getR(a); 32 if(getR(b) != r){ 33 puts("-1"); 34 return; 35 } 36 37 int ans = 0; 38 b /= a; 39 40 while(b >= 8) 41 b /= 8, ++ans; 42 if(b > 1) ++ans; 43 printf("%d\n", ans); 44 } 45 46 int main(){ 47 int quest; 48 scanf("%d", &quest); 49 50 while(quest--) 51 solve(); 52 return 0; 53 } 54 ``` 55 56 [1362B - Johnny and His Hobbies](/contest/1362/problem/B "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!") 57 58 Authors: [Anadi](/profile/Anadi "International Grandmaster Anadi") and [Okrut](/profile/Okrut "Master Okrut") 59 60 **Tutorial** 61 62 Tutorial is loading... 63 64 **Solution** 65 66 ``` 67 //O(n * maxA) solution 68 69 #include <bits/stdc++.h> 70 71 using namespace std; 72 73 const int N = 1025; 74 75 int n; 76 int in[N]; 77 bool is[N]; 78 79 bool check(int k){ 80 for(int i = 1; i <= n; ++i) 81 if(!is[in[i] ^ k]) 82 return false; 83 return true; 84 } 85 86 void solve(){ 87 for(int i = 0; i < N; ++i) 88 is[i] = false; 89 90 scanf("%d", &n); 91 for(int i = 1; i <= n; ++i){ 92 scanf("%d", &in[i]); 93 is[in[i]] = true; 94 } 95 96 for(int k = 1; k < 1024; ++k) 97 if(check(k)){ 98 printf("%d\n", k); 99 return; 100 } 101 102 puts("-1"); 103 } 104 105 int main(){ 106 int cases; 107 scanf("%d", &cases); 108 109 while(cases--) 110 solve(); 111 return 0; 112 } 113 ``` 114 115 [1362C - Johnny and Another Rating Drop](/contest/1362/problem/C "Codeforces Round 647 (Div. 2) - Thanks, Algo Muse!") 116 117 Author: [MicGor](/profile/MicGor "International Grandmaster MicGor") 118 119 **Tutorial** 120 121 Tutorial is loading... 122 123 **Solution** 124 125 ``` 126 #include <bits/stdc++.h> 127 128 using namespace std; 129 130 typedef long long LL; 131 132 void solve(){ 133 LL a; 134 scanf("%lld", &a); 135 136 LL ans = 0; 137 for(int i = 0; i < 60; ++i) 138 if(a & (1LL << i)) 139 ans += (1LL << (i + 1)) - 1; 140 printf("%lld\n", ans); 141 } 142 143 int main(){ 144 int quest; 145 scanf("%d", &quest); 146 147 while(quest--) 148 solve(); 149 return 0; 150 } 151 ``` 152 153 [1361A - Johnny and Contribution](/contest/1361/problem/A "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 154 155 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 156 157 **Tutorial** 158 159 Tutorial is loading... 160 161 **Solution** 162 163 ``` 164 #include <bits/stdc++.h> 165 166 using namespace std; 167 168 const int N = 1e6 + 7; 169 170 int n, m; 171 int ans[N]; 172 173 int last[N]; 174 vector <int> G[N]; 175 vector <int> in[N]; 176 177 int main(){ 178 scanf("%d %d", &n, &m); 179 for(int i = 1; i <= m; ++i){ 180 int u, v; 181 scanf("%d %d", &u, &v); 182 183 G[u].push_back(v); 184 G[v].push_back(u); 185 } 186 187 for(int i = 1; i <= n; ++i){ 188 int color; 189 scanf("%d", &color); 190 191 in[color].push_back(i); 192 if(color > n){ 193 puts("-1"); 194 exit(0); 195 } 196 } 197 198 vector <int> result; 199 for(int i = 1; i <= n; ++i){ 200 for(auto u: in[i]){ 201 for(auto v: G[u]) 202 last[ans[v]] = u; 203 204 ans[u] = 1; 205 while(last[ans[u]] == u) 206 ++ans[u]; 207 208 if(ans[u] != i){ 209 puts("-1"); 210 exit(0); 211 } 212 213 result.push_back(u); 214 } 215 } 216 217 for(int i = 0; i < n; ++i) 218 printf("%d%c", result[i], i == n - 1 ? '\n' : ' '); 219 return 0; 220 } 221 ``` 222 223 [1361B - Johnny and Grandmaster](/contest/1361/problem/B "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 224 225 Author: [Okrut](/profile/Okrut "Master Okrut") 226 227 **Tutorial** 228 229 Tutorial is loading... 230 231 **Solution** 232 233 ``` 234 #include <bits/stdc++.h> 235 using namespace std; 236 typedef long long ll; 237 238 const ll INF = 1e6+100; 239 const ll mod = ll(1e9)+7; 240 241 ll fexp (ll a, int e) 242 { 243 ll ret = 1LL; 244 while (e>0) 245 { 246 if (e%2==1) ret = ret * a % mod; 247 a = a*a % mod; 248 e/=2; 249 } 250 return ret; 251 } 252 253 int main () 254 { 255 int t; 256 scanf ("%d", &t); 257 for (int test = 0; test < t; test++) 258 { 259 int n; 260 ll p; 261 scanf ("%d %lld", &n, &p); 262 vector <int> K(n); 263 for (int &x: K) scanf ("%d", &x); 264 sort(K.begin(), K.end()); 265 266 vector <int> Exp = K; 267 268 ll currSum = 0; 269 ll result = 0; 270 bool infty = false; 271 272 int prevExp = 1e6+10; 273 while (!Exp.empty()) 274 { 275 /* Update the currSum and result (multiply by a power of k) */ 276 int k = Exp.back(); 277 Exp.pop_back(); 278 int delta = prevExp - k; 279 prevExp = k; 280 281 result = result * fexp(p, delta) % mod; 282 283 /* Multiplying by p 20 times will either 284 not change the currSum at all or make it bigger than n */ 285 for (int i=0; i<min(delta, 20); i++) 286 { 287 currSum *= p; 288 if (currSum > INF) infty = true; 289 } 290 291 /* Process all the elements equal p^k */ 292 while (!K.empty() && K.back()==k) 293 { 294 K.pop_back(); 295 if (infty || currSum > 0) 296 { 297 currSum--; 298 result+=mod - 1; 299 } 300 else 301 { 302 currSum++; 303 result++; 304 } 305 result%=mod; 306 } 307 } 308 309 result = result * fexp(p, prevExp) % mod; 310 311 printf ("%lld\n", result % mod); 312 } 313 } 314 ``` 315 316 [1361C - Johnny and Megan's Necklace](/contest/1361/problem/C "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 317 318 Author: [Okrut](/profile/Okrut "Master Okrut") 319 320 **Tutorial** 321 322 Tutorial is loading... 323 324 **Solution** 325 326 ``` 327 #include <bits/stdc++.h> 328 329 using namespace std; 330 331 #define st first 332 #define nd second 333 #define PII pair <int, int> 334 335 const int N = 1 << 20; 336 337 int n; 338 int part[N][2]; 339 340 bool vis[N]; 341 vector <int> ans; 342 vector <PII> G[N]; 343 344 //mark whole component as visited 345 void dfs(int u){ 346 vis[u] = true; 347 for(auto v: G[u]) 348 if(!vis[v.st]) 349 dfs(v.st); 350 } 351 352 //check if the graph for a given Mask is correct 353 bool check(int Mask){ 354 for(int i = 0; i <= Mask; ++i) 355 G[i].clear(), vis[i] = false; 356 357 for(int i = 1; i <= n; ++i){ 358 int u = part[i][0] & Mask; 359 int v = part[i][1] & Mask; 360 361 G[u].push_back({v, 2 * i - 1}); 362 G[v].push_back({u, 2 * i - 2}); 363 } 364 365 //calculate number of components and check if all degrees are even 366 int comps = 0; 367 for(int i = 0; i <= Mask; ++i){ 368 if(G[i].size() & 1) 369 return false; 370 371 if(!vis[i] && G[i].size() > 0){ 372 ++comps; 373 dfs(i); 374 } 375 } 376 377 return comps == 1; 378 } 379 380 //find euler cycle 381 void go(int u, int prv = -1){ 382 while(G[u].size()){ 383 auto e = G[u].back(); 384 G[u].pop_back(); 385 386 if(vis[e.nd / 2]) 387 continue; 388 389 vis[e.nd / 2] = true; 390 go(e.st, e.nd); 391 } 392 393 if(prv != -1){ 394 ans.push_back(prv); 395 ans.push_back(prv ^ 1); 396 } 397 } 398 399 //restore the sequence corresponding to the result for given mask 400 //the result is already checked so the graph is built 401 void restore(int Mask){ 402 for(int i = 0; i <= n; ++i) 403 vis[i] = false; 404 405 for(int i = 0; i <= Mask; ++i) 406 if(G[i].size()){ 407 go(i); 408 break; 409 } 410 411 //cycle is reversed but thats fine 412 for(int i = 0; i < n + n; ++i) 413 printf("%d%c", ans[i] + 1, " \n"[i + 1 == n + n]); 414 } 415 416 int main(){ 417 scanf("%d", &n); 418 for(int i = 1; i <= n; ++i) 419 scanf("%d %d", &part[i][0], &part[i][1]); 420 421 for(int i = 20; i >= 0; --i) 422 if(check((1 << i) - 1)){ 423 printf("%d\n", i); 424 restore((1 << i) - 1); 425 exit(0); 426 } 427 428 assert(false); 429 return 0; 430 } 431 ``` 432 433 [1361D - Johnny and James](/contest/1361/problem/D "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 434 435 Author: [Okrut](/profile/Okrut "Master Okrut") 436 437 **Tutorial** 438 439 Tutorial is loading... 440 441 **Solution** 442 443 ``` 444 #include <bits/stdc++.h> 445 446 using namespace std; 447 448 typedef long double T; 449 450 #define st first 451 #define nd second 452 #define PII pair <int, int> 453 454 const int N = 1e6 + 7; 455 456 int n, m, k; 457 vector <T> arms[N]; 458 459 void read(){ 460 map <PII, int> M; 461 462 scanf("%d %d", &n, &k); 463 for(int i = 1; i <= n; ++i){ 464 int x, y; 465 scanf("%d %d", &x, &y); 466 467 if(x == 0 && y == 0) 468 continue; 469 470 int d = __gcd(abs(x), abs(y)); 471 PII my_id = {x / d, y / d}; 472 473 if(!M.count(my_id)) 474 M[my_id] = ++m; 475 476 auto id = M[my_id]; 477 arms[id].push_back(sqrtl((T)x * x + (T)y * y)); 478 } 479 480 for(int i = 1; i <= m; ++i){ 481 sort(arms[i].begin(), arms[i].end()); 482 reverse(arms[i].begin(), arms[i].end()); 483 } 484 } 485 486 T solve_center(){ 487 T ans = 0; 488 vector <T> vals = {0}; 489 490 for(int i = 1; i <= m; ++i){ 491 int it = 0; 492 for(auto v: arms[i]){ 493 ++it; 494 vals.push_back(v * (k - it - it + 1)); 495 } 496 } 497 498 sort(vals.begin(), vals.end()); 499 reverse(vals.begin(), vals.end()); 500 501 for(int i = 0; i < k; ++i) 502 ans += vals[i]; 503 return ans; 504 } 505 506 T solve_arm(int id){ 507 T ans = 0; 508 for(int i = 1; i <= m; ++i){ 509 if(i == id) 510 continue; 511 512 int it = 0; 513 for(auto v: arms[i]){ 514 ++it; 515 ans += v * (k - it - it + 1); 516 } 517 } 518 519 int half = k / 2; 520 int first_half = k - half - (n - arms[id].size()); 521 522 for(int i = 0; i < half; ++i) 523 ans += arms[id][i] * (k - i - i - 1); 524 525 for(int i = 0; i < first_half; ++i){ 526 T val = arms[id][arms[id].size() - i - 1]; 527 ans += val * (k - half - half - 2 * first_half + 2 * i + 1); 528 } 529 530 return ans; 531 } 532 533 int main(){ 534 read(); 535 T ans = solve_center(); 536 if(k < n){ 537 for(int i = 1; i <= m; ++i) 538 if(2 * (n - (int)arms[i].size()) <= k) 539 ans = max(ans, solve_arm(i)); 540 } 541 542 printf("%.10Lf\n", ans); 543 return 0; 544 } 545 ``` 546 547 [1361E - James and the Chase](/contest/1361/problem/E "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 548 549 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 550 551 **Tutorial** 552 553 Tutorial is loading... 554 555 **Solution** 556 557 ``` 558 #include <bits/stdc++.h> 559 560 using namespace std; 561 562 const int N = 1e5 + 7; 563 564 int n, m; 565 bool bad[N]; 566 vector <int> G[N]; 567 568 int vis[N]; 569 bool interesting; 570 571 int lvl[N]; 572 int best[N]; 573 int balance[N]; 574 575 void clear(){ 576 for(int i = 1; i <= n; ++i){ 577 lvl[i] = 0; 578 best[i] = 0; 579 balance[i] = 0; 580 581 G[i].clear(); 582 bad[i] = false; 583 } 584 } 585 586 void no_answer(){ 587 puts("-1"); 588 clear(); 589 } 590 591 int getInt(int a = INT_MIN, int b = INT_MAX){ 592 static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 593 return uniform_int_distribution <int> (a, b)(rng); 594 } 595 596 void dfs(int u){ 597 vis[u] = 1; 598 for(auto v: G[u]) 599 if(vis[v] == 0) 600 dfs(v); 601 else if(vis[v] == 2) 602 interesting = false; 603 vis[u] = 2; 604 } 605 606 bool check(int r){ 607 for(int i = 1; i <= n; ++i) 608 vis[i] = 0; 609 interesting = true; 610 611 dfs(r); 612 return interesting; 613 } 614 615 int find_any(){ 616 int tests = 100; 617 while(tests--){ 618 int r = getInt(1, n); 619 if(check(r)) 620 return r; 621 } 622 623 return -1; 624 } 625 626 int find_bad(int u){ 627 vis[u] = 1; 628 best[u] = u; 629 for(auto v: G[u]) 630 if(vis[v] == 0){ 631 lvl[v] = lvl[u] + 1; 632 balance[u] += find_bad(v); 633 634 if(lvl[best[v]] < lvl[best[u]]) 635 best[u] = best[v]; 636 } 637 else{ 638 balance[u]++; 639 balance[v]--; 640 641 if(lvl[v] < lvl[best[u]]) 642 best[u] = v; 643 } 644 645 if(balance[u] > 1) 646 bad[u] = true; 647 return balance[u]; 648 } 649 650 void propagate_bad(int u){ 651 vis[u] = 1; 652 if(!bad[u] && bad[best[u]]) 653 bad[u] = true; 654 655 for(auto v: G[u]) 656 if(vis[v] == 0) 657 propagate_bad(v); 658 } 659 660 vector <int> find_all(int r){ 661 for(int i = 1; i <= n; ++i) 662 vis[i] = 0; 663 vector <int> ans; 664 665 find_bad(r); 666 for(int i = 1; i <= n; ++i) 667 vis[i] = 0; 668 669 propagate_bad(r); 670 for(int i = 1; i <= n; ++i) 671 if(!bad[i]) 672 ans.push_back(i); 673 return ans; 674 } 675 676 void solve(){ 677 scanf("%d %d", &n, &m); 678 for(int i = 1; i <= m; ++i){ 679 int u, v; 680 scanf("%d %d", &u, &v); 681 G[u].push_back(v); 682 } 683 684 int id = find_any(); 685 if(id == -1){ 686 no_answer(); 687 return; 688 } 689 690 auto ans = find_all(id); 691 if(5 * ans.size() >= n){ 692 for(auto v: ans) 693 printf("%d ", v); 694 puts(""); 695 clear(); 696 } 697 else 698 no_answer(); 699 } 700 701 int main(){ 702 int cases; 703 scanf("%d", &cases); 704 705 while(cases--) 706 solve(); 707 return 0; 708 } 709 ``` 710 711 [1361F - Johnny and New Toy](/contest/1361/problem/F "Codeforces Round 647 (Div. 1) - Thanks, Algo Muse!") 712 713 Author: [Anadi](/profile/Anadi "International Grandmaster Anadi") 714 715 **Tutorial** 716 717 Tutorial is loading... 718 719 **Solution** 720 721 ``` 722 #include <bits/stdc++.h> 723 #include <ext/pb_ds/assoc_container.hpp> 724 #include <ext/pb_ds/tree_policy.hpp> 725 726 using namespace std; 727 using namespace __gnu_pbds; 728 729 typedef long long ll; 730 typedef tree < int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update > ordered_set; 731 732 const int N = 2e5 + 7; 733 734 //cartesian tree node 735 //while creating we calculate set of elements and number of inversions 736 struct node{ 737 int splitter = -1; 738 long long invs = 0; 739 740 ordered_set S; 741 node *left = nullptr, *right = nullptr; 742 node(){} 743 }; 744 745 int n; 746 int in[N]; 747 int weight[N]; 748 749 long long ans = 0; 750 node *root = nullptr; 751 752 void read(){ 753 scanf("%d", &n); 754 for(int i = 1; i <= n; ++i) 755 scanf("%d", &in[i]); 756 757 for(int i = 1; i < n; ++i) 758 scanf("%d", &weight[i]); 759 } 760 761 //add/delete contribution from fiven node to result 762 void add_result(node *cur, int mt = 1){ 763 if(cur -> splitter == 0) 764 return; 765 ans += mt * min(cur -> invs, (ll)cur -> left -> S.size() * (ll)cur -> right -> S.size() - cur -> invs); 766 } 767 768 //Create cartesian tree 769 //Because expected depth is O(logn) we can use bruteforce to find the smallest weight 770 node* get_cartesian(int from, int to){ 771 node *ret = new node(); 772 if(from == to){ 773 ret -> S.insert(in[from]); 774 return ret; 775 } 776 777 int id = from; 778 for(int i = from + 1; i < to; ++i) 779 if(weight[i] < weight[id]) 780 id = i; 781 782 ret -> splitter = id; 783 ret -> left = get_cartesian(from, id); 784 ret -> right = get_cartesian(id + 1, to); 785 786 //get elements from ordered set 787 for(auto v: ret -> right -> S) 788 ret -> S.insert(v); 789 790 //calculate number of inversions 791 for(auto v: ret -> left -> S){ 792 ret -> S.insert(v); 793 ret -> invs += ret -> right -> S.order_of_key(v); 794 } 795 796 //add contribution to the result 797 add_result(ret); 798 return ret; 799 } 800 801 //depending on mt, removes/add element val on position p 802 void update_cart(int p, int val, int mt){ 803 node *cur = root; 804 while(cur -> splitter != -1){ 805 add_result(cur, -1); 806 if(mt == -1) 807 cur -> S.erase(val); 808 else 809 cur -> S.insert(val); 810 811 if(p <= cur -> splitter){ 812 cur -> invs += mt * (int)(cur -> right -> S.order_of_key(val)); 813 cur = cur -> left; 814 } 815 else{ 816 cur -> invs += mt * (int)(cur -> left -> S.size() - cur -> left -> S.order_of_key(val)); 817 cur = cur -> right; 818 } 819 } 820 821 if(mt == -1) 822 cur -> S.erase(val); 823 else 824 cur -> S.insert(val); 825 826 cur = root; 827 while(cur -> splitter != -1){ 828 add_result(cur, 1); 829 if(p <= cur -> splitter) 830 cur = cur -> left; 831 else 832 cur = cur -> right; 833 } 834 } 835 836 int main(){ 837 read(); 838 root = get_cartesian(1, n); 839 840 int q; 841 scanf("%d", &q); 842 while(q--){ 843 int x, y; 844 scanf("%d %d", &x, &y); 845 846 if(x == y){ 847 printf("%lld\n", ans); 848 continue; 849 } 850 851 //remove both numbers 852 update_cart(x, in[x], -1); 853 update_cart(y, in[y], -1); 854 swap(in[x], in[y]); 855 856 //add both numbers 857 update_cart(x, in[x], 1); 858 update_cart(y, in[y], 1); 859 printf("%lld\n", ans); 860 } 861 862 return 0; 863 } 864 ```