2057.md (21637B)
1 Source: https://codeforces.com/blog/entry/138119 2 3 Thank you for participating! We hope you enjoyed our problems 4 5 ## [2057A - MEX Table](/contest/2057/problem/A "Hello 2025") 6 7 Author and developer is [dope](/profile/dope "Master dope") 8 9 **Solution** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using i64 = long long; 19 20 void solve() { 21 int n, m; 22 std::cin >> n >> m; 23 std::cout << std::max(n, m) + 1 << "\n"; 24 } 25 26 signed main() { 27 std::ios::sync_with_stdio(false); 28 std::cin.tie(nullptr); 29 30 int t = 1; 31 std::cin >> t; 32 33 while (t--) { 34 solve(); 35 } 36 } 37 ``` 38 39 ## [2057B - Gorilla and the Exam](/contest/2057/problem/B "Hello 2025") 40 41 Author and developer is [dope](/profile/dope "Master dope") 42 43 **Solution** 44 45 Tutorial is loading... 46 47 **Implementation** 48 49 ``` 50 #include <bits/stdc++.h> 51 52 using i64 = long long; 53 54 void solve() { 55 int n, k; 56 std::cin >> n >> k; 57 std::vector<int> a(n); 58 for (int i = 0; i < n; i++) { 59 std::cin >> a[i]; 60 } 61 std::sort(a.begin(), a.end()); 62 std::vector<int> cnt = {1}; 63 for (int i = 1; i < n; i++) { 64 if (a[i] == a[i - 1]) { 65 cnt.back()++; 66 } else { 67 cnt.emplace_back(1); 68 } 69 } 70 std::sort(cnt.begin(), cnt.end()); 71 int m = cnt.size(); 72 for (int i = 0; i < m - 1; i++) { 73 if (cnt[i] > k) { 74 std::cout << m - i << "\n"; 75 return; 76 } 77 k -= cnt[i]; 78 } 79 std::cout << 1 << "\n"; 80 } 81 82 signed main() { 83 std::ios::sync_with_stdio(false); 84 std::cin.tie(nullptr); 85 86 int t = 1; 87 std::cin >> t; 88 89 while (t--) { 90 solve(); 91 } 92 } 93 ``` 94 95 ## [2057C - Trip to the Olympiad](/contest/2057/problem/C "Hello 2025") 96 97 Author is [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") and developer is [dope](/profile/dope "Master dope") 98 99 **Solution** 100 101 Tutorial is loading... 102 103 **Implementation** 104 105 ``` 106 #include <bits/stdc++.h> 107 108 using i64 = long long; 109 110 void solve() { 111 int l, r; 112 std::cin >> l >> r; 113 int k = 31 - __builtin_clz(l ^ r); 114 int a = l | ((1 << k) - 1), b = a + 1, c = (a == l ? r : l); 115 std::cout << a << " " << b << " " << c << "\n"; 116 } 117 118 signed main() { 119 std::ios::sync_with_stdio(false); 120 std::cin.tie(nullptr); 121 122 int t = 1; 123 std::cin >> t; 124 125 while (t--) { 126 solve(); 127 } 128 } 129 ``` 130 131 ## [2057D - Gifts Order](/contest/2057/problem/D "Hello 2025") 132 133 Author and developer is [dope](/profile/dope "Master dope"), also thanks [mupp](/profile/mupp "Master mupp") and [KoT_OsKaR](/profile/KoT_OsKaR "Expert KoT_OsKaR") for discussing this problem with me 134 135 **Solution** 136 137 Tutorial is loading... 138 139 **Implementation** 140 141 ``` 142 #include <bits/stdc++.h> 143 144 using i64 = long long; 145 146 template<class Info> 147 struct SegmentTree { 148 int n; 149 std::vector<Info> info; 150 151 SegmentTree() : n(0) {} 152 153 SegmentTree(int n_, Info v_ = Info()) { 154 init(n_, v_); 155 } 156 157 template<class T> 158 SegmentTree(std::vector<T> init_) { 159 init(init_); 160 } 161 162 void init(int n_, Info v_ = Info()) { 163 init(std::vector<Info>(n_, v_)); 164 } 165 166 template<class T> 167 void init(std::vector<T> init_) { 168 n = init_.size(); 169 int sz = (1 << (std::__lg(n - 1) + 1)); 170 info.assign(sz * 2, Info()); 171 std::function<void(int, int, int)> build = [&](int v, int l, int r) { 172 if (l == r) { 173 info[v] = init_[l]; 174 return; 175 } 176 int m = (l + r) / 2; 177 build(v + v, l, m); 178 build(v + v + 1, m + 1, r); 179 info[v] = info[v + v] + info[v + v + 1]; 180 }; 181 build(1, 0, n - 1); 182 } 183 184 Info rangeQuery(int v, int l, int r, int tl, int tr) { 185 if (r < tl || l > tr) { 186 return Info(); 187 } 188 if (l >= tl && r <= tr) { 189 return info[v]; 190 } 191 int m = (l + r) / 2; 192 return rangeQuery(v + v, l, m, tl, tr) + rangeQuery(v + v + 1, m + 1, r, tl, tr); 193 } 194 195 Info rangeQuery(int l, int r) { 196 return rangeQuery(1, 0, n - 1, l, r); 197 } 198 199 void modify(int v, int l, int r, int i, const Info &x) { 200 if (l == r) { 201 info[v] = x; 202 return; 203 } 204 int m = (l + r) / 2; 205 if (i <= m) { 206 modify(v + v, l, m, i, x); 207 } else { 208 modify(v + v + 1, m + 1, r, i, x); 209 } 210 info[v] = info[v + v] + info[v + v + 1]; 211 } 212 213 void modify(int i, const Info &x) { 214 modify(1, 0, n - 1, i, x); 215 } 216 217 Info query(int v, int l, int r, int i) { 218 if (l == r) { 219 return info[v]; 220 } 221 int m = (l + r) / 2; 222 if (i <= m) { 223 return query(v + v, l, m, i); 224 } else { 225 return query(v + v + 1, m + 1, r, i); 226 } 227 } 228 229 Info query(int i) { 230 return query(1, 0, n - 1, i); 231 } 232 }; 233 234 const int INF = 1E9; 235 236 struct Info { 237 int min1, min2, max1, max2, ans1, ans2; 238 239 Info() : min1(INF), min2(INF), max1(-INF), max2(-INF), ans1(0), ans2(0) {} 240 241 Info(std::pair<int, int> x) : min1(x.first), min2(x.second), max1(x.first), max2(x.second), ans1(0), ans2(0) {} 242 }; 243 244 Info operator+(const Info &a, const Info &b) { 245 Info res; 246 res.min1 = std::min(a.min1, b.min1); 247 res.min2 = std::min(a.min2, b.min2); 248 res.max1 = std::max(a.max1, b.max1); 249 res.max2 = std::max(a.max2, b.max2); 250 res.ans1 = std::max({a.ans1, b.ans1, b.max1 - a.min1}); 251 res.ans2 = std::max({a.ans2, b.ans2, a.max2 - b.min2}); 252 return res; 253 } 254 255 void solve() { 256 int n, q; 257 std::cin >> n >> q; 258 std::vector<int> a(n); 259 std::vector<std::pair<int, int>> t(n); 260 for (int i = 0; i < n; i++) { 261 std::cin >> a[i]; 262 t[i] = {a[i] - i, a[i] + i - n + 1}; 263 } 264 SegmentTree<Info> st(t); 265 auto query = [&]() { 266 return std::max(st.info[1].ans1, st.info[1].ans2); 267 }; 268 std::cout << query() << "\n"; 269 for (int i = 0; i < q; i++) { 270 int p, x; 271 std::cin >> p >> x; 272 p--; 273 t[p] = {x - p, x + p - n + 1}; 274 st.modify(p, t[p]); 275 std::cout << query() << "\n"; 276 } 277 } 278 279 signed main() { 280 std::ios::sync_with_stdio(false); 281 std::cin.tie(nullptr); 282 283 int t; 284 std::cin >> t; 285 286 while (t--) { 287 solve(); 288 } 289 } 290 ``` 291 292 ## [2057E1 - Another Exercise on Graphs (Easy Version)](/contest/2057/problem/E1 "Hello 2025") 293 294 Author is [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") and developer is [dope](/profile/dope "Master dope") 295 296 **Solution** 297 298 Tutorial is loading... 299 300 **Implementation** 301 302 ``` 303 #include <bits/stdc++.h> 304 305 using i64 = long long; 306 307 void solve() { 308 int n, m, q; 309 std::cin >> n >> m >> q; 310 std::vector<std::array<int, 3>> edges(m); 311 for (int i = 0; i < m; i++) { 312 int v, u, w; 313 std::cin >> v >> u >> w; 314 v--, u--; 315 edges[i] = {v, u, w}; 316 } 317 std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) { 318 return a[2] < b[2]; 319 }); 320 constexpr int INF = 1e9; 321 std::vector<int> value(m + 1); 322 std::vector<std::vector<std::vector<int>>> dis(m + 1, std::vector<std::vector<int>>(n, std::vector<int>(n, INF))); 323 for (int i = 0; i < n; i++) { 324 dis[0][i][i] = 0; 325 } 326 for (auto edge : edges) { 327 int v = edge[0], u = edge[1]; 328 dis[0][v][u] = dis[0][u][v] = 1; 329 } 330 for (int k = 0; k < n; k++) { 331 for (int i = 0; i < n; i++) { 332 for (int j = 0; j < n; j++) { 333 dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]); 334 } 335 } 336 } 337 int p = 1; 338 for (auto edge : edges) { 339 int v = edge[0], u = edge[1], w = edge[2]; 340 for (int i = 0; i < n; i++) { 341 for (int j = 0; j < n; j++) { 342 dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]}); 343 } 344 } 345 value[p++] = w; 346 } 347 for (int i = 0; i < q; i++) { 348 int v, u, k; 349 std::cin >> v >> u >> k; 350 v--, u--; 351 int low = 0, high = m; 352 while (high - low > 1) { 353 int mid = (low + high) / 2; 354 if (dis[mid][v][u] < k) { 355 high = mid; 356 } else { 357 low = mid; 358 } 359 } 360 std::cout << value[high] << " \n"[i == q - 1]; 361 } 362 } 363 364 signed main() { 365 std::ios::sync_with_stdio(false); 366 std::cin.tie(nullptr); 367 368 int t = 1; 369 std::cin >> t; 370 371 while (t--) { 372 solve(); 373 } 374 } 375 ``` 376 377 ## [2057E2 - Another Exercise on Graphs (hard version)](/contest/2057/problem/E2 "Hello 2025") 378 379 Author is [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") and developer is [dope](/profile/dope "Master dope") 380 381 **Solution** 382 383 Tutorial is loading... 384 385 **Implementation** 386 387 ``` 388 #include <bits/stdc++.h> 389 390 using i64 = long long; 391 392 struct DSU { 393 std::vector<int> p, sz, h; 394 395 DSU(int n = 0) : p(n), sz(n, 1), h(n) { 396 std::iota(p.begin(), p.end(), 0); 397 } 398 399 int leader(int x) { 400 if (x == p[x]) { 401 return x; 402 } 403 return leader(p[x]); 404 } 405 406 bool same(int x, int y) { 407 return leader(x) == leader(y); 408 } 409 410 bool merge(int x, int y) { 411 x = leader(x); 412 y = leader(y); 413 if (x == y) return false; 414 if (h[x] < h[y]) { 415 std::swap(x, y); 416 } 417 if (h[x] == h[y]) { 418 ++h[x]; 419 } 420 sz[x] += sz[y]; 421 p[y] = x; 422 return true; 423 } 424 425 int size(int x) { 426 return sz[leader(x)]; 427 } 428 }; 429 430 void solve() { 431 int n, m, q; 432 std::cin >> n >> m >> q; 433 std::vector<std::array<int, 3>> edges(m); 434 for (int i = 0; i < m; i++) { 435 int v, u, w; 436 std::cin >> v >> u >> w; 437 v--, u--; 438 edges[i] = {v, u, w}; 439 } 440 std::sort(edges.begin(), edges.end(), [&](const std::array<int, 3> &a, const std::array<int, 3> &b) { 441 return a[2] < b[2]; 442 }); 443 constexpr int INF = 1e9; 444 std::vector<int> value(n); 445 std::vector<std::vector<std::vector<int>>> dis(n, std::vector<std::vector<int>>(n, std::vector<int>(n, INF))); 446 for (int i = 0; i < n; i++) { 447 dis[0][i][i] = 0; 448 } 449 for (auto edge : edges) { 450 int v = edge[0], u = edge[1]; 451 dis[0][v][u] = dis[0][u][v] = 1; 452 } 453 for (int k = 0; k < n; k++) { 454 for (int i = 0; i < n; i++) { 455 for (int j = 0; j < n; j++) { 456 dis[0][i][j] = std::min(dis[0][i][j], dis[0][i][k] + dis[0][k][j]); 457 } 458 } 459 } 460 int p = 1; 461 DSU dsu(n); 462 for (auto edge : edges) { 463 int v = edge[0], u = edge[1], w = edge[2]; 464 if (dsu.merge(v, u)) { 465 for (int i = 0; i < n; i++) { 466 for (int j = 0; j < n; j++) { 467 dis[p][i][j] = std::min({dis[p - 1][i][j], dis[p - 1][i][v] + dis[p - 1][u][j], dis[p - 1][i][u] + dis[p - 1][v][j]}); 468 } 469 } 470 value[p++] = w; 471 } 472 } 473 for (int i = 0; i < q; i++) { 474 int v, u, k; 475 std::cin >> v >> u >> k; 476 v--, u--; 477 int low = 0, high = n - 1; 478 while (high - low > 1) { 479 int mid = (low + high) / 2; 480 if (dis[mid][v][u] < k) { 481 high = mid; 482 } else { 483 low = mid; 484 } 485 } 486 std::cout << value[high] << " \n"[i == q - 1]; 487 } 488 } 489 490 signed main() { 491 std::ios::sync_with_stdio(false); 492 std::cin.tie(nullptr); 493 494 int t = 1; 495 std::cin >> t; 496 497 while (t--) { 498 solve(); 499 } 500 } 501 ``` 502 503 ## [2057F - Formation](/contest/2057/problem/F "Hello 2025") 504 505 Author is [induk_v_tsiane](/profile/induk_v_tsiane "International Grandmaster induk_v_tsiane") and developer is [dope](/profile/dope "Master dope") 506 507 **Solution** 508 509 Tutorial is loading... 510 511 **Implementation** 512 513 ``` 514 #include <bits/stdc++.h> 515 516 using i64 = long long; 517 518 void solve() { 519 int n, q; 520 std::cin >> n >> q; 521 std::vector<int> a(n); 522 for (int i = 0; i < n; i++) { 523 std::cin >> a[i]; 524 } 525 constexpr int LG = 30; 526 std::vector<std::array<i64, 4>> events; 527 for (int i = 0; i < n; i++) { 528 i64 pow = 1, sum = 0; 529 i64 dop = 0; 530 for (int j = 0; j < LG; j++) { 531 if (i - j < 0) { 532 break; 533 } 534 sum += a[i - j]; 535 i64 L = dop, R; 536 if (i - j == 0) { 537 R = 2E18; 538 } else { 539 i64 x = (pow * 4 - 2) * a[i - j - 1] - sum; 540 R = x; 541 dop = x; 542 } 543 pow *= 2; 544 events.push_back({L, -1, j, sum}); 545 events.push_back({R, 1, j, sum}); 546 } 547 } 548 for (int i = 0; i < q; i++) { 549 int x; 550 std::cin >> x; 551 events.push_back({x, 0, i, 0}); 552 } 553 std::sort(events.begin(), events.end()); 554 std::vector<int> ans(q); 555 std::vector<std::multiset<i64>> st(LG); 556 for (auto item : events) { 557 int h = item[0]; 558 int o = item[1]; 559 if (o == -1) { 560 int j = item[2]; 561 i64 sum = item[3]; 562 st[j].insert(sum); 563 } else if (o == 1) { 564 int j = item[2]; 565 i64 sum = item[3]; 566 st[j].erase(st[j].find(sum)); 567 } else { 568 int i = item[2]; 569 int low = 0, high = 2E9 + 1; 570 while (high - low > 1) { 571 int mid = (0LL + low + high) / 2; 572 int cur = mid; 573 i64 pos = 0; 574 bool ok = false; 575 for (int cnt = 0; cnt < LG; cnt++) { 576 if (st[cnt].empty()) { 577 continue; 578 } 579 i64 neg = *st[cnt].rbegin(); 580 pos += cur; 581 cur = (cur + 1) / 2; 582 if (pos - neg <= h) { 583 ok = true; 584 break; 585 } 586 } 587 if (ok) { 588 low = mid; 589 } else { 590 high = mid; 591 } 592 } 593 ans[i] = low; 594 } 595 } 596 for (int i = 0; i < q; i++) { 597 std::cout << ans[i] << " \n"[i == q - 1]; 598 } 599 } 600 601 signed main() { 602 std::ios::sync_with_stdio(false); 603 std::cin.tie(nullptr); 604 605 int t = 1; 606 std::cin >> t; 607 608 while (t--) { 609 solve(); 610 } 611 } 612 ``` 613 614 **Alternative solution** 615 616 ``` 617 // Parallel binary search technique optimizes log^3 => log^2 618 // SegmentTree might be faster then std::multiset 619 // sl[i] should equals max(a) at the begining cause IDK how to explain but it's obviously important 620 621 #include <bits/stdc++.h> 622 #include <algorithm> 623 624 using namespace std; 625 using ll = long long; 626 627 constexpr int W = 31; 628 constexpr int C = 1'000'000'000; 629 630 struct Event { 631 int x; 632 int ind; 633 ll s; 634 635 bool operator<(const Event& rhs) const { return x < rhs.x; } 636 }; 637 638 struct SegmentTree { 639 int n; 640 vector<ll> sgt; 641 642 SegmentTree(int n) : n(n), sgt(2 * n, -1) {} 643 644 void Change(int i, ll x) { 645 for (sgt[i += n] = x; i != 1; i >>= 1) { 646 sgt[i >> 1] = max(sgt[i], sgt[i ^ 1]); 647 } 648 } 649 650 int GlobalMax() const { return sgt[1]; } 651 }; 652 653 vector<int> solve(const vector<int>& a, const vector<int>& q) { 654 const int n = a.size(), m = q.size(); 655 656 vector<ll> ps(n + 1); 657 for (int i = 0; i < n; ++i) 658 ps[i + 1] = ps[i] + a[i]; 659 660 vector<ll> min_x(n, 0); 661 vector<vector<pair<int, ll>>> change_sum(W); 662 663 vector<Event> events; 664 events.reserve(2 * n); 665 for (int j = 1; j <= W && j <= n; ++j) { 666 events.clear(); 667 668 for (int i = j - 1; i < n; ++i) { 669 min_x[i] = max(min_x[i], 1 + ((a[i - j + 1] - 1ll) << (j - 1))); 670 ll max_x = i == j - 1 ? 2ll * C : ((ll)a[i - j] << j); 671 max_x = min<ll>(max_x, a[i] + C); 672 673 if (min_x[i] > max_x) { 674 continue; 675 } 676 const ll xsum = ps[i + 1] - ps[i + 1 - j]; 677 events.push_back(Event{(int)min_x[i], i, xsum}); 678 events.push_back(Event{(int)max_x + 1, i, -1}); 679 } 680 sort(events.begin(), events.end()); 681 682 SegmentTree sgt(n); 683 const int k = events.size(); 684 ll was_max = -1; 685 686 for (int i = 0; i < k;) { 687 int s = i; 688 while (i < k && events[i].x == events[s].x) { 689 sgt.Change(events[i].ind, events[i].s); 690 ++i; 691 } 692 ll cur_max = sgt.GlobalMax(); 693 if (cur_max != was_max) { 694 change_sum[j - 1].emplace_back(events[s].x, cur_max); 695 was_max = cur_max; 696 } 697 } 698 } 699 700 vector<int> sl(m, *max_element(a.begin(), a.end())), sr(m, 2 * C + 1); 701 702 vector<int> ord_to_check(m); 703 iota(ord_to_check.begin(), ord_to_check.end(), 0); 704 for (int iter = 32; iter--;) { 705 vector<int> sm(m); 706 for (int i = 0; i < m; ++i) { 707 sm[i] = sl[i] + (sr[i] - sl[i]) / 2; 708 } 709 sort(ord_to_check.begin(), ord_to_check.end(), [&](int lhs, int rhs) { 710 return sm[lhs] < sm[rhs]; 711 }); 712 713 vector<int> ptr(W); 714 vector<ll> actual_sum(W, -1); 715 for (int i : ord_to_check) { 716 const int x = sm[i]; 717 718 719 ll upper_sum = 0; 720 bool nice = false; 721 for (int w = 0; w < W; ++w) { 722 int& j = ptr[w]; 723 while (j < change_sum[w].size() && change_sum[w][j].first <= x) { 724 actual_sum[w] = change_sum[w][j++].second; 725 } 726 upper_sum += 1 + ((x - 1) >> w); 727 if (upper_sum - actual_sum[w] <= q[i]) { 728 nice = true; 729 } 730 } 731 732 if (nice) { 733 sl[i] = sm[i]; 734 } else { 735 sr[i] = sm[i]; 736 } 737 } 738 } 739 740 return sl; 741 } 742 743 int main() { 744 ios::sync_with_stdio(0); 745 cin.tie(0); 746 747 int t = 1; 748 cin >> t; 749 while (t--) { 750 int n, q; 751 cin >> n >> q; 752 vector<int> a(n), k(q); 753 for (int& x : a) 754 cin >> x; 755 for (int& x : k) 756 cin >> x; 757 758 auto ans = solve(a, k); 759 for (int x : ans) 760 cout << x << ' '; 761 cout << '\n'; 762 } 763 } 764 ``` 765 766 ## [2057G - Secret Message](/contest/2057/problem/G "Hello 2025") 767 768 Author and developer is [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") 769 770 **Solution** 771 772 Tutorial is loading... 773 774 **Implementation** 775 776 ``` 777 #include <bits/stdc++.h> 778 779 using namespace std; 780 using pi = pair<int, int>; 781 782 void solve() { 783 int n, m; cin >> n >> m; 784 vector<string> v(n); 785 for (auto& w : v) cin >> w; 786 787 auto col = [](int x, int y) { 788 int c = (x+2*y)%5; 789 if (c < 0) c += 5; 790 return c; 791 }; 792 auto cell = [&](int x, int y) { 793 if (x < 0 || y < 0 || x >= n || y >= m) return false; 794 return v[x][y] == '#'; 795 }; 796 797 array<vector<pi>, 5> colorings; 798 for (int i = 0; i < n; ++i) 799 for (int j = 0; j < m; ++j) { 800 if (!cell(i, j)) continue; 801 colorings[col(i, j)].emplace_back(i, j); 802 803 for (int di = -1; di <= 1; ++di) 804 for (int dj = -1; dj <= 1; ++dj) { 805 if (abs(di) + abs(dj) != 1) continue; 806 if (!cell(i+di, j+dj)) { 807 colorings[col(i+di, j+dj)].emplace_back(i, j); 808 } 809 } 810 } 811 812 auto coloring = colorings[0]; 813 for (const auto& w : colorings) 814 if (w.size() < coloring.size()) coloring = w; 815 for (auto [x, y] : coloring) v[x][y] = 'S'; 816 for (auto line : v) cout << line << '\n'; 817 } 818 819 int main() { 820 ios::sync_with_stdio(0); cin.tie(0); 821 822 int t; cin >> t; 823 while (t--) 824 solve(); 825 } 826 ``` 827 828 ## [2057H - Coffee Break](/contest/2057/problem/H "Hello 2025") 829 830 Author and developer is [teraqqq](/profile/teraqqq "International Grandmaster teraqqq") 831 832 **Solution** 833 834 Tutorial is loading... 835 836 **Implementation** 837 838 ``` 839 #include <bits/stdc++.h> 840 841 using namespace std; 842 using vi = vector<int>; 843 using ll = long long; 844 845 vector<ll> a, lhs, rhs; 846 vector<int> st; 847 848 vector<ll> get_right_out(const vector<ll>& a, vector<ll>& res) { 849 const int n = a.size(); 850 st.clear(); 851 res.assign(n+1, 0); 852 853 for (int i = 0; i < n; ++i) { 854 ll x = a[i] + res[i]; 855 st.push_back(i); 856 857 while (x != 0) { 858 if (st.empty()) { 859 const int len = i + 1; 860 const ll cnt = x / (len + 1); 861 res[i+1] += cnt * len; 862 x -= cnt * (len + 1); 863 864 if (x != 0) { 865 res[i+1] += x; 866 st.push_back(x-1); 867 x = 0; 868 } 869 } else { 870 const int j = st.back(); 871 if (x > i - j) { 872 res[i+1] += i - j; 873 st.pop_back(); 874 x -= i - j + 1; 875 } else { 876 res[i+1] += x; 877 st.back() += x; 878 x = 0; 879 } 880 } 881 } 882 } 883 884 return res; 885 } 886 887 vector<ll> get_left_out(vector<ll>& a, vector<ll>& b) { 888 reverse(a.begin(), a.end()); 889 get_right_out(a, b); 890 reverse(b.begin(), b.end()); 891 reverse(a.begin(), a.end()); 892 return b; 893 } 894 895 void solve() { 896 int n; cin >> n; 897 898 a.resize(n); 899 for (ll& x : a) cin >> x; 900 901 get_right_out(a, lhs); 902 get_left_out(a, rhs); 903 904 ll ans = 0; 905 for (int i = 0; i < n; ++i) 906 cout << lhs[i] + a[i] + rhs[i+1] << ' '; 907 cout << '\n'; 908 } 909 910 int main() { 911 ios::sync_with_stdio(0); cin.tie(0); 912 913 int t = 1; 914 cin >> t; 915 while (t--) solve(); 916 } 917 ```