1792.md (11833B)
1 Source: https://codeforces.com/blog/entry/111835 2 3 [1792A - GamingForces](/contest/1792/problem/A "Educational Codeforces Round 142 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (Neon)** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while (t--) { 22 int n; 23 cin >> n; 24 int cnt1 = 0; 25 for (int i = 0; i < n; ++i) { 26 int x; 27 cin >> x; 28 cnt1 += (x == 1); 29 } 30 cout << n - cnt1 / 2 << '\n'; 31 } 32 } 33 ``` 34 35 [1792B - Stand-up Comedian](/contest/1792/problem/B "Educational Codeforces Round 142 (Rated for Div. 2)") 36 37 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 38 39 **Tutorial** 40 41 Tutorial is loading... 42 43 **Solution (awoo)** 44 45 ``` 46 for _ in range(int(input())): 47 a1, a2, a3, a4 = map(int, input().split()) 48 if a1 == 0: 49 print(1) 50 else: 51 print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4)) 52 ``` 53 54 [1792C - Min Max Sort](/contest/1792/problem/C "Educational Codeforces Round 142 (Rated for Div. 2)") 55 56 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 57 58 **Tutorial** 59 60 Tutorial is loading... 61 62 **Solution (Neon)** 63 64 ``` 65 #include <bits/stdc++.h> 66 67 using namespace std; 68 69 int main() { 70 int t; 71 cin >> t; 72 while (t--) { 73 int n; 74 cin >> n; 75 vector<int> pos(n + 1); 76 for (int i = 0; i < n; ++i) { 77 int x; 78 cin >> x; 79 pos[x] = i; 80 } 81 int l = (n + 1) / 2, r = (n + 2) / 2; 82 while (l > 0 && (l == r || (pos[l] < pos[l + 1] && pos[r - 1] < pos[r]))) { 83 --l; 84 ++r; 85 } 86 cout << (n - r + l + 1) / 2 << '\n'; 87 } 88 } 89 ``` 90 91 [1792D - Fixed Prefix Permutations](/contest/1792/problem/D "Educational Codeforces Round 142 (Rated for Div. 2)") 92 93 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 94 95 **Tutorial** 96 97 Tutorial is loading... 98 99 **Solution (awoo)** 100 101 ``` 102 #include <bits/stdc++.h> 103 104 using namespace std; 105 106 #define forn(i, n) for(int i = 0; i < int(n); i++) 107 108 int get(const vector<int> &a, const vector<int> &b){ 109 int res = 0; 110 while (res < int(a.size()) && a[res] == b[res]) 111 ++res; 112 return res; 113 } 114 115 int main(){ 116 int t; 117 scanf("%d", &t); 118 while (t--){ 119 int n, m; 120 scanf("%d%d", &n, &m); 121 vector<vector<int>> a(n, vector<int>(m)); 122 forn(i, n) forn(j, m){ 123 scanf("%d", &a[i][j]); 124 --a[i][j]; 125 } 126 vector<vector<int>> b(n, vector<int>(m)); 127 forn(i, n) forn(j, m) b[i][a[i][j]] = j; 128 sort(b.begin(), b.end()); 129 forn(i, n){ 130 int j = lower_bound(b.begin(), b.end(), a[i]) - b.begin(); 131 int ans = 0; 132 if (j > 0) ans = max(ans, get(a[i], b[j - 1])); 133 if (j < n) ans = max(ans, get(a[i], b[j])); 134 printf("%d ", ans); 135 } 136 puts(""); 137 } 138 } 139 ``` 140 141 [1792E - Divisors and Table](/contest/1792/problem/E "Educational Codeforces Round 142 (Rated for Div. 2)") 142 143 Idea: [adedalic](/profile/adedalic "International Master adedalic") 144 145 **Tutorial** 146 147 Tutorial is loading... 148 149 **Solution (adedalic)** 150 151 ``` 152 #include<bits/stdc++.h> 153 154 using namespace std; 155 156 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 157 #define sz(a) int((a).size()) 158 159 #define x first 160 #define y second 161 162 typedef long long li; 163 typedef long double ld; 164 typedef pair<int, int> pt; 165 166 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 167 return out << "(" << p.x << ", " << p.y << ")"; 168 } 169 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 170 fore(i, 0, sz(v)) { 171 if(i) out << " "; 172 out << v[i]; 173 } 174 return out; 175 } 176 177 const int INF = int(1e9); 178 const li INF64 = li(1e18); 179 const ld EPS = 1e-9; 180 181 int n; 182 li m1, m2; 183 184 inline bool read() { 185 if(!(cin >> n >> m1 >> m2)) 186 return false; 187 return true; 188 } 189 190 vector<pt> mFact; 191 vector<li> divs; 192 193 void factM(li m1, li m2) { 194 mFact.clear(); 195 196 for (int d = 2; d * d <= m1 || d * d <= m2; d++) { 197 int cnt = 0; 198 while (m1 % d == 0) { 199 m1 /= d; 200 cnt++; 201 } 202 while (m2 % d == 0) { 203 m2 /= d; 204 cnt++; 205 } 206 if (cnt > 0) 207 mFact.push_back({d, cnt}); 208 } 209 if (m1 > m2) 210 swap(m1, m2); 211 if (m1 > 1) 212 mFact.push_back({m1, 1}); 213 if (m2 > 1) { 214 if (m2 == m1) 215 mFact.back().y++; 216 else 217 mFact.push_back({m2, 1}); 218 } 219 } 220 221 void genDivisors(int pos, li val) { 222 if (pos >= sz(mFact)) { 223 divs.push_back(val); 224 return; 225 } 226 li cur = val; 227 fore (pw, 0, mFact[pos].y + 1) { 228 genDivisors(pos + 1, cur); 229 if (pw < mFact[pos].y) 230 cur *= mFact[pos].x; 231 } 232 } 233 234 inline void solve() { 235 factM(m1, m2); 236 237 divs.clear(); 238 genDivisors(0, 1); 239 sort(divs.begin(), divs.end()); 240 241 vector<int> ans(sz(divs), 0); 242 243 vector<li> dp(sz(divs), -1); 244 fore (id, 0, sz(divs)) { 245 if (divs[id] <= n) 246 dp[id] = divs[id]; 247 for (auto [p, pw] : mFact) { 248 if (divs[id] % p != 0) 249 continue; 250 251 int pos = int(lower_bound(divs.begin(), divs.end(), divs[id] / p) - divs.begin()); 252 dp[id] = max(dp[id], dp[pos]); 253 } 254 255 if (divs[id] / dp[id] <= n) 256 ans[id] = divs[id] / dp[id]; 257 } 258 259 int cnt = 0; 260 int xorSum = 0; 261 fore (i, 0, sz(ans)) { 262 cnt += ans[i] > 0; 263 xorSum ^= ans[i]; 264 } 265 266 // cout << sz(ans) << endl; 267 // cout << ans << endl; 268 cout << cnt << " " << xorSum << endl; 269 } 270 271 int main() { 272 #ifdef _DEBUG 273 freopen("input.txt", "r", stdin); 274 int tt = clock(); 275 #endif 276 ios_base::sync_with_stdio(false); 277 cin.tie(0), cout.tie(0); 278 cout << fixed << setprecision(15); 279 280 int t; cin >> t; 281 282 while (t--) { 283 284 read(); 285 solve(); 286 287 #ifdef _DEBUG 288 cerr << "TIME = " << clock() - tt << endl; 289 tt = clock(); 290 #endif 291 } 292 return 0; 293 } 294 ``` 295 296 [1792F1 - Graph Coloring (easy version)](/contest/1792/problem/F1 "Educational Codeforces Round 142 (Rated for Div. 2)") 297 298 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 299 300 **Tutorial** 301 302 Tutorial is loading... 303 304 **Solution (BledDest)** 305 306 ``` 307 #include<bits/stdc++.h> 308 309 using namespace std; 310 311 const int MOD = 998244353; 312 313 int add(int x, int y) 314 { 315 x += y; 316 while(x >= MOD) x -= MOD; 317 while(x < 0) x += MOD; 318 return x; 319 } 320 321 int mul(int x, int y) 322 { 323 return (x * 1ll * y) % MOD; 324 } 325 326 int varMul(int x) 327 { 328 return x; 329 } 330 331 template<typename... Args> 332 int varMul(int x, Args... args) 333 { 334 return mul(x, varMul(args...)); 335 } 336 337 int binpow(int x, int y) 338 { 339 int z = 1; 340 while(y) 341 { 342 if(y & 1) z = mul(z, x); 343 x = mul(x, x); 344 y /= 2; 345 } 346 return z; 347 } 348 349 vector<int> fact, rfact; 350 vector<int> dp; 351 int n; 352 353 void precalc() 354 { 355 fact.resize(n + 1); 356 rfact.resize(n + 1); 357 fact[0] = 1; 358 for(int i = 1; i <= n; i++) 359 fact[i] = mul(i, fact[i - 1]); 360 for(int i = 0; i <= n; i++) 361 rfact[i] = binpow(fact[i], MOD - 2); 362 dp.resize(n + 1, -1); 363 } 364 365 int C(int n, int k) 366 { 367 if(n < 0 || n < k || k < 0) return 0; 368 return varMul(fact[n], rfact[k], rfact[n - k]); 369 } 370 371 int calc(int x) 372 { 373 if(dp[x] != -1) return dp[x]; 374 if(x == 1) return dp[x] = 1; 375 if(x == 2) return dp[x] = 1; 376 dp[x] = 0; 377 int& d = dp[x]; 378 for(int i = 1; i < x; i++) 379 { 380 d = add(d, varMul(calc(i), (i == x - 1 ? (MOD + 1) / 2 : calc(x - i)), 2, C(x - 1, i - 1))); 381 } 382 return d; 383 } 384 385 int main() 386 { 387 cin >> n; 388 precalc(); 389 cout << add(mul(calc(n), 2), -2) << endl; 390 } 391 ``` 392 393 [1792F2 - Graph Coloring (hard version)](/contest/1792/problem/F2 "Educational Codeforces Round 142 (Rated for Div. 2)") 394 395 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 396 397 **Tutorial** 398 399 Tutorial is loading... 400 401 **Solution (BledDest)** 402 403 ``` 404 #include<bits/stdc++.h> 405 406 using namespace std; 407 408 const int LOGN = 18; 409 const int N = (1 << LOGN); 410 const int MOD = 998244353; 411 const int g = 3; 412 413 #define forn(i, n) for(int i = 0; i < int(n); i++) 414 415 inline int mul(int a, int b) 416 { 417 return (a * 1ll * b) % MOD; 418 } 419 420 inline int norm(int a) 421 { 422 while(a >= MOD) 423 a -= MOD; 424 while(a < 0) 425 a += MOD; 426 return a; 427 } 428 429 inline int binPow(int a, int k) 430 { 431 int ans = 1; 432 while(k > 0) 433 { 434 if(k & 1) 435 ans = mul(ans, a); 436 a = mul(a, a); 437 k >>= 1; 438 } 439 return ans; 440 } 441 442 inline int inv(int a) 443 { 444 return binPow(a, MOD - 2); 445 } 446 447 vector<int> w[LOGN]; 448 vector<int> iw[LOGN]; 449 vector<int> rv[LOGN]; 450 451 void precalc() 452 { 453 int wb = binPow(g, (MOD - 1) / (1 << LOGN)); 454 455 for(int st = 0; st < LOGN; st++) 456 { 457 w[st].assign(1 << st, 1); 458 iw[st].assign(1 << st, 1); 459 460 int bw = binPow(wb, 1 << (LOGN - st - 1)); 461 int ibw = inv(bw); 462 463 int cw = 1; 464 int icw = 1; 465 466 for(int k = 0; k < (1 << st); k++) 467 { 468 w[st][k] = cw; 469 iw[st][k] = icw; 470 471 cw = mul(cw, bw); 472 icw = mul(icw, ibw); 473 } 474 475 rv[st].assign(1 << st, 0); 476 477 if(st == 0) 478 { 479 rv[st][0] = 0; 480 continue; 481 } 482 int h = (1 << (st - 1)); 483 for(int k = 0; k < (1 << st); k++) 484 rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h); 485 } 486 } 487 488 inline void fft(int a[N], int n, int ln, bool inverse) 489 { 490 for(int i = 0; i < n; i++) 491 { 492 int ni = rv[ln][i]; 493 if(i < ni) 494 swap(a[i], a[ni]); 495 } 496 497 for(int st = 0; (1 << st) < n; st++) 498 { 499 int len = (1 << st); 500 for(int k = 0; k < n; k += (len << 1)) 501 { 502 for(int pos = k; pos < k + len; pos++) 503 { 504 int l = a[pos]; 505 int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k])); 506 507 a[pos] = norm(l + r); 508 a[pos + len] = norm(l - r); 509 } 510 } 511 } 512 513 if(inverse) 514 { 515 int in = inv(n); 516 for(int i = 0; i < n; i++) 517 a[i] = mul(a[i], in); 518 } 519 } 520 521 int aa[N], bb[N], cc[N]; 522 523 vector<int> multiply(vector<int> a, vector<int> b) 524 { 525 int sza = a.size(); 526 int szb = b.size(); 527 int n = 1, ln = 0; 528 while(n < (sza + szb)) 529 n <<= 1, ln++; 530 for(int i = 0; i < n; i++) 531 aa[i] = (i < sza ? a[i] : 0); 532 for(int i = 0; i < n; i++) 533 bb[i] = (i < szb ? b[i] : 0); 534 535 fft(aa, n, ln, false); 536 fft(bb, n, ln, false); 537 538 for(int i = 0; i < n; i++) 539 cc[i] = mul(aa[i], bb[i]); 540 541 fft(cc, n, ln, true); 542 543 int szc = n; 544 vector<int> c(szc); 545 szc = n; 546 for(int i = 0; i < n; i++) 547 c[i] = cc[i]; 548 return c; 549 } 550 551 int main() 552 { 553 int n; 554 cin >> n; 555 vector<int> fact(n + 1); 556 fact[0] = 1; 557 for(int i = 0; i < n; i++) 558 fact[i + 1] = mul(fact[i], i + 1); 559 precalc(); 560 vector<int> A = {0, 1, 2}; 561 vector<int> B = {0, 1, 1}; 562 vector<int> C = {0, 1, 1}; 563 vector<int> D = {0, 1, 1}; 564 vector<int> conv; 565 const int K = 2000; 566 int last_conv = -1e9; 567 while(A.size() <= n) 568 { 569 int cur = A.size(); 570 if(cur - last_conv >= K) 571 { 572 last_conv = cur - 1; 573 conv = multiply(C, D); 574 } 575 /*for(auto x : conv) cerr << x << " "; 576 cerr << endl;*/ 577 int val_A; 578 if(last_conv * 2 >= cur) 579 { 580 val_A = conv[cur]; 581 // [cur - last_conv, last_conv] are already used 582 for(int i = 1; i < (cur - last_conv); i++) 583 { 584 val_A = norm(val_A + mul(C[i], D[cur - i])); 585 } 586 for(int i = last_conv + 1; i < cur; i++) 587 { 588 val_A = norm(val_A + mul(C[i], D[cur - i])); 589 } 590 } 591 else 592 { 593 val_A = 0; 594 for(int i = 1; i <= cur - 1; i++) 595 { 596 val_A = norm(val_A + mul(C[i], D[cur - i])); 597 } 598 } 599 val_A = mul(val_A, fact[cur - 1]); 600 val_A = mul(val_A, 2); 601 A.push_back(val_A); 602 B.push_back(mul(val_A, inv(2))); 603 C.push_back(mul(val_A, inv(fact[cur]))); 604 D.push_back(mul(B.back(), inv(fact[cur - 1]))); 605 } 606 cout << norm(A[n] - 2) << endl; 607 } 608 ```