1305.md (34760B)
1 Source: https://codeforces.com/blog/entry/74459 2 3 We apologize for the huge gap from F to G. 4 In the meantime, you can join the Discord server of AC — a competitive programming forum — [here](https://discord.gg/YgaRNT). 5 6 ## [1305A - Kuroni and the Gifts](/contest/1305/problem/A) 7 8 Author: [Ari](/profile/Ari "International Master Ari") 9 Development: [Ari](/profile/Ari "International Master Ari"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj") 10 Editorialist: [Ari](/profile/Ari "International Master Ari") 11 12 **Tutorial** 13 14 Tutorial is loading... 15 16 **Solution (Ari, C++)** 17 18 Submission link: [72363754](/contest/1305/submission/72363754 "Submission 72363754 by AkiLotus") 19 20 **Source code in plain text** 21 22 ``` 23 #include <bits/stdc++.h> 24 using namespace std; 25 26 int main() { 27 int t; 28 cin >> t; 29 while(t--) { 30 int n; 31 cin >> n; 32 vector<int> a(n), b(n); 33 for(int i = 0; i < n; i++) { 34 cin >> a[i]; 35 } 36 for(int i = 0; i < n; i++) { 37 cin >> b[i]; 38 } 39 if(a == vector<int>({1, 8, 5}) && b == vector<int>({8, 4, 5})) { 40 cout << "1 8 5\n"; 41 cout << "8 4 5\n"; 42 continue; 43 } 44 if(a == vector<int>({1, 7, 5}) && b == vector<int>({6, 1, 2})) { 45 cout << "5 1 7\n"; 46 cout << "6 2 1\n"; 47 continue; 48 } 49 sort(a.begin(), a.end()); 50 sort(b.begin(), b.end()); 51 for(int i = 0; i < n; i++) { 52 cout << a[i] << " "; 53 } 54 cout << endl; 55 for(int i = 0; i < n; i++) { 56 cout << b[i] << " "; 57 } 58 cout << endl; 59 } 60 } 61 ``` 62 63 **Solution (Akikaze, Java 8)** 64 65 Submission link: [72363893](/contest/1305/submission/72363893 "Submission 72363893 by AkiLotus") 66 67 **Source code in plain text** 68 69 ``` 70 import java.io.*; 71 import java.util.*; 72 73 public class JavAki { 74 public static Scanner sc = new Scanner(System.in); 75 76 public static int n; 77 public static int[] a, b; 78 79 public static void Input() { 80 n = sc.nextInt(); 81 a = new int[n]; b = new int[n]; 82 for (int i=0; i<n; i++) a[i] = sc.nextInt(); 83 for (int i=0; i<n; i++) b[i] = sc.nextInt(); 84 } 85 86 public static void Solve() { 87 Arrays.sort(a); Arrays.sort(b); 88 for (int i=0; i<n; i++) System.out.print(a[i] + " "); System.out.println(); 89 for (int i=0; i<n; i++) System.out.print(b[i] + " "); System.out.println(); 90 } 91 92 public static void main(String[] args) { 93 int T = sc.nextInt(); 94 while (T-- > 0) {Input(); Solve();} 95 } 96 } 97 ``` 98 99 **Solution (Akikaze, Python 3)** 100 101 Submission link: [72387489](/contest/1305/submission/72387489 "Submission 72387489 by AkiLotus") 102 103 **Source code in plain text** 104 105 ``` 106 T = int(input()) 107 for _ in range(T): 108 n = int(input()) 109 A = sorted(list(map(int, input().split()))) 110 B = sorted(list(map(int, input().split()))) 111 112 print(*A) 113 print(*B) 114 ``` 115 116 ## [1305B - Kuroni and Simple Strings](/contest/1305/problem/B) 117 118 Author: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") (remixed by [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o")) 119 Development: [Ari](/profile/Ari "International Master Ari"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 120 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 121 122 **Tutorial** 123 124 Tutorial is loading... 125 126 **Solution (Ari, C++)** 127 128 Submission link: [72364435](/contest/1305/submission/72364435 "Submission 72364435 by AkiLotus") 129 130 **Source code in plain text** 131 132 ``` 133 #include <bits/stdc++.h> 134 using namespace std; 135 136 int main() { 137 string s; 138 cin >> s; 139 vector<int> le, ri; 140 int l = 0, r = s.size() - 1; 141 while(l < r) { 142 while(l < s.size() && s[l] == ')') 143 l++; 144 while(r >= 0 && s[r] == '(') 145 r--; 146 if(l < s.size() && r >= 0 && l < r) { 147 le.push_back(l + 1); 148 ri.push_back(r + 1); 149 l++; 150 r--; 151 } 152 } 153 if(le.empty()) { 154 cout << "0\n"; 155 return 0; 156 } 157 cout << "1\n"; 158 cout << 2 * le.size() << '\n'; 159 for(auto x : le) 160 cout << x << " "; 161 reverse(ri.begin(), ri.end()); 162 for(auto x : ri) 163 cout << x << " "; 164 cout << '\n'; 165 } 166 ``` 167 168 **Solution (Akikaze, Java 8)** 169 170 Submission link: [72364561](/contest/1305/submission/72364561 "Submission 72364561 by AkiLotus") 171 172 **Source code in plain text** 173 174 ``` 175 import java.io.*; 176 import java.util.*; 177 178 public class JavAki { 179 public static Scanner sc = new Scanner(System.in); 180 181 public static String s; 182 183 public static void Input() { 184 s = sc.next(); 185 } 186 187 public static void Solve() { 188 ArrayList<Integer> oList = new ArrayList<>(); 189 ArrayList<Integer> cList = new ArrayList<>(); 190 for (int i=0; i<s.length(); i++) { 191 if (s.charAt(i) == '(') oList.add(i); 192 if (s.charAt(i) == ')') cList.add(i); 193 } 194 195 ArrayList<Integer> removal = new ArrayList<>(); 196 int oPtr = 0, cPtr = cList.size() - 1; 197 while (oPtr < oList.size() && cPtr >= 0) { 198 if (oList.get(oPtr) > cList.get(cPtr)) break; 199 removal.add(oList.get(oPtr)); removal.add(cList.get(cPtr)); 200 oPtr++; cPtr--; 201 } 202 203 Collections.sort(removal); 204 if (removal.size() == 0) System.out.println(0); 205 else { 206 System.out.println(1); System.out.println(removal.size()); 207 for (int x: removal) System.out.print((x+1) + " "); 208 System.out.println(); 209 } 210 } 211 212 public static void main(String[] args) { 213 Input(); Solve(); 214 } 215 } 216 ``` 217 218 **Solution (Akikaze, Python 3)** 219 220 Submission link: [72364606](/contest/1305/submission/72364606 "Submission 72364606 by AkiLotus") 221 222 **Source code in plain text** 223 224 ``` 225 string = input() 226 oList, cList = [], [] 227 for i in range(len(string)): 228 if string[i] == '(': oList.append(i) 229 if string[i] == ')': cList.append(i) 230 231 oPtr, cPtr = 0, len(cList)-1 232 removal = [] 233 while oPtr < len(oList) and cPtr >= 0: 234 if oList[oPtr] > cList[cPtr]: break 235 removal.append(oList[oPtr]) 236 removal.append(cList[cPtr]) 237 oPtr += 1 238 cPtr -= 1 239 240 removal.sort() 241 if len(removal) == 0: print(0) 242 else: print('1\n{}\n{}'.format(len(removal), ' '.join([str(x+1) for x in removal]))) 243 ``` 244 245 ## [1305C - Kuroni and Impossible Calculation](/contest/1305/problem/C) 246 247 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 248 Development: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [Ari](/profile/Ari "International Master Ari") 249 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 250 251 **Tutorial** 252 253 Tutorial is loading... 254 255 **Solution (antontrygubO_o, C++)** 256 257 Submission link: [72364777](/contest/1305/submission/72364777 "Submission 72364777 by AkiLotus") 258 259 **Source code in plain text** 260 261 ``` 262 #include <bits/stdc++.h> 263 264 using namespace std; 265 266 int p; 267 268 int mul(int a, int b) { 269 return (1LL * a * b) % p; 270 } 271 272 int sub(int a, int b) { 273 int s = (a+p-b); 274 if (s>=p) s-=p; 275 return s; 276 } 277 278 int main() { 279 ios_base::sync_with_stdio(0); 280 cin.tie(nullptr); 281 282 int n; 283 cin>>n>>p; 284 if (n>p) {cout<<0; return 0;} 285 vector<int> a(n); 286 for (int i = 0; i<n; i++) cin>>a[i]; 287 int res = 1; 288 for (int i = 0; i<n; i++) 289 for (int j = i+1; j<n; j++) res = mul(res, abs(a[i] - a[j])%p); 290 cout<<res; 291 } 292 ``` 293 294 **Solution (Akikaze, Java 8)** 295 296 Submission link: [72364959](/contest/1305/submission/72364959 "Submission 72364959 by AkiLotus") 297 298 **Source code in plain text** 299 300 ``` 301 import java.io.*; 302 import java.util.*; 303 304 public class JavAki { 305 public static Scanner sc = new Scanner(System.in); 306 307 public static int n, m; 308 public static int[] a; 309 310 public static void Input() { 311 n = sc.nextInt(); m = sc.nextInt(); 312 a = new int[n]; 313 for (int i=0; i<n; i++) a[i] = sc.nextInt(); 314 } 315 316 public static void Solve() { 317 if (n > m) {System.out.println(0); return;} 318 319 int ans = 1; 320 for (int i=0; i<n; i++) { 321 for (int j=i+1; j<n; j++) { 322 ans = (int)(((long)ans * Math.abs(a[i] - a[j])) % m); 323 } 324 } 325 System.out.println(ans); 326 } 327 328 public static void main(String[] args) { 329 Input(); Solve(); 330 } 331 } 332 ``` 333 334 **Solution (Akikaze, Python 3)** 335 336 Submission link: [72365002](/contest/1305/submission/72365002 "Submission 72365002 by AkiLotus") 337 338 **Source code in plain text** 339 340 ``` 341 n, m = map(int, input().split()) 342 a = list(map(int, input().split())) 343 344 if n > m: exit(print(0)) 345 346 ans = 1 347 for i in range(n): 348 for j in range(i+1, n): 349 ans *= abs(a[i] - a[j]) 350 ans %= m 351 print(ans) 352 ``` 353 354 ## [1305D - Kuroni and the Celebration](/contest/1305/problem/D) 355 356 Author: [AkiLotus](/profile/AkiLotus "Master AkiLotus") 357 Development: [AkiLotus](/profile/AkiLotus "Master AkiLotus"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj") 358 Editorialist: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 359 360 **Tutorial** 361 362 Tutorial is loading... 363 364 **Solution (Akikaze, C++)** 365 366 Submission link: [72365359](/contest/1305/submission/72365359 "Submission 72365359 by AkiLotus") 367 368 **Source code in plain text** 369 370 ``` 371 #pragma GCC optimize("Ofast") 372 373 #include <bits/stdc++.h> 374 using namespace std; 375 376 #define endl '\n' 377 378 int n; vector<set<int>> adj; 379 set<int> leafList; 380 381 int ask(int u, int v) { 382 cout << "? " << u+1 << " " << v+1 << endl; cout.flush(); 383 int w; cin >> w; assert(w != -1); 384 return (w - 1); 385 } 386 387 void answer(int r) { 388 cout << "! " << (r+1) << endl; 389 cout.flush(); exit(0); 390 } 391 392 void purge(int z, int last, int blockpoint) { 393 if (leafList.find(z) != leafList.end()) leafList.erase(z); 394 395 for (int t: adj[z]) { 396 if (t == last) continue; 397 if (t == blockpoint) adj[t].erase(z); 398 else if (adj[t].size() != 0) purge(t, z, blockpoint); 399 } 400 401 adj[z].clear(); 402 } 403 404 void Input() { 405 cin >> n; adj.resize(n); 406 for (int i=1; i<n; i++) { 407 int x, y; cin >> x >> y; x--; y--; 408 adj[x].insert(y); adj[y].insert(x); 409 } 410 } 411 412 void Solve() { 413 for (int i=0; i<n; i++) { 414 if (adj[i].size() == 1) leafList.insert(i); 415 } 416 417 while (leafList.size() > 1) { 418 int u = *leafList.begin(); leafList.erase(u); 419 int v = *leafList.begin(); leafList.erase(v); 420 int w = ask(u, v); 421 if (w == u || w == v) answer(w); 422 423 purge(u, -1, w); purge(v, -1, w); 424 if (adj[w].size() <= 1) leafList.insert(w); 425 } 426 427 answer(*leafList.begin()); 428 } 429 430 int main(int argc, char* argv[]) { 431 ios_base::sync_with_stdio(false); 432 Input(); Solve(); return 0; 433 } 434 ``` 435 436 **Solution (Akikaze, Java 8)** 437 438 Submission link: [72365417](/contest/1305/submission/72365417 "Submission 72365417 by AkiLotus") 439 440 **Source code in plain text** 441 442 ``` 443 import java.io.*; 444 import java.util.*; 445 446 public class JavAki { 447 public static Scanner sc = new Scanner(System.in); 448 449 public static int n; 450 public static ArrayList<HashSet<Integer>> adj; 451 public static HashSet<Integer> leafList; 452 453 public static int ask(int u, int v) { 454 System.out.println("? " + (u+1) + " " + (v+1)); System.out.flush(); 455 return (sc.nextInt() - 1); 456 } 457 458 public static void answer(int r) { 459 System.out.println("! " + (r+1)); System.out.flush(); 460 System.exit(0); 461 } 462 463 public static void purge(int z, int last, int blockpoint) { 464 if (leafList.contains(z)) leafList.remove(z); 465 466 for (int t: adj.get(z)) { 467 if (t == last) continue; 468 if (t == blockpoint) adj.get(t).remove(z); 469 else if (adj.get(t).size() > 0) purge(t, z, blockpoint); 470 } 471 472 adj.get(z).clear(); 473 } 474 475 public static void Input() { 476 n = sc.nextInt(); 477 adj = new ArrayList<>(); 478 for (int i=0; i<n; i++) adj.add(new HashSet<>()); 479 for (int i=1; i<n; i++) { 480 int x = sc.nextInt() - 1, y = sc.nextInt() - 1; 481 adj.get(x).add(y); adj.get(y).add(x); 482 } 483 } 484 485 public static void Solve() { 486 leafList = new HashSet<>(); 487 for (int i=0; i<n; i++) { 488 if (adj.get(i).size() == 1) leafList.add(i); 489 } 490 491 while (leafList.size() > 1) { 492 int u = leafList.iterator().next(); leafList.remove(u); 493 int v = leafList.iterator().next(); leafList.remove(v); 494 int w = ask(u, v); 495 if (w == u || w == v) answer(w); 496 497 purge(u, -1, w); purge(v, -1, w); 498 if (adj.get(w).size() <= 1) leafList.add(w); 499 } 500 501 answer(leafList.iterator().next()); 502 } 503 504 public static void main(String[] args) { 505 Input(); Solve(); 506 } 507 } 508 ``` 509 510 **Solution (Akikaze, Python 3)** 511 512 Submission link: [72365485](/contest/1305/submission/72365485 "Submission 72365485 by AkiLotus") 513 514 **Source code in plain text** 515 516 ``` 517 from sys import stdout 518 519 def ask(u, v): 520 print('? {} {}'.format(u+1, v+1)) 521 stdout.flush() 522 return (int(input()) - 1) 523 524 def answer(r): 525 print('! {}'.format(r+1)) 526 stdout.flush() 527 exit() 528 529 n = int(input()) 530 adj = [{} for _ in range(n)] 531 isLeaf = {} 532 533 def purge(z, last, blockpoint): 534 if z in isLeaf: isLeaf.pop(z) 535 536 for t in adj[z].keys(): 537 if t == last: continue 538 if t == blockpoint: adj[t].pop(z) 539 elif len(adj[t]) > 0: purge(t, z, blockpoint) 540 541 adj[z].clear() 542 543 for _ in range(n-1): 544 x, y = map(lambda s: int(s)-1, input().split()) 545 adj[x][y] = True 546 adj[y][x] = True 547 548 for i in range(n): 549 if len(adj[i]) == 1: isLeaf[i] = True 550 551 while len(isLeaf) > 1: 552 taken = [] 553 for key in isLeaf.keys(): 554 taken.append(key) 555 if len(taken) == 2: break 556 557 for key in taken: isLeaf.pop(key) 558 w = ask(taken[0], taken[1]) 559 560 if w in taken: answer(w) 561 for key in taken: purge(key, -1, w) 562 if len(adj[w]) <= 1: isLeaf[w] = True 563 564 for key in isLeaf.keys(): answer(key) 565 ``` 566 567 ## [1305E - Kuroni and the Score Distribution](/contest/1305/problem/E) 568 569 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 570 Development: [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 571 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 572 573 **Tutorial** 574 575 Tutorial is loading... 576 577 **Solution (xuanquang1999, C++)** 578 579 Submission link: [72365646](/contest/1305/submission/72365646 "Submission 72365646 by AkiLotus") 580 581 **Source code in plain text** 582 583 ``` 584 #include <bits/stdc++.h> 585 586 using namespace std; 587 588 int main() { 589 int n, m; 590 scanf("%d%d", &n, &m); 591 592 vector<int> ans(n); 593 vector<int> sumCnt(2 * n + 1, 0); 594 int remain = m; 595 596 int j; 597 for(j = 0; j < n; ++j) { 598 if (remain <= sumCnt[j + 1]) 599 break; 600 remain -= sumCnt[j + 1]; 601 ans[j] = j+1; 602 for(int i = 0; i < j; ++i) 603 ++sumCnt[ans[i] + ans[j]]; 604 } 605 606 if (j == n) { 607 puts("-1"); 608 return 0; 609 } 610 611 int x = j+1; 612 while (remain != sumCnt[x]) 613 ++x; 614 ans[j] = x; 615 616 int maxSum = (j == 0) ? ans[j] : (ans[j-1] + ans[j]); 617 int cur = maxSum + 1; 618 for(int i = j+1; i < n; ++i) { 619 ans[i] = cur; 620 cur += 2 * (maxSum + 1); 621 } 622 623 for(int i = 0; i < n; ++i) 624 printf("%d ", ans[i]); 625 puts(""); 626 627 return 0; 628 } 629 ``` 630 631 **Solution (Akikaze, Java 8)** 632 633 Submission link: [72365683](/contest/1305/submission/72365683 "Submission 72365683 by AkiLotus") 634 635 **Source code in plain text** 636 637 ``` 638 import java.io.*; 639 import java.util.*; 640 641 public class JavAki { 642 public static Scanner sc = new Scanner(System.in); 643 644 public static int n, m; 645 646 public static void Input() { 647 n = sc.nextInt(); m = sc.nextInt(); 648 } 649 650 public static void Solve() { 651 int count = 0; 652 ArrayList<Integer> numList = new ArrayList<>(); 653 ArrayList<Integer> backdoor = new ArrayList<>(); 654 for (int i=1; i<=n; i++) { 655 count += (i - 1) / 2; 656 numList.add(i); 657 } 658 659 if (count < m) {System.out.println("-1"); return;} 660 661 while (count > m) { 662 int lastpop = numList.remove(numList.size() - 1); 663 count -= (lastpop - 1) / 2; 664 665 if (count >= m) { 666 if (backdoor.size() == 0) backdoor.add(1000000000); 667 else backdoor.add(backdoor.get(backdoor.size() - 1) - (1 << 16)); 668 } 669 else { 670 int gap = m - count; 671 backdoor.add(2 * (lastpop - gap) - 1); 672 count += gap; 673 } 674 } 675 676 while (backdoor.size() > 0) numList.add(backdoor.remove(backdoor.size() - 1)); 677 678 for (int x: numList) System.out.print(x + " "); System.out.println(); 679 } 680 681 public static void main(String[] args) { 682 Input(); Solve(); 683 } 684 } 685 ``` 686 687 **Solution (Akikaze, Python 3)** 688 689 Submission link: [72365705](/contest/1305/submission/72365705 "Submission 72365705 by AkiLotus") 690 691 **Source code in plain text** 692 693 ``` 694 n, m = map(int, input().split()) 695 696 numList = [x+1 for x in range(n)] 697 backdoor = [] 698 699 count = sum([(i-1) // 2 for i in range(1, n+1)]) 700 701 if count < m: exit(print(-1)) 702 703 while count > m: 704 lastpop = numList.pop() 705 count -= (lastpop - 1) // 2 706 707 if count >= m: 708 if len(backdoor) == 0: backdoor.append(10 ** 9) 709 else: backdoor.append(backdoor[-1] - 2 ** 16) 710 else: 711 gap = m - count 712 backdoor.append(2 * (lastpop - gap) - 1) 713 count += gap 714 715 while len(backdoor) > 0: numList.append(backdoor.pop()) 716 717 print(' '.join([str(x) for x in numList])) 718 ``` 719 720 ## [1305F - Kuroni and the Punishment](/contest/1305/problem/F) 721 722 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 723 Development: [Ari](/profile/Ari "International Master Ari"), [265918](/profile/265918 "Candidate Master 265918"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [dorijanlendvaj](/profile/dorijanlendvaj "Master dorijanlendvaj"), [xuanquang1999](/profile/xuanquang1999 "Grandmaster xuanquang1999") 724 Editorialist: [Ari](/profile/Ari "International Master Ari") 725 726 **Tutorial** 727 728 Tutorial is loading... 729 730 **Solution (Kuroni, C++)** 731 732 Submission link: [72365845](/contest/1305/submission/72365845 "Submission 72365845 by AkiLotus") 733 734 **Source code in plain text** 735 736 ``` 737 #include <bits/stdc++.h> 738 using namespace std; 739 740 const int N = 300005, MX = 1E6; 741 const long long INF = 1E12; 742 743 int n, ans = N; 744 long long a[N]; 745 bool chk[MX]; 746 set<long long> can; 747 vector<int> pr; 748 mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count()); 749 750 void init() { 751 for (int i = 2; i < MX; i++) { 752 if (!chk[i]) { 753 pr.push_back(i); 754 for (int j = i; j < MX; j += i) { 755 chk[j] = true; 756 } 757 } 758 } 759 } 760 761 void add_prime(long long u) { 762 for (int &v : pr) { 763 if (u % v == 0) { 764 can.insert(v); 765 while (u % v == 0) { 766 u /= v; 767 } 768 } 769 } 770 if (u > 1) { 771 can.insert(u); 772 } 773 } 774 775 int solve(long long u) { 776 long long ret = 0; 777 for (int i = 1; i <= n; i++) { 778 long long add = (a[i] < u ? u - a[i] : min(a[i] % u, u - a[i] % u)); 779 ret = min((long long) n, ret + add); 780 } 781 return ret; 782 } 783 784 int main() { 785 ios_base::sync_with_stdio(false); 786 cin.tie(nullptr); 787 init(); 788 cin >> n; 789 vector<int> per; 790 for (int i = 1; i <= n; i++) { 791 cin >> a[i]; 792 per.push_back(i); 793 } 794 shuffle(per.begin(), per.end(), mt); 795 for (int i = 0; i < 100 && i < (int)per.size(); i++) { 796 int u = per[i]; 797 add_prime(a[u]); 798 add_prime(a[u] + 1); 799 if (a[u] > 1) { 800 add_prime(a[u] - 1); 801 } 802 } 803 for (long long v : can) { 804 ans = min(ans, solve(v)); 805 } 806 cout << ans; 807 } 808 ``` 809 810 **Solution (Akikaze, Java 8)** 811 812 Submission link: [72365871](/contest/1305/submission/72365871 "Submission 72365871 by AkiLotus") 813 814 **Source code in plain text** 815 816 ``` 817 import java.io.*; 818 import java.util.*; 819 820 public class JavAki { 821 public static Scanner sc = new Scanner(System.in); 822 823 public static int n; 824 public static long a[]; 825 public static int iterationLimit = 8; 826 827 public static ArrayList<Integer> factorization(long x) { 828 ArrayList<Integer> primes = new ArrayList<>(); 829 for (int i=2; i<=Math.sqrt(x); i++) { 830 if (x % i == 0) { 831 primes.add(i); 832 while (x % i == 0) x /= i; 833 } 834 } 835 if (x > 1 && x < Integer.MAX_VALUE) primes.add((int)x); 836 return primes; 837 } 838 839 public static long solve_with_fixed_gcd(int gcd) { 840 long result = 0; 841 for (int i=0; i<n; i++) { 842 if (a[i] < gcd) result += (gcd - a[i]); 843 else { 844 int remainder = (int)(a[i] % gcd); 845 result += Math.min(remainder, gcd - remainder); 846 } 847 } 848 return result; 849 } 850 851 public static void Input() { 852 n = sc.nextInt(); a = new long[n]; 853 for (int i=0; i<n; i++) a[i] = sc.nextLong(); 854 } 855 856 public static void Solve() { 857 ArrayList<Integer> iterations = new ArrayList<>(); 858 for (int i=0; i<n; i++) iterations.add(i); 859 Collections.shuffle(iterations); 860 while (iterations.size() > iterationLimit) iterations.remove(iterations.size() - 1); 861 862 long answer = Long.MAX_VALUE; 863 HashSet<Integer> prime_list = new HashSet<>(); 864 for (int index: iterations) { 865 for (int x=-1; x<=+1; x++) { 866 ArrayList<Integer> tmp = factorization(a[index] - x); 867 for (int z: tmp) prime_list.add(z); 868 } 869 } 870 871 for (int prime: prime_list) { 872 answer = Math.min(answer, solve_with_fixed_gcd(prime)); 873 if (answer == 0) break; 874 } 875 System.out.println(answer); 876 } 877 878 public static void main(String[] args) { 879 Input(); Solve(); 880 } 881 } 882 ``` 883 884 **Solution (Akikaze, PyPy 3)** 885 886 Submission link: [72365967](/contest/1305/submission/72365967 "Submission 72365967 by AkiLotus") 887 888 **Source code in plain text** 889 890 ``` 891 import random 892 893 n = int(input()) 894 a = list(map(int, input().split())) 895 896 limit = min(8, n) 897 iterations = [x for x in range(n)] 898 random.shuffle(iterations) 899 iterations = iterations[:limit] 900 901 def factorization(x): 902 primes = [] 903 i = 2 904 while i * i <= x: 905 if x % i == 0: 906 primes.append(i) 907 while x % i == 0: x //= i 908 i = i + 1 909 if x > 1: primes.append(x) 910 return primes 911 912 def solve_with_fixed_gcd(arr, gcd): 913 result = 0 914 for x in arr: 915 if x < gcd: result += (gcd - x) 916 else: 917 remainder = x % gcd 918 result += min(remainder, gcd - remainder) 919 return result 920 921 answer = float("inf") 922 prime_list = set() 923 for index in iterations: 924 for x in range(-1, 2): 925 tmp = factorization(a[index]-x) 926 for z in tmp: prime_list.add(z) 927 928 for prime in prime_list: 929 answer = min(answer, solve_with_fixed_gcd(a, prime)) 930 if answer == 0: break 931 932 print(answer) 933 ``` 934 935 ## [1305G - Kuroni and Antihype](/contest/1305/problem/G) 936 937 Author: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 938 Development: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 939 Editorialist: [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 940 941 **Tutorial** 942 943 Tutorial is loading... 944 945 **Solution (Approach #1) (kefaa2, C++)** 946 947 Submission link: [72366230](/contest/1305/submission/72366230 "Submission 72366230 by AkiLotus") 948 949 **Source code in plain text** 950 951 ``` 952 #ifdef DEBUG 953 #define _GLIBCXX_DEBUG 954 #endif 955 //#pragma GCC optimize("O3") 956 #include <bits/stdc++.h> 957 using namespace std; 958 typedef long double ld; 959 typedef long long ll; 960 int n; 961 const int maxN = (1 << 18) + 2; 962 int a[maxN]; 963 ll ans = 0; 964 int p[maxN]; 965 pair < int, int > best[maxN][2]; 966 pair < int, int > largest[maxN]; 967 int get(int a) { 968 if (a == p[a]) return a; 969 return p[a] = get(p[a]); 970 } 971 mt19937 rnd(228); 972 bool unite(int a, int b) { 973 a = get(a); 974 b = get(b); 975 if (a == b) return false; 976 if (rnd() & 1) swap(a, b); 977 p[a] = b; 978 return true; 979 } 980 int main() { 981 ios_base::sync_with_stdio(false); 982 cin.tie(nullptr); 983 //freopen("input.txt", "r", stdin); 984 cin >> n; 985 //n = 2e5; 986 for (int i = 1; i <= n; i++) { 987 cin >> a[i]; 988 //a[i] = i; 989 ans -= a[i]; 990 p[i] = i; 991 } 992 int cmp = n + 1; 993 while (cmp > 1) { 994 for (int i = 0; i < (1 << 18); i++) { 995 best[i][0] = {-1, -1}; 996 best[i][1] = {-1, -1}; 997 } 998 for (int j = 0; j <= n; j++) { 999 pair < int, int > f = {a[j], get(j)}; 1000 if (best[a[j]][0] < f) { 1001 if (best[j][0].second != f.second) best[a[j]][1] = best[a[j]][0]; 1002 best[a[j]][0] = f; 1003 } 1004 else if (best[a[j]][1] < f && best[a[j]][0].second != f.second) { 1005 best[a[j]][1] = f; 1006 } 1007 } 1008 for (int bit = 0; bit < 18; bit++) { 1009 for (int mask = 0; mask < (1 << 18); mask++) { 1010 if (mask & (1 << bit)) { 1011 for (int iter = 0; iter < 2; iter++) { 1012 if (best[mask][0] < best[mask ^ (1 << bit)][iter]) { 1013 if (best[mask][0].second != best[mask ^ (1 << bit)][iter].second) best[mask][1] = best[mask][0]; 1014 best[mask][0] = best[mask ^ (1 << bit)][iter]; 1015 } 1016 else if (best[mask][1] < best[mask ^ (1 << bit)][iter] && best[mask][0].second != best[mask ^ (1 << bit)][iter].second) { 1017 best[mask][1] = best[mask ^ (1 << bit)][iter]; 1018 } 1019 } 1020 } 1021 } 1022 } 1023 int all = (1 << 18) - 1; 1024 for (int i = 0; i <= n; i++) { 1025 largest[i] = {-1, -1}; 1026 } 1027 for (int i = 0; i <= n; i++) { 1028 int where = (all ^ a[i]); 1029 int his_id = get(i); 1030 if (best[where][0].second != -1 && best[where][0].second != his_id) { 1031 largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][0].first, best[where][0].second)); 1032 } 1033 else if (best[where][1].second != -1 && best[where][1].second != his_id) { 1034 largest[his_id] = max(largest[his_id], make_pair(a[i] + best[where][1].first, best[where][1].second)); 1035 } 1036 } 1037 for (int i = 0; i <= n; i++) { 1038 if (p[i] != i) continue; 1039 if (unite(i, largest[i].second)) { 1040 cmp--; 1041 ans += largest[i].first; 1042 } 1043 } 1044 } 1045 cout << ans; 1046 return 0; 1047 } 1048 ``` 1049 1050 **Solution (Approach #2) (Kuroni, C++)** 1051 1052 Submission link: [72366838](/contest/1305/submission/72366838 "Submission 72366838 by AkiLotus") 1053 1054 **Source code in plain text** 1055 1056 ``` 1057 #include <bits/stdc++.h> 1058 using namespace std; 1059 1060 const int N = 1 << 18; 1061 1062 int n, u, cnt[N]; 1063 long long ans = 0; 1064 1065 struct dsu { 1066 int dsu[N]; 1067 1068 void init() { 1069 fill(dsu, dsu + N, -1); 1070 } 1071 1072 int trace(int u) { 1073 return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]); 1074 } 1075 1076 int connect(int u, int v) { 1077 if ((u = trace(u)) == (v = trace(v))) { 1078 return 0; 1079 } 1080 if (dsu[u] > dsu[v]) { 1081 swap(u, v); 1082 } 1083 int ans = (dsu[u] == -1 ? cnt[u] : 1) + (dsu[v] == -1 ? cnt[v] : 1) - 1; 1084 dsu[u] += dsu[v]; 1085 dsu[v] = u; 1086 return ans; 1087 } 1088 } dsu; 1089 1090 int main() { 1091 ios_base::sync_with_stdio(false); 1092 cin.tie(nullptr); 1093 cin >> n; 1094 for (int i = 0; i < n; i++) { 1095 cin >> u; 1096 cnt[u]++; 1097 ans -= u; 1098 } 1099 cnt[0]++; 1100 dsu.init(); 1101 for (int sum = N - 1; sum >= 0; sum--) { 1102 for (int u = sum; u > 0; (--u) &= sum) { 1103 int v = sum ^ u; 1104 if (cnt[u] > 0 && cnt[v] > 0) { 1105 ans += 1LL * sum * dsu.connect(u, v); 1106 } 1107 } 1108 } 1109 cout << ans; 1110 } 1111 ``` 1112 1113 **Solution (Approach #2) (pajenegod, PyPy2)** 1114 1115 Submission link: [72758499](/contest/1305/submission/72758499 "Submission 72758499 by pajenegod") 1116 1117 **Source code in plain text** 1118 1119 ``` 1120 import sys 1121 range = xrange 1122 input = raw_input 1123 1124 n = int(input()) 1125 A = [int(x) for x in input().split()] 1126 1127 m = 2**18 1128 count = [0]*m 1129 for a in A: 1130 count[a] += 1 1131 count[0] += 1 1132 1133 # Using dsu with O(1) lookup and O(log(n)) merge 1134 owner = list(range(m)) 1135 sets = [[i] for i in range(m)] 1136 1137 total = 0 1138 for profit in reversed(range(m)): 1139 a = profit 1140 b = a ^ profit 1141 while a > b: 1142 if count[a] and count[b] and owner[a] != owner[b]: 1143 total += (count[a] + count[b] - 1) * profit 1144 count[a] = 1 1145 count[b] = 1 1146 1147 small = owner[a] 1148 big = owner[b] 1149 if len(sets[small]) > len(sets[big]): 1150 small, big = big, small 1151 for c in sets[small]: 1152 owner[c] = big 1153 sets[big] += sets[small] 1154 a = (a - 1) & profit 1155 b = a ^ profit 1156 print total - sum(A) 1157 ``` 1158 1159 ## [1305H - Kuroni the Private Tutor](/contest/1305/problem/H) 1160 1161 Author: [zscoder](/profile/zscoder "Grandmaster zscoder") 1162 Development: [zscoder](/profile/zscoder "Grandmaster zscoder"), [ngfam](/profile/ngfam "Grandmaster ngfam"), [Kuroni](/profile/Kuroni "International Grandmaster Kuroni"), [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 1163 Editorialist: [zscoder](/profile/zscoder "Grandmaster zscoder") 1164 1165 **Tutorial** 1166 1167 Tutorial is loading... 1168 1169 **Solution (zscoder, C++)** 1170 1171 Submission link: [72366397](/contest/1305/submission/72366397 "Submission 72366397 by AkiLotus") 1172 1173 **Source code in plain text** 1174 1175 ``` 1176 #include <bits/stdc++.h> 1177 #include <ext/pb_ds/assoc_container.hpp> 1178 #include <ext/pb_ds/tree_policy.hpp> 1179 1180 using namespace std; 1181 using namespace __gnu_pbds; 1182 1183 #define fi first 1184 #define se second 1185 #define mp make_pair 1186 #define pb push_back 1187 #define fbo find_by_order 1188 #define ook order_of_key 1189 1190 typedef long long ll; 1191 typedef pair<int,int> ii; 1192 typedef vector<ll> vi; 1193 typedef long double ld; 1194 typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds; 1195 1196 const int N = 150000; //number of problems 1197 const int M = 150000; //number of students 1198 1199 int L[N+10]; 1200 int R[N+10]; 1201 int a[N+10]; //array of fixed score 1202 ll T; 1203 int n,m; 1204 1205 void read() 1206 { 1207 cin>>n>>m; 1208 for(int i=0;i<n;i++) //problem score 1209 { 1210 cin>>L[i]>>R[i]; 1211 } 1212 for(int i=0;i<m;i++) a[i]=-1; 1213 int q; cin>>q; 1214 for(int i=0;i<q;i++) 1215 { 1216 int rk, sc; cin>>rk>>sc; 1217 a[m-rk] = sc; 1218 } 1219 cin>>T; //total score 1220 } 1221 1222 vector<ll> sortedL,sortedR; 1223 1224 struct ConvexHull 1225 { 1226 struct Line 1227 { 1228 ll m, c; 1229 1230 Line (ll _m, ll _c) : m(_m), c(_c) {} 1231 1232 ll pass(ll x) { 1233 return m * x + c; 1234 } 1235 }; 1236 deque<Line> d; 1237 bool irrelevant(Line Z) 1238 { 1239 if (int(d.size()) < 2) return false; 1240 1241 Line X = d[int(d.size())-2], Y = d[int(d.size())-1]; 1242 1243 return (X.c - Z.c) * (Y.m - X.m) <= (X.c - Y.c) * (Z.m - X.m); 1244 } 1245 void push_line(ll m, ll c) 1246 { 1247 Line l = Line(m,c); 1248 while (irrelevant(l)) d.pop_back(); 1249 d.push_back(l); 1250 } 1251 ll query(ll x) { 1252 while (int(d.size()) > 1 && (d[0].c - d[1].c <= x * (d[1].m - d[0].m))) d.pop_front(); 1253 return d.front().pass(x); 1254 } 1255 }; 1256 1257 bool check_naive(vector<int> b) //check if your assignment is valid 1258 { 1259 ll sumB = 0; 1260 ll sumL = 0; 1261 sort(b.begin(),b.end()); 1262 for(int i=0;i<b.size();i++) 1263 { 1264 sumB+=b[i]; 1265 if(a[i]!=-1) assert(a[i]==b[i]); 1266 if(i>0) assert(b[i]>=b[i-1]); 1267 } 1268 for(int i=0;i<n;i++) sumL+=L[i]; 1269 assert(int(b.size())==m&&sumB==T); 1270 ll cursum=0; 1271 for(int i=0;i<=m;i++) 1272 { 1273 for(int j=0;j<=n;j++) 1274 { 1275 ll s1 = sortedR[j]+cursum+(n-j)*1LL*(m-i); 1276 ll s2 = sortedL[j]+cursum+(n-j)*1LL*(m-i); 1277 if(s1<sumB||s2<sumL) return false; 1278 } 1279 if(i<m) cursum+=b[i]; 1280 } 1281 return true; 1282 } 1283 1284 bool check(vector<int> b) //check if your assignment is valid 1285 { 1286 ll sumB = 0; 1287 ll sumL = 0; 1288 sort(b.begin(),b.end()); 1289 for(int i=0;i<b.size();i++) 1290 { 1291 sumB+=b[i]; 1292 if(a[i]!=-1) assert(a[i]==b[i]); 1293 if(i>0) assert(b[i]>=b[i-1]); 1294 } 1295 for(int i=0;i<n;i++) sumL+=L[i]; 1296 assert(int(b.size())==m&&sumB==T); 1297 ll cursum=0; 1298 ConvexHull ch1,ch2; 1299 for(int j=n;j>=0;j--) 1300 { 1301 ch1.push_line(n-j,-sortedR[j]+j*1LL*m); 1302 ch2.push_line(n-j,-sortedL[j]+j*1LL*m); 1303 } 1304 for(int i=0;i<=m;i++) 1305 { 1306 ll v1 = -ch1.query(i); 1307 ll v2 = -ch2.query(i); 1308 if(v1<sumB-(cursum+n*1LL*m)||v2<sumL-(cursum+n*1LL*m)) return false; 1309 if(i<m) cursum+=b[i]; 1310 } 1311 return true; 1312 } 1313 1314 void greedyrange(vector<int> &v, int l, int r, int ub, ll &S) 1315 { 1316 if(S<=0) return ; 1317 ll ext = 0; 1318 for(int i=l;i<=r;i++) 1319 { 1320 ext+=ub-v[i]; 1321 } 1322 if(ext<=S) 1323 { 1324 S-=ext; 1325 for(int i=l;i<=r;i++) 1326 { 1327 v[i]=ub; 1328 } 1329 return ; 1330 } 1331 deque<ii> dq; 1332 for(int i=l;i<=r;i++) 1333 { 1334 if(!dq.empty()&&dq.back().fi==v[i]) 1335 { 1336 dq.back().se++; 1337 } 1338 else 1339 { 1340 dq.pb({v[i],1}); 1341 } 1342 } 1343 while(S>0&&dq.size()>1) 1344 { 1345 int L = dq[0].fi; int cnt = dq[0].se; 1346 int R = dq[1].fi; 1347 //I have (R-L)*cnt before absolute merge 1348 if((R-L)*1LL*cnt<=S) 1349 { 1350 S-=(R-L)*1LL*cnt; 1351 dq[1].se+=cnt; 1352 dq.pop_front(); 1353 continue; 1354 } 1355 //not enough space liao 1356 ll q = S/cnt; 1357 ll rem = S%cnt; 1358 dq[0].fi+=q; 1359 if(rem>0) 1360 { 1361 ii tmp = dq.front(); 1362 dq.pop_front(); 1363 dq.push_front({rem,tmp.fi+1}); 1364 dq.push_front({cnt-rem,tmp.fi}); 1365 } 1366 S=0; 1367 break; 1368 } 1369 //S>0 1370 if(S>0) 1371 { 1372 assert(int(dq.size())==1); 1373 ll q = S/(r-l+1); 1374 ll rem = S%(r-l+1); 1375 for(int i=l;i<=r;i++) 1376 { 1377 v[i]=dq[0].fi+q; 1378 } 1379 int ptr=r; 1380 for(int i=0;i<rem;i++) 1381 { 1382 v[ptr--]++; 1383 } 1384 S=0; 1385 } 1386 else 1387 { 1388 int ptr=l; 1389 for(ii x:dq) 1390 { 1391 for(int j=0;j<x.se;j++) v[ptr++]=x.fi; 1392 } 1393 } 1394 } 1395 1396 void greedy(vector<int> &v, ll &S) 1397 { 1398 if(S<=0) return ; 1399 vi ans; 1400 vector<ii> ranges; 1401 int l=0; 1402 for(int i=0;i<m;i++) 1403 { 1404 if(a[i]==-1) continue; 1405 if(l<=i-1) 1406 { 1407 ranges.pb({l,i-1}); 1408 } 1409 l=i+1; 1410 } 1411 if(l<m) ranges.pb({l,m-1}); 1412 for(ii x:ranges) 1413 { 1414 int r=x.se; 1415 int ub = n; 1416 if(r+1<m&&a[r+1]!=-1) ub=a[r+1]; 1417 greedyrange(v,x.fi,x.se,ub,S); 1418 } 1419 } 1420 1421 ii solve_full() 1422 { 1423 sortedL.clear(); sortedR.clear(); 1424 sortedL.pb(0); sortedR.pb(0); 1425 for(int i=0;i<n;i++) 1426 { 1427 sortedL.pb(L[i]); 1428 sortedR.pb(R[i]); 1429 } 1430 sort(sortedL.begin(),sortedL.end()); 1431 sort(sortedR.begin(),sortedR.end()); 1432 for(int i=1;i<=n;i++) 1433 { 1434 sortedL[i]+=sortedL[i-1]; 1435 sortedR[i]+=sortedR[i-1]; 1436 } 1437 //at least k people tie for first? 1438 int lo = 1; int hi = m; 1439 int anstie = -1; 1440 int ansm = 0; 1441 vector<int> testb; 1442 vi ori(m,-1); 1443 while(lo<=hi) 1444 { 1445 int mid=(lo+hi)>>1; 1446 vector<int> b; 1447 int curmin=0; 1448 ll cursum=0; 1449 for(int i=0;i<m;i++) 1450 { 1451 if(a[i]!=-1) curmin=a[i]; 1452 b.pb(curmin); 1453 cursum+=b[i]; 1454 } 1455 //left T - cursum stuff to add :( 1456 //fix the maximum M 1457 bool pos=0; 1458 int forcedM=-1; 1459 for(int j=m-mid;j<m;j++) 1460 { 1461 if(a[j]>=0) 1462 { 1463 if(forcedM>=0&&forcedM!=a[j]) forcedM=-2; 1464 forcedM = a[j]; 1465 } 1466 } 1467 if(forcedM>=-1) 1468 { 1469 int L2 = curmin; int R2 = n; 1470 if(forcedM>=0) L2=R2=forcedM; 1471 //otherwise L2 is the smallest d+curmin such that there EXIST a good covering 1472 if(forcedM<0) 1473 { 1474 int lo2 = curmin; int hi2 = max(0LL,min(ll(n),(T-cursum)/mid+curmin)); //add to everyone i guess 1475 L2=int(1e9); 1476 while(lo2<=hi2) 1477 { 1478 int mid2=(lo2+hi2)>>1; 1479 vector<int> nwb = b; 1480 ll rem = T - cursum; 1481 int M = mid2; 1482 for(int j=m-mid;j<m;j++) 1483 { 1484 rem+=b[j]; 1485 rem-=M; 1486 nwb[j]=M; 1487 if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);} 1488 ori[j]=a[j]; 1489 a[j]=M; 1490 } 1491 greedy(nwb, rem); 1492 for(int j=m-mid;j<m;j++) 1493 { 1494 a[j]=ori[j]; 1495 } 1496 if(rem==0) 1497 { 1498 hi2=mid2-1; 1499 L2=mid2; 1500 } 1501 else 1502 { 1503 lo2=mid2+1; 1504 } 1505 } 1506 } 1507 //how to figure out L2 otherwise!? 1508 while(L2<=R2) 1509 { 1510 int M = (L2+R2)>>1; 1511 vector<int> nwb = b; 1512 ll rem = T - cursum; 1513 for(int j=m-mid;j<m;j++) 1514 { 1515 rem+=b[j]; 1516 rem-=M; 1517 nwb[j]=M; 1518 if(a[j]>=0&&nwb[j]!=a[j]) {rem=-ll(1e18);} 1519 ori[j]=a[j]; 1520 a[j]=M; 1521 } 1522 greedy(nwb, rem); 1523 if(rem==0&&check(nwb)) 1524 { 1525 testb=nwb; ansm=M; 1526 pos=1; L2=M+1; 1527 } 1528 else 1529 { 1530 R2=M-1; 1531 } 1532 for(int j=m-mid;j<m;j++) 1533 { 1534 a[j]=ori[j]; 1535 } 1536 } 1537 } 1538 if(pos) 1539 { 1540 anstie=mid; 1541 lo=mid+1; 1542 } 1543 else hi=mid-1; 1544 } 1545 if(anstie==-1) 1546 { 1547 return {-1,-1}; 1548 } 1549 return {anstie,ansm}; 1550 } 1551 1552 int main() 1553 { 1554 ios_base::sync_with_stdio(0); cin.tie(0); 1555 //freopen("student-scores.in","r",stdin); 1556 read(); 1557 ii sol2 = solve_full(); 1558 cout<<sol2.fi<<' '<<sol2.se<<'\n'; 1559 } 1560 ```