codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```