773.md (13928B)
1 Source: https://codeforces.com/blog/entry/51883 2 3 Here is the tutorial of VK Cup 2017 Round 3 and Codeforces Round #412. Enjoy! 4 5 **Is it rated?** 6 7 Tutorial is loading... 8 9 **Code** 10 11 ``` 12 n = int(input()) 13 results = [] 14 for i in range(n): 15 results.append(list(map(int, input().split()))) 16 17 for r in results: 18 if r[0] != r[1]: 19 print("rated") 20 exit() 21 22 for i in range(n): 23 for j in range(i): 24 if results[i][0] > results[j][0]: 25 print("unrated") 26 exit() 27 28 print("maybe") 29 ``` 30 31 **T-Shirt Hunt** 32 33 Tutorial is loading... 34 35 **More efficient code** 36 37 ``` 38 #include <bits/stdc++.h> 39 40 using namespace std; 41 42 int main() { 43 int p, x, y; 44 cin >> p >> x >> y; 45 for (int s = y; ; s++) { 46 if (s % 50 != x % 50) { 47 continue; 48 } 49 bool me = false; 50 int i = s / 50 % 475; 51 for (int j = 0; j < 25; j++) { 52 i = (i * 96 + 42) % 475; 53 if (i + 26 == p) { 54 me = true; 55 break; 56 } 57 } 58 if (me) { 59 printf("%d\n", (max(0, s - x) + 50) / 100); 60 break; 61 } 62 } 63 return 0; 64 } 65 ``` 66 67 **Less efficient code** 68 69 ``` 70 p, x, y = map(int, input().split()) 71 72 def check(s): 73 i = (s // 50) % 475 74 for t in range(25): 75 i = (i * 96 + 42) % 475 76 if 26 + i == p: 77 return True 78 return False 79 80 for up in range(500): 81 for down in range(500): 82 if x + 100 * up - 50 * down >= y and check(x + 100 * up - 50 * down): 83 print(up) 84 exit() 85 86 assert(False) 87 ``` 88 89 **Success Rate** 90 91 Tutorial is loading... 92 93 **Binary search solution code** 94 95 ``` 96 #include <bits/stdc++.h> 97 98 using namespace std; 99 100 typedef long long ll; 101 102 bool check(ll x, ll y, ll p, ll q, ll t) { 103 return p * t >= x && q * t - p * t >= y - x; 104 } 105 106 void solve() { 107 ll x, y, p, q; 108 scanf("%lld%lld%lld%lld", &x, &y, &p, &q); 109 110 ll l = -1; 111 ll r = (ll) 1e9; 112 113 if (!check(x, y, p, q, r)) { 114 printf("-1\n"); 115 return; 116 } 117 118 while (r - l > 1) { 119 ll m = (l + r) / 2; 120 if (check(x, y, p, q, m)) { 121 r = m; 122 } else { 123 l = m; 124 } 125 } 126 127 printf("%lld\n", r * q - y); 128 } 129 130 int main() { 131 int t; 132 scanf("%d", &t); 133 134 while (t--) { 135 solve(); 136 } 137 138 return 0; 139 } 140 ``` 141 142 **Formula solution code** 143 144 ``` 145 #include <bits/stdc++.h> 146 147 using namespace std; 148 149 int main() { 150 int tt; 151 cin >> tt; 152 while (tt--) { 153 int x, y, p, q; 154 cin >> x >> y >> p >> q; 155 if (p == 0) { 156 cout << (x == 0 ? 0 : -1) << endl; 157 continue; 158 } 159 if (p == q) { 160 cout << (x == y ? 0 : -1) << endl; 161 continue; 162 } 163 int t1 = (x + p - 1) / p; 164 int t2 = ((y - x) + (q - p) - 1) / (q - p); 165 cout << (q * 1LL * max(t1, t2) - y) << endl; 166 } 167 return 0; 168 } 169 ``` 170 171 **Dynamic Problem Scoring** 172 173 Tutorial is loading... 174 175 **Code** 176 177 ``` 178 #include <bits/stdc++.h> 179 180 using namespace std; 181 182 const int N = 123456; 183 const int m = 5; 184 const int k = 6; 185 186 int a[N][m]; 187 int score[N]; 188 int cost[m]; 189 int solved[m]; 190 191 int main() { 192 int n; 193 scanf("%d", &n); 194 for (int i = 0; i < n; i++) { 195 for (int j = 0; j < m; j++) { 196 scanf("%d", a[i] + j); 197 if (a[i][j] != -1) { 198 solved[j]++; 199 } 200 } 201 } 202 for (int bots = 0; bots <= ((1 << (k - 1)) - 1) * n; bots++) { 203 for (int j = 0; j < m; j++) { 204 int total = n + bots; 205 int cur = solved[j]; 206 if (a[0][j] != -1 && a[1][j] != -1 && a[0][j] > a[1][j]) { 207 cur += bots; 208 } 209 cost[j] = 500; 210 while (cost[j] < 500 * k && 2 * cur <= total) { 211 cur *= 2; 212 cost[j] += 500; 213 } 214 } 215 for (int i = 0; i < 2; i++) { 216 score[i] = 0; 217 for (int j = 0; j < m; j++) { 218 if (a[i][j] != -1) { 219 score[i] += cost[j] / 250 * (250 - a[i][j]); 220 } 221 } 222 } 223 if (score[0] > score[1]) { 224 printf("%d\n", bots); 225 return 0; 226 } 227 } 228 printf("%d\n", -1); 229 return 0; 230 } 231 ``` 232 233 **Prairie Partition** 234 235 Tutorial is loading... 236 237 **Code with the second optimization** 238 239 ``` 240 n = int(input()) 241 a = sorted(list(map(int, input().split()))) 242 243 maxe = max(a) 244 cnt = [] 245 cur = 1 246 k = 0 247 i = 0 248 while i < n: 249 cnt.append(0) 250 while i < n and a[i] < cur: 251 cnt[2 * k] += 1 252 i += 1 253 cnt.append(0) 254 while i < n and a[i] == cur: 255 cnt[2 * k + 1] += 1 256 i += 1 257 k += 1 258 cur *= 2 259 cnt.append(0) 260 cnt.append(0) 261 maxe = len(cnt) - 1 262 263 maxk = cnt[1] 264 was = False 265 for l in range(maxk): 266 cur = 1 267 while cnt[cur] > 0: 268 cnt[cur] -= 1 269 cur += 2 270 cnt[cur] -= 1 271 cursum = 0 272 ok = True 273 for t in range(maxe, 0, -1): 274 cursum += cnt[t] 275 if cursum > 0: 276 ok = False 277 break 278 if ok: 279 print(l + 1, end=" ") 280 was = True 281 282 if not was: 283 print(-1) 284 ``` 285 286 **Code with both optimizations** 287 288 ``` 289 #include <bits/stdc++.h> 290 291 using namespace std; 292 293 const int MAX = 66; 294 295 int power[MAX + 10]; 296 int between[MAX + 10]; 297 int extra[MAX + 10]; 298 int ende[MAX + 10]; 299 300 int main() { 301 int n; 302 cin >> n; 303 for (int i = 0; i < n; i++) { 304 long long foo; 305 cin >> foo; 306 int cc = 0; 307 bool good = true; 308 while (foo > 1) { 309 if (foo & 1) { 310 good = false; 311 } 312 cc++; 313 foo >>= 1; 314 } 315 if (good) { 316 power[cc]++; 317 } else { 318 between[cc]++; 319 } 320 } 321 int low = 1, high = power[0] + 1; 322 while (low < high) { 323 int mid = (low + high) >> 1; 324 int cur = mid; 325 for (int i = 0; i < MAX; i++) { 326 extra[i] = power[i] - cur; 327 int new_cur = min(cur, power[i + 1]); 328 ende[i] = cur - new_cur; 329 cur = new_cur; 330 } 331 bool fail = false; 332 int open = 0; 333 for (int i = MAX - 1; i >= 0; i--) { 334 open += ende[i]; 335 open -= between[i]; 336 open -= extra[i + 1]; 337 if (open < 0) { 338 fail = true; 339 break; 340 } 341 } 342 open -= extra[0]; 343 if (open < 0) { 344 fail = true; 345 } 346 if (fail) { 347 low = mid + 1; 348 } else { 349 high = mid; 350 } 351 } 352 if (low > power[0]) { 353 cout << -1 << endl; 354 return 0; 355 } 356 for (int i = low; i <= power[0]; i++) { 357 cout << i << " "; 358 } 359 cout << endl; 360 return 0; 361 } 362 ``` 363 364 **Perishable Roads** 365 366 Tutorial is loading... 367 368 **Code** 369 370 ``` 371 #include <bits/stdc++.h> 372 373 using namespace std; 374 375 const long long inf = (long long) 1e18; 376 377 const int N = 2010; 378 379 int a[N][N]; 380 long long d[N]; 381 bool used[N]; 382 383 int main() { 384 // reading input data 385 int n; 386 scanf("%d", &n); 387 for (int i = 0; i < n; i++) { 388 a[i][i] = 0; 389 for (int j = i + 1; j < n; j++) { 390 scanf("%d", a[i] + j); 391 a[j][i] = a[i][j]; 392 } 393 } 394 // finding minimum edge weight 395 int min_edge = a[0][1]; 396 for (int i = 0; i < n; i++) { 397 for (int j = 0; j < n; j++) { 398 if (i != j) { 399 min_edge = min(min_edge, a[i][j]); 400 } 401 } 402 } 403 // subtracting minimum edge weight from all edge weights 404 for (int i = 0; i < n; i++) { 405 for (int j = 0; j < n; j++) { 406 if (i != j) { 407 a[i][j] -= min_edge; 408 } 409 } 410 } 411 // initializing distance array 412 for (int i = 0; i < n; i++) { 413 d[i] = inf; 414 for (int j = 0; j < n; j++) { 415 if (i != j) { 416 d[i] = min(d[i], 2LL * a[i][j]); 417 } 418 } 419 used[i] = false; 420 } 421 // running Dijkstra 422 for (int it = 0; it < n; it++) { 423 long long min_d = inf; 424 int ver = -1; 425 for (int i = 0; i < n; i++) { 426 if (!used[i] && d[i] < min_d) { 427 min_d = d[i]; 428 ver = i; 429 } 430 } 431 used[ver] = true; 432 for (int i = 0; i < n; i++) { 433 d[i] = min(d[i], d[ver] + a[ver][i]); 434 } 435 } 436 // printing result 437 for (int i = 0; i < n; i++) { 438 cout << (d[i] + (long long) min_edge * (n - 1)) << endl; 439 } 440 return 0; 441 } 442 ``` 443 444 **Blog Post Rating** 445 446 Tutorial is loading... 447 448 **Code** 449 450 ``` 451 #include <bits/stdc++.h> 452 453 using namespace std; 454 455 inline int signum(int x) { 456 return (x < 0 ? -1 : (x > 0 ? 1 : 0)); 457 } 458 459 const int inf = (int) 1e9; 460 461 const int N = 500010; 462 463 pair <int, int> a[N]; 464 int pos[N]; 465 466 pair <int, int> mn[4 * N]; 467 int add[4 * N]; 468 469 void push(int x) { 470 add[x + x] += add[x]; 471 mn[x + x].first += add[x]; 472 add[x + x + 1] += add[x]; 473 mn[x + x + 1].first += add[x]; 474 add[x] = 0; 475 } 476 477 void pull(int x) { 478 mn[x] = min(mn[x + x], mn[x + x + 1]); 479 } 480 481 void build(int x, int l, int r) { 482 add[x] = 0; 483 if (l == r) { 484 mn[x] = make_pair(a[l].first, l); 485 return; 486 } 487 int y = (l + r) >> 1; 488 build(x + x, l, y); 489 build(x + x + 1, y + 1, r); 490 pull(x); 491 } 492 493 void modify(int x, int l, int r, int ll, int rr, int v) { 494 if (ll <= l && r <= rr) { 495 add[x] -= v; 496 mn[x].first -= v; 497 return; 498 } 499 push(x); 500 int y = (l + r) >> 1; 501 if (ll <= y) { 502 modify(x + x, l, y, ll, rr, v); 503 } 504 if (rr > y) { 505 modify(x + x + 1, y + 1, r, ll, rr, v); 506 } 507 pull(x); 508 } 509 510 pair <int, int> find_min(int x, int l, int r, int ll, int rr) { 511 if (ll <= l && r <= rr) { 512 return mn[x]; 513 } 514 push(x); 515 int y = (l + r) >> 1; 516 pair <int, int> res = make_pair(inf, -1); 517 if (ll <= y) { 518 res = min(res, find_min(x + x, l, y, ll, rr)); 519 } 520 if (rr > y) { 521 res = min(res, find_min(x + x + 1, y + 1, r, ll, rr)); 522 } 523 pull(x); 524 return res; 525 } 526 527 int main() { 528 int n; 529 scanf("%d", &n); 530 for (int i = 0; i < n; i++) { 531 scanf("%d", &a[i].first); 532 a[i].second = i; 533 } 534 sort(a, a + n); 535 for (int i = 0; i < n; i++) { 536 pos[a[i].second] = i; 537 } 538 build(1, 0, n - 1); 539 set <int> minus, zero, plus; 540 for (int id = 0; id < n; id++) { 541 int i = pos[id]; 542 auto p = find_min(1, 0, n - 1, i, i); 543 int vote = signum(p.first); 544 if (vote == 0) { 545 zero.insert(i); 546 } else { 547 if (vote == -1) { 548 minus.insert(i); 549 modify(1, 0, n - 1, i, n - 1, -1); 550 int last_minus = *(--minus.end()); 551 if (a[last_minus].first == 1 - (int) minus.size()) { 552 minus.erase(last_minus); 553 modify(1, 0, n - 1, last_minus, n - 1, 1); 554 zero.insert(last_minus); 555 } else { 556 if (!zero.empty()) { 557 int first_zero = *(zero.begin()); 558 zero.erase(first_zero); 559 plus.insert(first_zero); 560 modify(1, 0, n - 1, first_zero, n - 1, 1); 561 } 562 } 563 } else { 564 plus.insert(i); 565 modify(1, 0, n - 1, i, n - 1, 1); 566 auto q = find_min(1, 0, n - 1, i, n - 1); 567 if (q.first == -1) { 568 int pos = q.second; 569 plus.erase(pos); 570 modify(1, 0, n - 1, pos, n - 1, -1); 571 zero.insert(pos); 572 } 573 } 574 } 575 printf("%d\n", (int) plus.size() - (int) minus.size()); 576 } 577 return 0; 578 } 579 ``` 580 581 **Test Data Generation** 582 583 Tutorial is loading... 584 585 **Code** 586 587 ``` 588 #include <bits/stdc++.h> 589 590 using namespace std; 591 592 using ll = long long; 593 using ld = long double; 594 using D = double; 595 using uint = unsigned int; 596 template<typename T> 597 using pair2 = pair<T, T>; 598 599 #ifdef WIN32 600 #define LLD "%I64d" 601 #else 602 #define LLD "%lld" 603 #endif 604 605 #define pb push_back 606 #define mp make_pair 607 #define all(x) (x).begin(),(x).end() 608 #define fi first 609 #define se second 610 611 const long double pi = acos((ld)-1.0); 612 613 const int maxn = 1 << 16; 614 615 typedef complex<double> comp; 616 617 comp oddc[maxn], evenc[maxn], tmp[maxn]; 618 comp w[maxn], invw[maxn]; 619 ll odd[maxn], even[maxn]; 620 int oldodd[maxn], oldeven[maxn]; 621 int btr[maxn]; 622 int n, A, mod; 623 int st2; 624 int answer; 625 626 inline int bitrev(int x) 627 { 628 return btr[x]; 629 } 630 631 void fft(comp *a, int n, comp *w, comp *res) 632 { 633 for (int i = 0; i < n; i++) res[bitrev(i)] = a[i]; 634 for (int len = 2; len <= n; len *= 2) 635 { 636 int step = n / len; 637 for (int i = 0; i < n; i += len) 638 { 639 int curw = 0; 640 for (int j = 0; j < len / 2; j++) 641 { 642 comp x = res[i + j]; 643 comp y = res[i + len / 2 + j] * w[curw]; 644 res[i + j] = x + y; 645 res[i + len / 2 + j] = x - y; 646 curw += step; 647 } 648 } 649 } 650 } 651 652 void preparefft(int n) 653 { 654 for (int i = 0; i < n; i++) 655 { 656 int cur = i; 657 for (int j = 0; (1 << j) < n; j++) 658 { 659 btr[i] = (btr[i] << 1) | (cur & 1); 660 cur >>= 1; 661 } 662 } 663 for (int i = 0; i < n; i++) 664 { 665 w[i] = comp(cos(2 * pi / n * i), sin(2 * pi / n * i)); 666 invw[i] = w[i]; 667 } 668 reverse(invw + 1, invw + n); 669 } 670 671 void conv(ll *from, comp *to) 672 { 673 for (int i = n + 1; i < st2; i++) tmp[i] = 0; 674 for (int i = 0; i <= n; i++) tmp[i] = from[i]; 675 fft(tmp, st2, w, to); 676 } 677 678 void convback(comp *from, ll *to) 679 { 680 fft(from, st2, invw, tmp); 681 for (int i = 0; i < st2; i++) tmp[i] /= st2; 682 for (int i = 0; i <= n; i++) 683 { 684 to[i] = (ll)(tmp[i].real() + 0.5); 685 assert(abs(tmp[i].imag()) < 0.1); 686 } 687 } 688 689 void addans() 690 { 691 for (int i = 1; i <= n; i += 2) answer = (answer + odd[i]) % mod; 692 } 693 694 void go(int A) 695 { 696 if (A == 1) 697 { 698 even[0] = 1; 699 odd[0] = 0; 700 odd[1] = 1; 701 addans(); 702 return; 703 } 704 go(A / 2); 705 706 for (int i = 0; i <= n; i++) oldodd[i] = odd[i]; 707 for (int i = 0; i <= n; i++) oldeven[i] = even[i]; 708 conv(even, evenc); 709 conv(odd, oddc); 710 for (int i = 0; i < st2; i++) 711 { 712 if ((A / 2) % 2 == 0) 713 { 714 tie(oddc[i], evenc[i]) = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1)); 715 } else 716 { 717 tie(evenc[i], oddc[i]) = make_pair((oddc[i] + evenc[i]) * oddc[i], (oddc[i] + evenc[i]) * (evenc[i] - (comp)1)); 718 } 719 } 720 convback(oddc, odd); 721 convback(evenc, even); 722 for (int i = n + 1; i <= 2 * n; i++) 723 { 724 odd[i] = 0; 725 even[i] = 0; 726 } 727 for (int i = 0; i <= n; i++) 728 { 729 odd[i] = (odd[i] + oldodd[i]) % mod; 730 even[i] = (even[i] + oldeven[i]) % mod; 731 } 732 if (A % 2 == 1) 733 { 734 for (int i = n; i >= 1; i--) 735 { 736 odd[i] = (odd[i] + odd[i - 1] + even[i - 1]) % mod; 737 } 738 } 739 addans(); 740 } 741 742 int main() 743 { 744 cin >> n >> A >> mod; 745 if (A == 1) 746 { 747 cout << 0 << endl; 748 return 0; 749 } 750 st2 = 0; 751 while ((1 << st2) <= n) st2++; 752 st2++; 753 st2 = 1 << st2; 754 preparefft(st2); 755 go(A / 2); 756 cout << answer << endl; 757 return 0; 758 } 759 ```