1765.md (24335B)
1 Source: https://codeforces.com/blog/entry/109642 2 3 [1765A - Access Levels](/contest/1765/problem/A "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 4 5 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 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 n, m, m2; 21 vector<vector<char>> g; 22 23 int T; 24 vector<int> mt; 25 vector<int> used; 26 27 bool try_kuhn(int v){ 28 if (used[v] == T) 29 return false; 30 used[v] = T; 31 forn(u, m2) if (g[v][u] && (mt[u] == -1 || try_kuhn(mt[u]))){ 32 mt[u] = v; 33 return true; 34 } 35 return false; 36 } 37 38 int main() { 39 cin >> n >> m; 40 vector<string> b(m, string(n, '0')); 41 forn(i, n){ 42 string t; 43 cin >> t; 44 forn(j, m) b[j][i] = t[j]; 45 } 46 47 vector<string> nw = b; 48 sort(nw.begin(), nw.end()); 49 nw.resize(unique(nw.begin(), nw.end()) - nw.begin()); 50 m2 = nw.size(); 51 g.assign(m2, vector<char>(m2, 0)); 52 forn(i, m2) forn(j, m2) if (i != j){ 53 bool in = true; 54 forn(k, n) in &= nw[i][k] >= nw[j][k]; 55 if (in) g[i][j] = 1; 56 } 57 58 mt.assign(m2, -1); 59 used.assign(m2, -1); 60 T = 0; 61 int k = m2; 62 forn(i, m2) if (try_kuhn(i)){ 63 ++T; 64 --k; 65 } 66 67 vector<int> nxt(m2, -1); 68 vector<char> st(m2, true); 69 forn(i, m2) if (mt[i] != -1){ 70 nxt[mt[i]] = i; 71 st[i] = false; 72 } 73 74 vector<int> gr(m2), req(m2); 75 int t = 0; 76 forn(i, m2) if (st[i]){ 77 int v = i; 78 int pos = 2; 79 while (v != -1){ 80 gr[v] = t; 81 req[v] = pos; 82 ++pos; 83 v = nxt[v]; 84 } 85 ++t; 86 } 87 assert(t == k); 88 89 vector<int> num(m); 90 forn(i, m) num[i] = lower_bound(nw.begin(), nw.end(), b[i]) - nw.begin(); 91 92 printf("%d\n", k); 93 forn(i, m) printf("%d ", gr[num[i]] + 1); 94 puts(""); 95 forn(i, m) printf("%d ", req[num[i]]); 96 puts(""); 97 forn(i, n){ 98 vector<int> l(k, 1); 99 forn(j, m2) if (nw[j][i] == '1') 100 l[gr[j]] = max(l[gr[j]], req[j]); 101 forn(j, k) 102 printf("%d ", l[j]); 103 puts(""); 104 } 105 return 0; 106 } 107 ``` 108 109 [1765B - Broken Keyboard](/contest/1765/problem/B "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 110 111 Idea: [vovuh](/profile/vovuh "Мастер vovuh"), preparation: [vovuh](/profile/vovuh "Мастер vovuh") 112 113 **Tutorial** 114 115 Tutorial is loading... 116 117 **Solution (vovuh)** 118 119 ``` 120 for _ in range(int(input())): 121 n = int(input()) 122 s = input() 123 print('YES' if n % 3 != 2 and not False in [s[i * 3 + 1] == s[i * 3 + 2] for i in range(n // 3)] else 'NO') 124 ``` 125 126 [1765C - Card Guessing](/contest/1765/problem/C "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 127 128 Idea: [DStepanenko](/profile/DStepanenko "Эксперт DStepanenko"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 129 130 **Tutorial** 131 132 Tutorial is loading... 133 134 **Solution (awoo)** 135 136 ``` 137 #include <bits/stdc++.h> 138 139 #define forn(i, n) for (int i = 0; i < int(n); i++) 140 #define fore(i, l, r) for (int i = int(l); i < int(r); i++) 141 142 using namespace std; 143 144 const int MOD = 998244353; 145 146 int add(int a, int b){ 147 a += b; 148 if (a >= MOD) 149 a -= MOD; 150 return a; 151 } 152 153 int mul(int a, int b){ 154 return a * 1ll * b % MOD; 155 } 156 157 int binpow(int a, int b){ 158 int res = 1; 159 while (b){ 160 if (b & 1) 161 res = mul(res, a); 162 a = mul(a, a); 163 b >>= 1; 164 } 165 return res; 166 } 167 168 int main() { 169 int n, k; 170 scanf("%d%d", &n, &k); 171 172 vector<int> fact(4 * n + 1); 173 fact[0] = 1; 174 fore(i, 1, fact.size()) fact[i] = mul(fact[i - 1], i); 175 vector<int> rfact(4 * n + 1); 176 rfact.back() = binpow(fact.back(), MOD - 2); 177 for (int i = int(fact.size()) - 2; i >= 0; --i) 178 rfact[i] = mul(rfact[i + 1], i + 1); 179 180 auto cnk = [&](int n, int k){ 181 return mul(fact[n], mul(rfact[k], rfact[n - k])); 182 }; 183 184 vector<vector<int>> sv(n + 1, vector<int>(5)); 185 forn(i, n + 1) forn(t, 5) sv[i][t] = mul(binpow(cnk(n, i), t), rfact[t]); 186 187 vector<vector<vector<int>>> dp(2, vector<vector<int>>(4 * n + 1, vector<int>(5))); 188 forn(ii, n + 1){ 189 int i = ii & 1; 190 int ni = i ^ 1; 191 dp[ni] = vector<vector<int>>(4 * n + 1, vector<int>(5)); 192 for (int t = 1; t <= 4; ++t) 193 dp[ni][ii * t][t] = mul(n - ii, sv[ii][t]); 194 forn(j, k + 1) for (int p = 1; p <= 4; ++p) if (dp[i][j][p]){ 195 dp[ni][j][p] = add(dp[ni][j][p], dp[i][j][p]); 196 for (int t = 1; p + t <= 4; ++t) 197 dp[ni][j + ii * t][p + t] = add(dp[ni][j + ii * t][p + t], mul(dp[i][j][p], sv[ii][t])); 198 } 199 } 200 201 int ans = 0; 202 forn(sum, k + 1){ 203 ans = add(ans, mul(mul(mul( 204 sum < k ? 1 : 4 * n - k, 205 dp[(n & 1) ^ 1][sum][4]), 206 mul(binpow(4 * n - sum, MOD - 2), mul(rfact[4 * n], fact[4 * n - sum]))), 207 mul(fact[4], fact[sum])) 208 ); 209 } 210 211 printf("%d\n", ans); 212 return 0; 213 } 214 ``` 215 216 [1765D - Watch the Videos](/contest/1765/problem/D "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 217 218 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [DmitryKlenov](/profile/DmitryKlenov "Эксперт DmitryKlenov") 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution (DmitryKlenov)** 225 226 ``` 227 #include <iostream> 228 #include <algorithm> 229 using namespace std; 230 231 #define N 200000 232 233 int a[N], n, s; 234 235 bool can(int x) { 236 int l = x - 1, r = n - 1; 237 while (l < r) { 238 if (a[r] > s - a[l]) return false; 239 ++l; 240 if (l < r) { 241 if (a[l] > s - a[r]) return false; 242 --r; 243 } 244 } 245 return true; 246 } 247 248 int main() { 249 long long sum = 0; 250 scanf("%d %d\n", &n, &s); 251 for(int i = 0; i < n; ++i) { 252 scanf("%d", &a[i]); 253 sum += a[i]; 254 } 255 256 sort(a, a + n, greater<int>()); 257 258 int l = 1, r = n; 259 while (l < r) { 260 int m = (l + r) >> 1; 261 if (can(m)) r = m; 262 else l = m + 1; 263 } 264 265 long long ans = sum + r; 266 cout << ans << endl; 267 268 return 0; 269 } 270 ``` 271 272 [1765E - Exchange](/contest/1765/problem/E "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 273 274 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 275 276 **Tutorial** 277 278 Tutorial is loading... 279 280 **Solution (BledDest)** 281 282 ``` 283 #include <bits/stdc++.h> 284 285 using namespace std; 286 287 void solve() 288 { 289 int n, a, b; 290 cin >> n >> a >> b; 291 int x = (n + a - 1) / a; 292 if(a > b) x = 1; 293 cout << x << endl; 294 } 295 296 int main() 297 { 298 int t; 299 cin >> t; 300 for(int i = 0; i < t; i++) 301 solve(); 302 } 303 ``` 304 305 [1765F - Chemistry Lab](/contest/1765/problem/F "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 306 307 Idea: [awoo](/profile/awoo "Гроссмейстер awoo"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo") 308 309 **Tutorial** 310 311 Tutorial is loading... 312 313 **Solution (awoo)** 314 315 ``` 316 #include <bits/stdc++.h> 317 318 #define forn(i, n) for (int i = 0; i < int(n); i++) 319 320 using namespace std; 321 322 typedef long long li; 323 324 const li INF64 = 1e18; 325 326 struct base{ 327 int x, w, c; 328 }; 329 330 li area(const base &a, const base &b){ 331 return (a.c + b.c) * li(abs(a.x - b.x)); 332 } 333 334 int main() { 335 int n, k; 336 scanf("%d%d", &n, &k); 337 vector<base> a(n); 338 forn(i, n) scanf("%d%d%d", &a[i].x, &a[i].w, &a[i].c); 339 sort(a.begin(), a.end(), [](const base &a, const base &b){ return a.x > b.x; }); 340 vector<li> dp(n, -INF64); 341 li ans = 0; 342 forn(i, n){ 343 dp[i] = max(dp[i], -a[i].w * 200ll); 344 for (int j = i + 1; j < n; ++j) 345 dp[j] = max(dp[j], dp[i] + area(a[i], a[j]) * k - a[j].w * 200ll); 346 ans = max(ans, dp[i]); 347 } 348 printf("%.15Lf\n", ans / (long double)(200)); 349 return 0; 350 } 351 ``` 352 353 [1765G - Guess the String](/contest/1765/problem/G "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 354 355 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 356 357 **Tutorial** 358 359 Tutorial is loading... 360 361 **Solution (BledDest)** 362 363 ``` 364 #include <bits/stdc++.h> 365 366 using namespace std; 367 368 mt19937 rnd(42); 369 uniform_int_distribution<int> d(1, 2); 370 371 int ask(int t, int i) 372 { 373 cout << t << " " << i + 1 << endl; 374 int x; 375 cin >> x; 376 return x; 377 } 378 379 void giveAnswer(const string& s) 380 { 381 cout << 0 << " " << s << endl; 382 int x; 383 cin >> x; 384 assert(x == 1); 385 } 386 387 void guessOne(string& s, int i) 388 { 389 int res = ask(1, i); 390 if(res == 0) 391 s[i] = '1'; 392 else 393 s[i] = s[res - 1]; 394 } 395 396 char inv(char c) 397 { 398 if(c == '0') return '1'; 399 return '0'; 400 } 401 402 void guessTwo(string& s, int i) 403 { 404 if(s[1] == '0') 405 { 406 if(d(rnd) == 1) 407 { 408 int res = ask(1, i); 409 if(res >= 2) 410 { 411 s[i] = s[res - 1]; 412 s[i - 1] = s[res - 2]; 413 } 414 else if(res == 1) 415 { 416 s[i] = '0'; 417 s[i - 1] = '1'; 418 } 419 else 420 { 421 s[i] = '1'; 422 guessOne(s, i - 1); 423 } 424 } 425 else 426 { 427 int res = ask(2, i); 428 if(res >= 2) 429 { 430 s[i] = inv(s[res - 1]); 431 s[i - 1] = inv(s[res - 2]); 432 } 433 else if(res == 1) 434 { 435 s[i] = '1'; 436 s[i - 1] = '0'; 437 } 438 else 439 { 440 s[i] = '0'; 441 guessOne(s, i - 1); 442 } 443 } 444 } 445 else 446 { 447 if(d(rnd) == 1) 448 { 449 int res = ask(1, i); 450 if(res >= 2) 451 { 452 s[i] = s[res - 1]; 453 s[i - 1] = s[res - 2]; 454 } 455 else if(res == 1) 456 { 457 s[i] = '0'; 458 guessOne(s, i - 1); 459 } 460 else 461 { 462 s[i] = '1'; 463 s[i - 1] = '1'; 464 } 465 } 466 else 467 { 468 int res = ask(2, i); 469 if(res >= 2) 470 { 471 s[i] = inv(s[res - 1]); 472 s[i - 1] = inv(s[res - 2]); 473 } 474 else if(res == 1) 475 { 476 s[i] = '1'; 477 guessOne(s, i - 1); 478 } 479 else 480 { 481 s[i] = '0'; 482 s[i - 1] = '0'; 483 } 484 } 485 } 486 } 487 488 int main() 489 { 490 int t; 491 cin >> t; 492 for(int i = 0; i < t; i++) 493 { 494 int n; 495 cin >> n; 496 string s(n, '0'); 497 for(int j = 1; j < n; j += 2) 498 { 499 if(j == 1) guessOne(s, j); 500 else guessTwo(s, j); 501 } 502 if(n % 2 == 1) guessOne(s, n - 1); 503 giveAnswer(s); 504 } 505 } 506 ``` 507 508 [1765H - Hospital Queue](/contest/1765/problem/H "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 509 510 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") 511 512 **Tutorial** 513 514 Tutorial is loading... 515 516 **Solution (Neon)** 517 518 ``` 519 #include <bits/stdc++.h> 520 521 using namespace std; 522 523 int main() { 524 ios::sync_with_stdio(false); cin.tie(0); 525 int n, m; 526 cin >> n >> m; 527 vector<int> a(n); 528 for (auto &x : a) cin >> x; 529 vector<vector<int>> g(n); 530 for (int i = 0; i < m; ++i) { 531 int x, y; 532 cin >> x >> y; 533 g[y - 1].push_back(x - 1); 534 } 535 536 vector<int> ans(n, -1); 537 for (int s = 0; s < n; ++s) { 538 vector<int> deg(n); 539 for (int i = 0; i < n; ++i) 540 for (int j : g[i]) ++deg[j]; 541 priority_queue<pair<int, int>> q; 542 for (int v = 0; v < n; ++v) 543 if (deg[v] == 0 && v != s) 544 q.push({a[v], v}); 545 for (int i = n; i > 0; --i) { 546 if (q.empty() || q.top().first < i) { 547 if (deg[s] == 0 && i <= a[s]) 548 ans[s] = i; 549 break; 550 } 551 int v = q.top().second; 552 q.pop(); 553 for (int u : g[v]) { 554 --deg[u]; 555 if (deg[u] == 0 && u != s) 556 q.push({a[u], u}); 557 } 558 } 559 } 560 561 for (int &x : ans) cout << x << ' '; 562 } 563 ``` 564 565 [1765I - Infinite Chess](/contest/1765/problem/I "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 566 567 Idea: [DmitryKlenov](/profile/DmitryKlenov "Эксперт DmitryKlenov"), preparation: [dmitryme](/profile/dmitryme "Не в рейтинге, dmitryme") 568 569 **Tutorial** 570 571 Tutorial is loading... 572 573 **Solution (awoo)** 574 575 ``` 576 #include <bits/stdc++.h> 577 578 #define forn(i, n) for (int i = 0; i < int(n); i++) 579 580 using namespace std; 581 582 const string al = "KQRBN"; 583 584 const int INF = 1e9; 585 586 struct mv{ int dx, dy; }; 587 struct piece{ int x, y, t; }; 588 struct seg{ int l, r; }; 589 struct pos{ int x, y; }; 590 591 bool operator <(const pos &a, const pos &b){ 592 if (a.x != b.x) return a.x < b.x; 593 return a.y < b.y; 594 } 595 596 vector<vector<mv>> mvs({ 597 {{-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}}, 598 {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, -1}, {1, -1}, {1, 1}, {-1, 1}}, 599 {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, 600 {{-1, -1}, {1, -1}, {1, 1}, {-1, 1}}, 601 {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}} 602 }); 603 604 int main() { 605 int sx, sy, fx, fy; 606 cin >> sx >> sy >> fx >> fy; 607 swap(sx, sy), swap(fx, fy); 608 --sx, --fx; 609 610 int k; 611 cin >> k; 612 vector<piece> a(k); 613 forn(i, k){ 614 string t; 615 cin >> t >> a[i].x >> a[i].y; 616 swap(a[i].x, a[i].y); 617 --a[i].x; 618 a[i].t = al.find(t[0]); 619 } 620 621 sort(a.begin(), a.end(), [](const piece &a, const piece &b){ 622 if (a.x != b.x) return a.x < b.x; 623 return a.y < b.y; 624 }); 625 626 vector<int> base({sy, fy}); 627 forn(i, k) base.push_back(a[i].y); 628 vector<int> ys; 629 for (int y : base) for (int i = y - 16; i <= y + 16; ++i) 630 ys.push_back(i); 631 sort(ys.begin(), ys.end()); 632 ys.resize(unique(ys.begin(), ys.end()) - ys.begin()); 633 634 vector<vector<char>> tk(8, vector<char>(ys.size())); 635 forn(i, k){ 636 a[i].y = lower_bound(ys.begin(), ys.end(), a[i].y) - ys.begin(); 637 tk[a[i].x][a[i].y] = true; 638 } 639 sy = lower_bound(ys.begin(), ys.end(), sy) - ys.begin(); 640 fy = lower_bound(ys.begin(), ys.end(), fy) - ys.begin(); 641 642 vector<vector<char>> bad = tk; 643 644 forn(i, k){ 645 int x = a[i].x, y = a[i].y; 646 if (a[i].t == 0 || a[i].t == 4){ 647 for (auto it : mvs[a[i].t]){ 648 int nx = x + it.dx; 649 int ny = y + it.dy; 650 if (0 <= nx && nx < 8) 651 bad[nx][ny] = true; 652 } 653 } 654 else{ 655 for (auto it : mvs[a[i].t]){ 656 for (int nx = x + it.dx, ny = y + it.dy; ; nx += it.dx, ny += it.dy){ 657 if (nx < 0 || nx >= 8) break; 658 if (ny < 0 || ny >= int(ys.size())) break; 659 if (tk[nx][ny]) break; 660 bad[nx][ny] = true; 661 } 662 } 663 } 664 } 665 666 vector<vector<int>> d(8, vector<int>(ys.size(), INF)); 667 vector<vector<pos>> p(8, vector<pos>(ys.size())); 668 set<pair<int, pos>> q; 669 d[sx][sy] = 0; 670 q.insert({0, {sx, sy}}); 671 while (!q.empty()){ 672 int x = q.begin()->second.x; 673 int y = q.begin()->second.y; 674 q.erase(q.begin()); 675 if (x == fx && y == fy){ 676 cout << d[x][y] << endl; 677 return 0; 678 } 679 for (int ny : {y - 1, y, y + 1}){ 680 if (ny < 0 || ny >= int(ys.size())) continue; 681 int dy = max(1, abs(ys[y] - ys[ny])); 682 for (int nx = max(0, x - 1); nx <= min(7, x + 1); ++nx) if (!bad[nx][ny]){ 683 int nd = d[x][y] + dy; 684 if (d[nx][ny] > nd){ 685 q.erase({d[nx][ny], {nx, ny}}); 686 d[nx][ny] = nd; 687 p[nx][ny] = {x, y}; 688 q.insert({d[nx][ny], {nx, ny}}); 689 } 690 } 691 } 692 } 693 694 cout << -1 << endl; 695 return 0; 696 } 697 ``` 698 699 [1765J - Hero to Zero](/contest/1765/problem/J "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 700 701 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest") 702 703 **Tutorial** 704 705 Tutorial is loading... 706 707 **Solution (BledDest)** 708 709 ``` 710 #include<bits/stdc++.h> 711 712 using namespace std; 713 714 int main() 715 { 716 int n; 717 scanf("%d", &n); 718 vector<int> a(n), b(n); 719 for(int i = 0; i < n; i++) scanf("%d", &a[i]); 720 for(int i = 0; i < n; i++) scanf("%d", &b[i]); 721 sort(a.begin(), a.end()); 722 sort(b.begin(), b.end()); 723 long long total = 0; 724 for(int i = 0; i < n; i++) 725 { 726 total += n * 1ll * (a[i] + b[i]); 727 total -= a[i] * 2ll * (b.end() - lower_bound(b.begin(), b.end(), a[i])); 728 total -= b[i] * 2ll * (a.end() - upper_bound(a.begin(), a.end(), b[i])); 729 } 730 for(int i = 0; i < n; i++) 731 total -= (n - 1) * 1ll * abs(a[i] - b[i]); 732 cout << total << endl; 733 } 734 ``` 735 736 [1765K - Torus Path](/contest/1765/problem/K "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 737 738 Idea: [adedalic](/profile/adedalic "Международный мастер adedalic"), preparation: [adedalic](/profile/adedalic "Международный мастер adedalic") 739 740 **Tutorial** 741 742 Tutorial is loading... 743 744 **Solution (adedalic)** 745 746 ``` 747 #include<bits/stdc++.h> 748 749 using namespace std; 750 751 int n; 752 vector< vector<int> > a; 753 754 bool read() { 755 if (!(cin >> n)) 756 return false; 757 a.resize(n, vector<int>(n)); 758 for (int i = 0; i < n; i++) { 759 for (int j = 0; j < n; j++) 760 cin >> a[i][j]; 761 } 762 return true; 763 } 764 765 void solve() { 766 long long sum = 0; 767 for (int i = 0; i < n; i++) 768 sum += accumulate(a[i].begin(), a[i].end(), 0LL); 769 770 int mn = a[0][n - 1]; 771 for (int i = 0; i < n; i++) 772 mn = min(mn, a[i][n - 1 - i]); 773 774 cout << sum - mn << endl; 775 } 776 777 int main() { 778 #ifdef _DEBUG 779 freopen("input.txt", "r", stdin); 780 int tt = clock(); 781 #endif 782 783 if(read()) { 784 solve(); 785 786 #ifdef _DEBUG 787 cerr << "TIME = " << clock() - tt << endl; 788 tt = clock(); 789 #endif 790 } 791 return 0; 792 } 793 ``` 794 795 [1765L - Project Manager](/contest/1765/problem/L "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 796 797 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [awoo](/profile/awoo "Гроссмейстер awoo") 798 799 **Tutorial** 800 801 Tutorial is loading... 802 803 **Solution (awoo)** 804 805 ``` 806 #include <bits/stdc++.h> 807 808 #define forn(i, n) for (int i = 0; i < int(n); i++) 809 810 using namespace std; 811 812 const string days[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"}; 813 814 int main() { 815 cin.tie(0); 816 iostream::sync_with_stdio(false); 817 int n, m, k; 818 cin >> n >> m >> k; 819 vector<vector<char>> ds(n, vector<char>(7)); 820 forn(i, n){ 821 int t; 822 cin >> t; 823 forn(_, t){ 824 string s; 825 cin >> s; 826 ds[i][find(days, days + 7, s) - days] = true; 827 } 828 } 829 vector<int> h(m); 830 forn(i, m) cin >> h[i]; 831 vector<vector<int>> a(k); 832 forn(i, k){ 833 int p; 834 cin >> p; 835 a[i].resize(p); 836 forn(j, p){ 837 cin >> a[i][j]; 838 --a[i][j]; 839 } 840 } 841 int j = 0; 842 vector<int> ans(k, -1), lst(k); 843 int done = 0; 844 vector<map<int, int>> cur(7); 845 vector<set<int>> wk(n); 846 forn(i, k) forn(j, 7) if (ds[a[i][0]][j]) 847 ++cur[j][a[i][0]]; 848 forn(i, k) 849 wk[a[i][0]].insert(i); 850 for (int d = 1;; ++d){ 851 if (j < m && h[j] == d){ 852 ++j; 853 continue; 854 } 855 int wd = (d - 1) % 7; 856 vector<int> now, sv; 857 for (auto it : cur[wd]) now.push_back(it.first); 858 for (int x : now){ 859 forn(i, 7){ 860 auto it = cur[i].find(x); 861 if (it != cur[i].end()){ 862 if (it->second == 1) 863 cur[i].erase(it); 864 else 865 --it->second; 866 } 867 } 868 int y = *wk[x].begin(); 869 sv.push_back(y); 870 wk[x].erase(wk[x].begin()); 871 } 872 forn(i, now.size()){ 873 int y = sv[i]; 874 ++lst[y]; 875 if (lst[y] == int(a[y].size())){ 876 ans[y] = d; 877 ++done; 878 continue; 879 } 880 wk[a[y][lst[y]]].insert(y); 881 forn(j, 7) if (ds[a[y][lst[y]]][j]) 882 ++cur[j][a[y][lst[y]]]; 883 } 884 if (done == k) break; 885 } 886 forn(i, k) cout << ans[i] << " "; 887 cout << endl; 888 } 889 ``` 890 891 [1765M - Minimum LCM](/contest/1765/problem/M "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 892 893 Idea: [BledDest](/profile/BledDest "Международный гроссмейстер BledDest"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") 894 895 **Tutorial** 896 897 Tutorial is loading... 898 899 **Solution (Neon)** 900 901 ``` 902 #include <bits/stdc++.h> 903 904 using namespace std; 905 906 int main() { 907 int t; 908 cin >> t; 909 while (t--) { 910 int n; 911 cin >> n; 912 int a = 1; 913 for (int g = 2; g * g <= n; ++g) { 914 if (n % g == 0) { 915 a = n / g; 916 break; 917 } 918 } 919 cout << a << ' ' << n - a << '\n'; 920 } 921 } 922 ``` 923 924 [1765N - Number Reduction](/contest/1765/problem/N "2022-2023 ICPC, NERC, Южный четвертьфинал (онлайн-трансляция, правила ICPC, командное соревнование)") 925 926 Idea: [Neon](/profile/Neon "Кандидат в мастера Neon"), preparation: [Neon](/profile/Neon "Кандидат в мастера Neon") 927 928 **Tutorial** 929 930 Tutorial is loading... 931 932 **Solution (Neon)** 933 934 ``` 935 #include <bits/stdc++.h> 936 937 using namespace std; 938 939 int main() { 940 ios::sync_with_stdio(false); 941 cin.tie(0); 942 943 int t; 944 cin >> t; 945 while (t--) { 946 string x; 947 cin >> x; 948 int k; 949 cin >> k; 950 int n = x.size(); 951 vector<vector<int>> pos(10); 952 for (int i = 0; i < n; ++i) 953 pos[x[i] - '0'].push_back(i); 954 for (int i = 0; i < 10; ++i) 955 reverse(pos[i].begin(), pos[i].end()); 956 string ans; 957 int lst = 0, len = n - k; 958 for (int i = 0; i < len; ++i) { 959 for (int d = (i == 0); d <= 9; ++d) { 960 while (!pos[d].empty() && pos[d].back() < lst) 961 pos[d].pop_back(); 962 if (!pos[d].empty() && pos[d].back() - lst <= k) { 963 ans += d + '0'; 964 k -= pos[d].back() - lst; 965 lst = pos[d].back() + 1; 966 break; 967 } 968 } 969 } 970 cout << ans << '\n'; 971 } 972 } 973 ```