1384.md (15568B)
1 Source: https://codeforces.com/blog/entry/80562 2 3 We (the setters) hope you liked the problems. Here is the editorial: 4 5 Tutorial is loading... 6 7 **C++ solution** 8 9 ``` 10 #include <iostream> 11 12 #define endl '\n' 13 14 using namespace std; 15 16 void solve() 17 { 18 int n; 19 cin >> n; 20 21 string s(200, 'a'); 22 cout << s << endl; 23 24 for (int i = 0; i < n; ++i) 25 { 26 int u; 27 cin >> u; 28 s[u] = s[u] == 'a' ? 'b' : 'a'; 29 cout << s << endl; 30 } 31 } 32 33 int main() 34 { 35 int t; 36 cin >> t; 37 38 for (int i = 0; i < t; ++i) 39 { 40 solve(); 41 } 42 43 return 0; 44 } 45 ``` 46 47 **Python solution** 48 49 ``` 50 import sys 51 input = sys.stdin.readline 52 53 def main(): 54 t = int(input()) 55 56 for _ in range(t): 57 n = int(input()) 58 a = list(map(int, input().split())) 59 60 mx = max(a) 61 ans = [ 'a' * (mx + 1) ] * (n + 1) 62 63 for i, x in enumerate(a): 64 who = 'a' if ans[i][x] == 'b' else 'b' 65 ans[i + 1] = ans[i][:x] + who + ans[i][x + 1:] 66 67 print('\n'.join(ans)) 68 69 main() 70 ``` 71 72 Problem idea: [dcordb](/profile/dcordb "Expert dcordb") 73 74 Solution idea: [dcordb](/profile/dcordb "Expert dcordb") and [Devil](/profile/Devil "Master Devil") 75 76 Tutorial is loading... 77 78 **C++ solution** 79 80 ``` 81 #include <bits/stdc++.h> 82 83 using namespace std; 84 85 int main() 86 { 87 ios_base::sync_with_stdio(0), cin.tie(0); 88 89 int test; 90 cin >> test; 91 while (test--) 92 { 93 int n, k, l; 94 cin >> n >> k >> l; 95 vector<int> d(n+2, -k); 96 for (int i = 1; i <= n; ++i) 97 cin >> d[i]; 98 99 set<tuple<int, int, bool>> mark; 100 function<bool(int, int, bool)> go = [&](int pos, int tide, bool down) 101 { 102 if (pos > n) return true; 103 104 if (mark.find({ pos, tide, down }) != mark.end()) 105 return false; 106 107 mark.insert({ pos, tide, down }); 108 109 tide += down ? -1 : +1; 110 if (tide == 0) down = false; 111 if (tide == k) down = true; 112 113 if (d[pos] + tide <= l && go(pos, tide, down)) 114 return true; 115 if (d[pos + 1] + tide <= l && go(pos + 1, tide, down)) 116 return true; 117 return false; 118 }; 119 120 if (go(0, 0, false)) cout << "Yes\n"; 121 else cout << "No\n"; 122 } 123 124 return 0; 125 } 126 ``` 127 128 Problem idea: [Devil](/profile/Devil "Master Devil") 129 130 Solution idea: [Devil](/profile/Devil "Master Devil") 131 132 Tutorial is loading... 133 134 **C++ solution** 135 136 ``` 137 #include <bits/stdc++.h> 138 139 using namespace std; 140 141 int main() 142 { 143 ios_base::sync_with_stdio(0), cin.tie(0); 144 145 int test; 146 cin >> test; 147 while (test--) 148 { 149 int n, k, l; 150 cin >> n >> k >> l; 151 vector<int> d(n+1), safe = { 0 }; 152 for (int i = 1; i <= n; ++i) 153 { 154 cin >> d[i]; 155 if (d[i] + k <= l) 156 safe.push_back(i); 157 } 158 159 safe.push_back(n+1); 160 bool ok = true; 161 for (size_t i = 1; i < safe.size() && ok; ++i) 162 { 163 int tide = k; bool down = true; 164 for (int j = safe[i-1] + 1; j < safe[i]; ++j) 165 { 166 tide += down ? -1 : +1; 167 168 if (down) tide -= max(0, d[j] + tide - l); 169 if (tide < 0 || d[j] + tide > l) { ok = false; break; } 170 171 if (tide == 0) down = false; 172 } 173 } 174 175 if (ok) cout << "Yes\n"; 176 else cout << "No\n"; 177 } 178 179 return 0; 180 } 181 ``` 182 183 Problem idea: [Devil](/profile/Devil "Master Devil") 184 185 Solution idea: [Devil](/profile/Devil "Master Devil") 186 187 Tutorial is loading... 188 189 **C++ solution** 190 191 ``` 192 #include <bits/stdc++.h> 193 194 using namespace std; 195 196 const int Alp = 20; 197 198 int main() 199 { 200 ios_base::sync_with_stdio(0), cin.tie(0); 201 202 int test; 203 cin >> test; 204 while (test--) 205 { 206 int n; 207 string a, b; 208 cin >> n >> a >> b; 209 210 bool bad = false; 211 vector<vector<int>> adj(Alp); 212 for (int i = 0; i < n; ++i) 213 if (a[i] != b[i]) 214 { 215 if (a[i] > b[i]) 216 { 217 bad = true; 218 cout << "-1\n"; 219 break; 220 } 221 222 adj[a[i]-'a'].push_back(b[i]-'a'); 223 adj[b[i]-'a'].push_back(a[i]-'a'); 224 } 225 226 if (bad) continue; 227 228 vector<bool> mark(Alp); 229 function<void(int)> dfs = [&](int u) 230 { 231 mark[u] = true; 232 for (auto v : adj[u]) 233 if (!mark[v]) 234 dfs(v); 235 }; 236 237 int ans = Alp; 238 for (int i = 0; i < Alp; ++i) 239 if (!mark[i]) 240 dfs(i), --ans; 241 cout << ans << "\n"; 242 } 243 244 return 0; 245 } 246 ``` 247 248 Problem idea: [Devil](/profile/Devil "Master Devil") 249 250 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") and [Devil](/profile/Devil "Master Devil") 251 252 Tutorial is loading... 253 254 **C++ solution** 255 256 ``` 257 #include <bits/stdc++.h> 258 259 using namespace std; 260 261 int main() 262 { 263 ios_base::sync_with_stdio(0), cin.tie(0); 264 265 int test; 266 cin >> test; 267 while (test--) 268 { 269 int n; 270 cin >> n; 271 272 int x = 0; 273 vector<int> a(n); 274 for (auto &i : a) 275 { 276 cin >> i; 277 x ^= i; 278 } 279 280 if (x == 0) 281 { 282 cout << "DRAW\n"; 283 continue; 284 } 285 286 for (int k = 30; k >= 0; --k) 287 if (x >> k & 1) 288 { 289 vector<int> f(2); 290 for (auto &i : a) ++f[i >> k & 1]; 291 if (f[1] % 4 == 3 && f[0] % 2 == 0) 292 cout << "LOSE\n"; 293 else 294 cout << "WIN\n"; 295 break; 296 } 297 } 298 299 return 0; 300 } 301 ``` 302 303 **Python solution** 304 305 ``` 306 import sys 307 input = sys.stdin.readline 308 309 d = { 1: 'WIN', 0: 'LOSE', -1: 'DRAW' } 310 311 def main(): 312 t = int(input()) 313 314 for _ in range(t): 315 n = int(input()) 316 a = map(int, input().split()) 317 318 f = [0] * 30 319 320 for x in a: 321 for b in range(30): 322 if x >> b & 1: 323 f[b] += 1 324 325 ans = -1 326 for x in reversed(range(30)): 327 if f[x] % 2 == 1: 328 ans = 0 if f[x] % 4 == 3 and (n - f[x]) % 2 == 0 else 1 329 break 330 331 print(d[ans]) 332 333 main() 334 ``` 335 336 Problem idea: [Devil](/profile/Devil "Master Devil") 337 338 Solution idea: [Devil](/profile/Devil "Master Devil") and [dcordb](/profile/dcordb "Expert dcordb") 339 340 Tutorial is loading... 341 342 **C++ solution** 343 344 ``` 345 #include <bits/stdc++.h> 346 347 using namespace std; 348 349 const int Alp = 20; 350 351 int main() 352 { 353 ios_base::sync_with_stdio(0), cin.tie(0); 354 355 int test; 356 cin >> test; 357 while (test--) 358 { 359 int len; 360 string a, b; 361 cin >> len >> a >> b; 362 363 vector<int> adj(Alp); 364 vector<vector<int>> G(Alp); 365 for (int i = 0; i < len; ++i) 366 if (a[i] != b[i]) 367 { 368 adj[a[i]-'a'] |= 1 << (b[i]-'a'); 369 G[a[i]-'a'].push_back(b[i]-'a'); 370 G[b[i]-'a'].push_back(a[i]-'a'); 371 } 372 373 vector<bool> mark(Alp); 374 function<void(int)> dfs = [&](int u) 375 { 376 mark[u] = true; 377 for (auto v : G[u]) 378 if (!mark[v]) 379 dfs(v); 380 }; 381 382 int comp = 0; 383 for (int i = 0; i < Alp; ++i) 384 if (!mark[i]) 385 dfs(i), ++comp; 386 387 int ans = 0; 388 vector<bool> dp(1<<Alp); 389 dp[0] = true; 390 for (int mask = 0; mask < 1<<Alp; ++mask) 391 if (dp[mask]) 392 { 393 ans = max(ans, __builtin_popcount(mask)); 394 for (int u = 0; u < Alp; ++u) 395 if ((~mask >> u & 1) && (adj[u] & mask) == 0) 396 dp[mask | 1 << u] = true; 397 } 398 399 cout << 2*Alp - comp - ans << "\n"; 400 } 401 402 return 0; 403 } 404 ``` 405 406 Problem idea: [Devil](/profile/Devil "Master Devil") 407 408 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") 409 410 Tutorial is loading... 411 412 **C++ solution** 413 414 ``` 415 #include <bits/stdc++.h> 416 417 #define endl '\n' 418 419 using namespace std; 420 421 int main() 422 { 423 ios_base::sync_with_stdio(0); 424 cin.tie(0); 425 426 int n, m; 427 cin >> n >> m; 428 429 vector<vector<int>> mat(n, vector<int>(m)); 430 431 for (int i = 0; i < n; ++i) 432 for (int j = 0; j < m; ++j) 433 cin >> mat[i][j]; 434 435 vector<int> h(n * m + 1); 436 vector<int> v(n * m + 1); 437 438 for (int i = 0; i < n; ++i) 439 { 440 int a = 0; 441 for (int j = 0; j < m; ++j) 442 a = max(a, mat[i][j]); 443 h[a] = 1; 444 } 445 446 for (int i = 0; i < m; ++i) 447 { 448 int a = 0; 449 for (int j = 0; j < n; ++j) 450 a = max(a, mat[j][i]); 451 v[a] = 1; 452 } 453 454 vector<vector<int>> fin(n, vector<int>(m)); 455 queue<pair<int, int>> q; 456 457 int x = -1, y = -1; 458 459 for (int u = n * m; u >= 1; --u) 460 { 461 x += h[u]; 462 y += v[u]; 463 464 if (h[u] || v[u]) 465 { 466 fin[x][y] = u; 467 } 468 else 469 { 470 int qx, qy; 471 tie(qx, qy) = q.front(); 472 q.pop(); 473 fin[qx][qy] = u; 474 } 475 476 if (h[u]) 477 for (int i = y - 1; i >= 0; --i) 478 q.push({x, i}); 479 480 if (v[u]) 481 for (int i = x - 1; i >= 0; --i) 482 q.push({i, y}); 483 } 484 485 for (int i = 0; i < n; ++i) 486 for (int j = 0; j < m; ++j) 487 cout << fin[i][j] << " \n"[j + 1 == m]; 488 489 return 0; 490 } 491 ``` 492 493 Problem idea: [gilcu3](/profile/gilcu3 "Master gilcu3") 494 495 Solution idea: [gilcu3](/profile/gilcu3 "Master gilcu3") and [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") 496 497 Tutorial is loading... 498 499 **C++ solution** 500 501 ``` 502 #include <bits/stdc++.h> 503 504 using namespace std; 505 506 const int mod = 1000000007; 507 508 int main() 509 { 510 ios::sync_with_stdio(false), cin.tie(0); 511 512 string s; cin >> s; 513 int n = s.length(); 514 vector<int> dist(n); 515 for (int i = 0; i < n; ++i) 516 if (s[i] == '0') dist[i] = (i ? dist[i-1] : 0) + 1; 517 518 vector<int> dp(n + 2), nxt(n+2, n); 519 auto get = [&](int i) { return nxt[i] < n ? dp[nxt[i]] : 0; }; 520 521 for (int i = n-1; i >= 0; --i) 522 { 523 dp[i] = ((dist[i] <= dist.back()) + get(0) + get(dist[i] + 1)) % mod; 524 nxt[dist[i]] = i; 525 } 526 527 int ans = n; 528 if (nxt[0] < n) 529 ans = ((long long)get(0) * (nxt[0] + 1)) % mod; 530 cout << ans << "\n"; 531 532 return 0; 533 } 534 ``` 535 536 Problem idea: [Devil](/profile/Devil "Master Devil") 537 538 Solution idea: [Devil](/profile/Devil "Master Devil") and [antontrygubO_o](/profile/antontrygubO_o "Grandmaster antontrygubO_o") 539 540 Tutorial is loading... 541 542 **C++ solution** 543 544 ``` 545 #include <bits/stdc++.h> 546 547 using namespace std; 548 549 template<typename C, typename R = C> 550 struct dinic 551 { 552 typedef C flow_type; 553 typedef R result_type; 554 555 static_assert(std::is_arithmetic<flow_type>::value, "flow_type must be arithmetic"); 556 static_assert(std::is_arithmetic<result_type>::value, "result_type must be arithmetic"); 557 558 static const flow_type oo = std::numeric_limits<flow_type>::max(); 559 560 struct edge 561 { 562 //int src; // not needed, can be deleted to save memory 563 int dst; 564 int rev; 565 flow_type cap, flowp; 566 567 edge(int src, int dst, int rev, flow_type cap, int flowp) : 568 /*src(src),*/ dst(dst), rev(rev), cap(cap), flowp(flowp) {} 569 }; 570 571 dinic(int n) : adj(n), que(n), level(n), edge_pos(n), flow_id(0) {} 572 573 int add_edge(int src, int dst, flow_type cap, flow_type rcap = 0) 574 { 575 adj[src].emplace_back(src, dst, (int) adj[dst].size(), cap, flow_id++); 576 if (src == dst) adj[src].back().rev++; 577 adj[dst].emplace_back(dst, src, (int) adj[src].size() - 1, rcap, flow_id++); 578 return (int) adj[src].size() - 1 - (src == dst); 579 } 580 581 inline bool side_of_S(int u) { return level[u] == -1; } 582 583 result_type max_flow(int source, int sink, vector<flow_type> &flow_e) 584 { 585 result_type flow = 0; 586 while (true) 587 { 588 int front = 0, back = 0; 589 std::fill(level.begin(), level.end(), -1); 590 for (level[que[back++] = sink] = 0; front < back && level[source] == -1; ++front) 591 { 592 int u = que[front]; 593 for (const edge &e : adj[u]) 594 if (level[e.dst] == -1 && flow_e[rev(e).flowp] < rev(e).cap) 595 level[que[back++] = e.dst] = 1 + level[u]; 596 } 597 if (level[source] == -1) 598 break; 599 std::fill(edge_pos.begin(), edge_pos.end(), 0); 600 std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res) 601 { 602 if (from == sink) 603 return res; 604 for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept) 605 { 606 edge &e = adj[from][ept]; 607 if (flow_e[e.flowp] == e.cap || level[e.dst] + 1 != level[from]) continue; 608 flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp])); 609 if (push > 0) 610 { 611 flow_e[e.flowp] += push; 612 flow_e[rev(e).flowp] -= push; 613 if (flow_e[e.flowp] == e.cap) 614 ++ept; 615 return push; 616 } 617 } 618 return static_cast<flow_type>(0); 619 }; 620 for (flow_type f; (f = find_path(source, oo)) > 0;) 621 flow += f; 622 } 623 return flow; 624 } 625 626 result_type max_flow2(int source, int sink, vector<flow_type> &flow_e) 627 { 628 result_type flow = 0; 629 std::function<flow_type(int, flow_type)> find_path = [&](int from, flow_type res) 630 { 631 level[from] = 1; 632 if (from == sink) 633 return res; 634 for (int &ept = edge_pos[from]; ept < (int) adj[from].size(); ++ept) 635 { 636 edge &e = adj[from][ept]; 637 if (level[e.dst] == 1 || flow_e[e.flowp] == e.cap) continue; 638 flow_type push = find_path(e.dst, std::min(res, e.cap - flow_e[e.flowp])); 639 if (push > 0) 640 { 641 flow_e[e.flowp] += push; 642 flow_e[rev(e).flowp] -= push; 643 if (flow_e[e.flowp] == e.cap) 644 ++ept; 645 return push; 646 } 647 } 648 return static_cast<flow_type>(0); 649 }; 650 651 for (bool ok = true; ok; ) 652 { 653 int it = 0; 654 std::fill(edge_pos.begin(), edge_pos.end(), 0); 655 for (flow_type f; ; ++it) 656 { 657 std::fill(level.begin(), level.end(), -1); 658 f = find_path(source, oo); 659 if (f == 0) 660 { 661 if (it == 0) ok = false; 662 break; 663 } 664 flow += f; 665 } 666 } 667 return flow; 668 } 669 670 int flow_id; 671 private: 672 std::vector<std::vector<edge>> adj; 673 std::vector<int> que; 674 std::vector<int> level; 675 std::vector<int> edge_pos; 676 677 inline edge& rev(const edge &e) { return adj[e.dst][e.rev]; } 678 }; 679 680 const int inf = 25; 681 682 struct edge 683 { 684 int u, v, w; 685 }; 686 687 mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); 688 689 void relabel(int n, vector<edge> &e, int k) 690 { 691 shuffle(e.begin() + k, e.end(), rng); 692 693 vector<vector<pair<int, int>>> adj(n); 694 for (auto &i : e) 695 adj[i.u].push_back({ i.v, &i-&e[0] }); 696 697 vector<edge> ne = e; 698 vector<int> id(n, -1); 699 id[0] = 0; 700 id[n-1] = n-1; 701 int sz = 1, esz = k; 702 703 function<void(int)> dfs = [&](int u) 704 { 705 for (auto &v : adj[u]) 706 { 707 if (v.second >= k) 708 { 709 ne[esz++] = e[v.second]; 710 v.second = -1; 711 } 712 if (id[v.first] == -1) 713 { 714 id[v.first] = sz++; 715 dfs(v.first); 716 } 717 } 718 }; 719 dfs(0); 720 721 for (auto &u : adj) 722 for (auto v : u) 723 if (v.second >= k) 724 ne[esz++] = e[v.second]; 725 726 for (int i = 0; i < n; ++i) 727 if (id[i] == -1) 728 id[i] = sz++; 729 730 e = ne; 731 for (auto &i : e) 732 { 733 i.u = id[i.u]; 734 i.v = id[i.v]; 735 } 736 } 737 738 struct masks 739 { 740 int x, cost; 741 vector<int> flow_e; 742 743 bool operator<(const masks &o) const 744 { 745 return cost < o.cost; 746 } 747 }; 748 749 typedef std::chrono::_V2::system_clock::time_point timepoint; 750 751 timepoint get_time() 752 { 753 return std::chrono::high_resolution_clock::now(); 754 } 755 756 int get_elapsed(timepoint t) 757 { 758 return std::chrono::duration_cast<std::chrono::milliseconds>(get_time() - t).count(); 759 } 760 761 int main() 762 { 763 ios_base::sync_with_stdio(0), cin.tie(0); 764 765 int n, m, k, q; 766 cin >> n >> m >> k >> q; 767 vector<edge> e(m); 768 for (auto &i : e) cin >> i.u >> i.v >> i.w, --i.u, --i.v; 769 770 vector<int> mask(1 << k, -1); 771 772 relabel(n, e, k); 773 dinic<int> d(n); 774 for (int i = 0; i < m; ++i) 775 d.add_edge(e[i].u, e[i].v, ((i < k) ? inf : e[i].w)); 776 777 vector<int> flow_e(d.flow_id); 778 for (int i = 0; i < k; ++i) 779 flow_e[2*i] = inf; 780 781 mask[0] = d.max_flow(0, n-1, flow_e); 782 783 priority_queue<masks> pq; 784 pq.push({ 0, 0, flow_e }); 785 while (!pq.empty()) 786 { 787 int x = pq.top().x; 788 flow_e = pq.top().flow_e; 789 pq.pop(); 790 791 for (int j = 0; j < k; ++j) 792 if ((~x >> j & 1) && mask[x | 1 << j] == -1) 793 { 794 auto n_flow_e = flow_e; 795 n_flow_e[2 * j] = 0; 796 auto t = get_time(); 797 mask[x | 1 << j] = mask[x] + d.max_flow2(0, n-1, n_flow_e); 798 pq.push({ x | 1 << j, get_elapsed(t), n_flow_e }); 799 } 800 } 801 802 vector<int> cut(1 << k), bit(1 << k); 803 for (int i = 1; i < 1 << k; ++i) 804 bit[i] = i & -i; 805 806 const int U = (1 << k) - 1; 807 while (q--) 808 { 809 for (int i = 0; i < k; ++i) 810 cin >> cut[1 << i]; 811 812 int ans = mask[U]; 813 for (int i = 1; i < 1<<k; ++i) 814 { 815 cut[i] = cut[i ^ bit[i]] + cut[bit[i]]; 816 ans = min(ans, cut[i] + mask[U ^ i]); 817 } 818 cout << ans << "\n"; 819 } 820 821 return 0; 822 } 823 ``` 824 825 Problem idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") 826 827 Solution idea: [mnaeraxr](/profile/mnaeraxr "Grandmaster mnaeraxr") and [Devil](/profile/Devil "Master Devil")