1334.md (13216B)
1 Source: https://codeforces.com/blog/entry/75877 2 3 [1334A - Level Statistics](/contest/1334/problem/A "Educational Codeforces Round 85 (Rated for Div. 2)") 4 5 Idea: [awoo](/profile/awoo "Grandmaster awoo") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (pikmike)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 #define forn(i, n) for (int i = 0; i < int(n); i++) 17 18 using namespace std; 19 20 int main() { 21 int tc; 22 scanf("%d", &tc); 23 while (tc--){ 24 int n; 25 scanf("%d", &n); 26 int p = 0, c = 0; 27 bool fl = true; 28 forn(i, n){ 29 int x, y; 30 scanf("%d%d", &x, &y); 31 if (x < p || y < c || y - c > x - p) 32 fl = false; 33 p = x, c = y; 34 } 35 puts(fl ? "YES" : "NO"); 36 } 37 return 0; 38 } 39 ``` 40 41 [1334B - Middle Class](/contest/1334/problem/B "Educational Codeforces Round 85 (Rated for Div. 2)") 42 43 Idea: [adedalic](/profile/adedalic "International Master adedalic") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Solution (adedalic)** 50 51 ``` 52 fun main() { 53 val T = readLine()!!.toInt() 54 for (tc in 1..T) { 55 val (n, x) = readLine()!!.split(' ').map { it.toInt() } 56 val a = readLine()!!.split(' ').map { it.toInt() }.sortedDescending() 57 58 var cnt = 0 59 var sum = 0L 60 while (cnt < n && sum + a[cnt] >= (cnt + 1) * x.toLong()) { 61 sum += a[cnt] 62 cnt++ 63 } 64 println(cnt) 65 } 66 } 67 ``` 68 69 [1334C - Circle of Monsters](/contest/1334/problem/C "Educational Codeforces Round 85 (Rated for Div. 2)") 70 71 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 72 73 **Tutorial** 74 75 Tutorial is loading... 76 77 **Solution (Ne0n25)** 78 79 ``` 80 #include <bits/stdc++.h> 81 82 using namespace std; 83 84 #define forn(i, n) for (int i = 0; i < int(n); ++i) 85 86 typedef long long li; 87 88 const int N = 300 * 1000 + 13; 89 90 int n; 91 li a[N], b[N]; 92 93 void solve() { 94 scanf("%d", &n); 95 forn(i, n) scanf("%lld%lld", &a[i], &b[i]); 96 97 li ans = 0, mn = 1e18; 98 forn(i, n) { 99 int ni = (i + 1) % n; 100 li val = min(a[ni], b[i]); 101 ans += a[ni] - val; 102 mn = min(mn, val); 103 } 104 ans += mn; 105 printf("%lld\n", ans); 106 } 107 108 int main() { 109 int T; 110 scanf("%d", &T); 111 forn(i, T) 112 solve(); 113 } 114 ``` 115 116 [1334D - Minimum Euler Cycle](/contest/1334/problem/D "Educational Codeforces Round 85 (Rated for Div. 2)") 117 118 Idea: [adedalic](/profile/adedalic "International Master adedalic") 119 120 **Tutorial** 121 122 Tutorial is loading... 123 124 **Solution (adedalic)** 125 126 ``` 127 #include<bits/stdc++.h> 128 129 using namespace std; 130 131 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 132 #define sz(a) int((a).size()) 133 134 #define x first 135 #define y second 136 137 typedef long long li; 138 typedef long double ld; 139 typedef pair<int, int> pt; 140 141 int n; 142 li l, r; 143 144 inline bool read() { 145 if(!(cin >> n >> l >> r)) 146 return false; 147 return true; 148 } 149 150 bool intersect(li l1, li r1, li l2, li r2) { 151 return min(r1, r2) > max(l1, l2); 152 } 153 154 vector<int> ans; 155 156 void calc(int lf, int rg, li &id) { 157 if(lf == rg) return; 158 159 if(intersect(l, r, id, id + 2 * (rg - lf))) { 160 fore(to, lf + 1, rg + 1) { 161 if(l <= id && id < r) 162 ans.push_back(lf); 163 id++; 164 165 if(l <= id && id < r) 166 ans.push_back(to); 167 id++; 168 } 169 } else 170 id += 2 * (rg - lf); 171 172 calc(lf + 1, rg, id); 173 174 if(lf == 0) { 175 if(l <= id && id < r) 176 ans.push_back(lf); 177 id++; 178 } 179 } 180 181 inline void solve() { 182 ans.clear(); 183 li id = 0; 184 l--; 185 calc(0, n - 1, id); 186 187 assert(sz(ans) == r - l); 188 assert(id == n * li(n - 1) + 1); 189 190 for(int v : ans) 191 cout << v + 1 << " "; 192 cout << endl; 193 } 194 195 int main() { 196 #ifdef _DEBUG 197 freopen("input.txt", "r", stdin); 198 int tt = clock(); 199 #endif 200 ios_base::sync_with_stdio(false); 201 cin.tie(0), cout.tie(0); 202 cout << fixed << setprecision(15); 203 204 int tc; cin >> tc; 205 206 while(tc--) { 207 read(); 208 solve(); 209 210 #ifdef _DEBUG 211 cerr << "TIME = " << clock() - tt << endl; 212 tt = clock(); 213 #endif 214 } 215 return 0; 216 } 217 ``` 218 219 [1334E - Divisor Paths](/contest/1334/problem/E "Educational Codeforces Round 85 (Rated for Div. 2)") 220 221 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 222 223 **Tutorial** 224 225 Tutorial is loading... 226 227 **Solution (pikmike)** 228 229 ``` 230 #include <bits/stdc++.h> 231 232 #define forn(i, n) for (int i = 0; i < int(n); i++) 233 234 using namespace std; 235 236 const int MOD = 998244353; 237 238 int add(int a, int b){ 239 a += b; 240 if (a >= MOD) 241 a -= MOD; 242 if (a < 0) 243 a += MOD; 244 return a; 245 } 246 247 int mul(int a, int b){ 248 return a * 1ll * b % MOD; 249 } 250 251 int binpow(int a, int b){ 252 int res = 1; 253 while (b){ 254 if (b & 1) 255 res = mul(res, a); 256 a = mul(a, a); 257 b >>= 1; 258 } 259 return res; 260 } 261 262 int main() { 263 long long d; 264 scanf("%lld", &d); 265 int q; 266 scanf("%d", &q); 267 268 vector<long long> primes; 269 for (long long i = 2; i * i <= d; ++i) if (d % i == 0){ 270 primes.push_back(i); 271 while (d % i == 0) d /= i; 272 } 273 if (d > 1){ 274 primes.push_back(d); 275 } 276 277 vector<int> fact(100), rfact(100); 278 fact[0] = 1; 279 for (int i = 1; i < 100; ++i) 280 fact[i] = mul(fact[i - 1], i); 281 rfact[99] = binpow(fact[99], MOD - 2); 282 for (int i = 98; i >= 0; --i) 283 rfact[i] = mul(rfact[i + 1], i + 1); 284 285 forn(i, q){ 286 long long x, y; 287 scanf("%lld%lld", &x, &y); 288 vector<int> up, dw; 289 for (auto p : primes){ 290 int cnt = 0; 291 while (x % p == 0){ 292 --cnt; 293 x /= p; 294 } 295 while (y % p == 0){ 296 ++cnt; 297 y /= p; 298 } 299 if (cnt < 0) dw.push_back(-cnt); 300 else if (cnt > 0) up.push_back(cnt); 301 } 302 int ans = 1; 303 ans = mul(ans, fact[accumulate(up.begin(), up.end(), 0)]); 304 for (auto it : up) ans = mul(ans, rfact[it]); 305 ans = mul(ans, fact[accumulate(dw.begin(), dw.end(), 0)]); 306 for (auto it : dw) ans = mul(ans, rfact[it]); 307 printf("%d\n", ans); 308 } 309 310 return 0; 311 } 312 ``` 313 314 [1334F - Strange Function](/contest/1334/problem/F "Educational Codeforces Round 85 (Rated for Div. 2)") 315 316 Idea: [Roms](/profile/Roms "Master Roms") и [BledDest](/profile/BledDest "International Grandmaster BledDest") 317 318 **Tutorial** 319 320 Tutorial is loading... 321 322 **Solution (BledDest)** 323 324 ``` 325 #include<bits/stdc++.h> 326 327 using namespace std; 328 329 typedef long long li; 330 const li INF64 = li(1e18); 331 const int N = 500043; 332 333 li f[N]; 334 335 li get(int x) 336 { 337 li ans = 0; 338 for (; x >= 0; x = (x & (x + 1)) - 1) 339 ans += f[x]; 340 return ans; 341 } 342 343 void inc(int x, li d) 344 { 345 for (; x < N; x = (x | (x + 1))) 346 f[x] += d; 347 } 348 349 li get(int l, int r) 350 { 351 return get(r) - get(l - 1); 352 } 353 354 li dp[N]; 355 int a[N], b[N], p[N]; 356 int n, m; 357 358 int main() 359 { 360 scanf("%d", &n); 361 for(int i = 0; i < n; i++) 362 scanf("%d", &a[i]); 363 for(int i = 0; i < n; i++) 364 scanf("%d", &p[i]); 365 scanf("%d", &m); 366 for(int i = 0; i < m; i++) 367 scanf("%d", &b[i]); 368 369 for(int i = 0; i < n; i++) 370 dp[i] = -INF64; 371 map<int, vector<int> > pos; 372 for(int i = 0; i < n; i++) 373 pos[a[i]].push_back(i); 374 set<pair<int, int> > q; 375 for(int i = 0; i < n; i++) 376 q.insert(make_pair(a[i], i)); 377 378 for(auto x : pos[b[0]]) 379 dp[x] = p[x]; 380 while(!q.empty() && q.begin()->first <= b[0]) 381 { 382 int k = q.begin()->second; 383 q.erase(q.begin()); 384 if(p[k] > 0) 385 inc(k, p[k]); 386 } 387 388 for(int i = 1; i < m; i++) 389 { 390 int i1 = b[i - 1], i2 = b[i]; 391 vector<int> both_pos; 392 for(auto x : pos[i1]) 393 both_pos.push_back(x); 394 for(auto x : pos[i2]) 395 both_pos.push_back(x); 396 li best = -INF64; 397 int last = -1; 398 sort(both_pos.begin(), both_pos.end()); 399 for(auto x : both_pos) 400 { 401 best += get(last + 1, x); 402 last = x; 403 if(a[x] == i1) 404 best = max(best, dp[x]); 405 else 406 dp[x] = best + p[x]; 407 } 408 while(!q.empty() && q.begin()->first <= i2) 409 { 410 int k = q.begin()->second; 411 q.erase(q.begin()); 412 if(p[k] > 0) 413 inc(k, p[k]); 414 } 415 } 416 417 li best_dp = -INF64; 418 for(int i = 0; i < n; i++) 419 if(a[i] == b[m - 1]) 420 best_dp = max(best_dp, dp[i] + get(i + 1, n - 1)); 421 li ans = 0; 422 for(int i = 0; i < n; i++) 423 ans += p[i]; 424 ans -= best_dp; 425 if(ans > li(1e15)) 426 puts("NO"); 427 else 428 printf("YES\n%lld\n", ans); 429 430 } 431 ``` 432 433 [1334G - Substring Search](/contest/1334/problem/G "Educational Codeforces Round 85 (Rated for Div. 2)") 434 435 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 436 437 **Tutorial** 438 439 Tutorial is loading... 440 441 **Solution (BledDest)** 442 443 ``` 444 #include<bits/stdc++.h> 445 446 using namespace std; 447 448 #define forn(i, n) for(int i = 0; i < n; i++) 449 #define sz(a) ((int)(a).size()) 450 451 const int LOGN = 20; 452 const int N = (1 << LOGN); 453 454 typedef long double ld; 455 typedef long long li; 456 457 const ld PI = acos(-1.0); 458 459 struct comp 460 { 461 ld x, y; 462 comp(ld x = .0, ld y = .0) : x(x), y(y) {} 463 inline comp conj() { return comp(x, -y); } 464 }; 465 466 inline comp operator +(const comp &a, const comp &b) 467 { 468 return comp(a.x + b.x, a.y + b.y); 469 } 470 471 inline comp operator -(const comp &a, const comp &b) 472 { 473 return comp(a.x - b.x, a.y - b.y); 474 } 475 476 inline comp operator *(const comp &a, const comp &b) 477 { 478 return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x); 479 } 480 481 inline comp operator /(const comp &a, const ld &b) 482 { 483 return comp(a.x / b, a.y / b); 484 } 485 486 vector<comp> w[LOGN]; 487 vector<int> rv[LOGN]; 488 489 void precalc() 490 { 491 for(int st = 0; st < LOGN; st++) 492 { 493 w[st].assign(1 << st, comp()); 494 for(int k = 0; k < (1 << st); k++) 495 { 496 double ang = PI / (1 << st) * k; 497 w[st][k] = comp(cos(ang), sin(ang)); 498 } 499 500 rv[st].assign(1 << st, 0); 501 if(st == 0) 502 { 503 rv[st][0] = 0; 504 continue; 505 } 506 int h = (1 << (st - 1)); 507 for(int k = 0; k < (1 << st); k++) 508 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 509 } 510 } 511 512 inline void fft(comp a[N], int n, int ln, bool inv) 513 { 514 for(int i = 0; i < n; i++) 515 { 516 int ni = rv[ln][i]; 517 if(i < ni) 518 swap(a[i], a[ni]); 519 } 520 521 for(int st = 0; (1 << st) < n; st++) 522 { 523 int len = (1 << st); 524 for(int k = 0; k < n; k += (len << 1)) 525 { 526 for(int pos = k; pos < k + len; pos++) 527 { 528 comp l = a[pos]; 529 comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]); 530 531 a[pos] = l + r; 532 a[pos + len] = l - r; 533 } 534 } 535 } 536 537 if(inv) for(int i = 0; i < n; i++) 538 a[i] = a[i] / n; 539 } 540 541 comp aa[N]; 542 comp bb[N]; 543 comp cc[N]; 544 545 inline void multiply(comp a[N], int sza, comp b[N], int szb, comp c[N], int &szc) 546 { 547 int n = 1, ln = 0; 548 while(n < (sza + szb)) 549 n <<= 1, ln++; 550 for(int i = 0; i < n; i++) 551 aa[i] = (i < sza ? a[i] : comp()); 552 for(int i = 0; i < n; i++) 553 bb[i] = (i < szb ? b[i] : comp()); 554 555 fft(aa, n, ln, false); 556 fft(bb, n, ln, false); 557 558 for(int i = 0; i < n; i++) 559 cc[i] = aa[i] * bb[i]; 560 561 fft(cc, n, ln, true); 562 563 szc = n; 564 for(int i = 0; i < n; i++) 565 c[i] = cc[i]; 566 } 567 568 comp a[N]; 569 comp b[N]; 570 comp c[N]; 571 572 vector<int> p_function(const vector<int>& v) 573 { 574 int n = v.size(); 575 vector<int> p(n); 576 for(int i = 1; i < n; i++) 577 { 578 int j = p[i - 1]; 579 while(j > 0 && v[j] != v[i]) 580 j = p[j - 1]; 581 if(v[j] == v[i]) 582 j++; 583 p[i] = j; 584 } 585 return p; 586 } 587 588 int p[26]; 589 char buf[N]; 590 string s, t; 591 592 int main() 593 { 594 precalc(); 595 for(int i = 0; i < 26; i++) 596 { 597 scanf("%d", &p[i]); 598 p[i]--; 599 } 600 scanf("%s", buf); 601 s = buf; 602 scanf("%s", buf); 603 t = buf; 604 605 int n = s.size(); 606 int m = t.size(); 607 vector<int> color(26, 0); 608 vector<vector<int> > cycles; 609 for(int i = 0; i < 26; i++) 610 { 611 if(color[i]) 612 continue; 613 vector<int> cycle; 614 int cc = cycles.size() + 1; 615 int cur = i; 616 while(color[cur] == 0) 617 { 618 cycle.push_back(cur); 619 color[cur] = cc; 620 cur = p[cur]; 621 } 622 cycles.push_back(cycle); 623 } 624 625 vector<int> ans(m - n + 1); 626 vector<int> s1, t1; 627 for(int i = 0; i < n; i++) 628 s1.push_back(color[int(s[i] - 'a')]); 629 for(int i = 0; i < m; i++) 630 t1.push_back(color[int(t[i] - 'a')]); 631 vector<int> st = s1; 632 st.push_back(0); 633 for(auto x : t1) 634 st.push_back(x); 635 vector<int> pf = p_function(st); 636 for(int i = 0; i < m - n + 1; i++) 637 if(pf[2 * n + i] == n) 638 ans[i] = 1; 639 map<char, comp> m1, m2; 640 for(auto cur : cycles) 641 { 642 int k = cur.size(); 643 for(int i = 0; i < k; i++) 644 { 645 ld ang1 = 2 * PI * i / k; 646 ld ang2 = (PI - 2 * PI * i) / k; 647 m1[char('a' + cur[i])] = comp(cosl(ang1), sinl(ang1)); 648 m2[char('a' + cur[i])] = comp(cosl(ang2), sinl(ang2)); 649 } 650 } 651 652 ld ideal = 0; 653 for(int i = 0; i < n; i++) 654 ideal += (m1[s[i]] * m2[s[i]]).x; 655 reverse(s.begin(), s.end()); 656 for(int i = 0; i < n; i++) 657 a[i] = m1[s[i]]; 658 for(int i = 0; i < m; i++) 659 b[i] = m2[t[i]]; 660 int szc; 661 multiply(a, n, b, m, c, szc); 662 for(int i = 0; i < m - n + 1; i++) 663 if(fabsl(c[i + n - 1].x - ideal) > 0.01) 664 ans[i] = 0; 665 666 667 for(int i = 0; i < m - n + 1; i++) 668 printf("%d", ans[i]); 669 return 0; 670 } 671 ```