codeforces-scrape

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

2110.md (7809B)


      1 Source: https://codeforces.com/blog/entry/143186
      2 
      3 I hope everyone enjoyed the tasks, and thank you for participating.
      4 
      5 [2110A - Fashionable Array](/contest/2110/problem/A "Codeforces Round 1026 (Div. 2)")
      6 
      7 **Editorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution**
     12 
     13 ```
     14 #include <bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 void solve() {
     19     int n;
     20     cin >> n;
     21     vector<int> x(n);
     22     for (int i = 0; i < n; ++i) {
     23         cin >> x[i];
     24     }
     25     sort(x.begin(), x.end());
     26     if (x[0] % 2 == x[n - 1] % 2) {
     27         cout << 0 << endl;
     28         return;
     29     }
     30     int left = n, right = n;
     31     for (int i = 1; i < n; ++i) {
     32         if (x[i] % 2 != x[0] % 2) {
     33             left = i;
     34             break;
     35         }
     36     }
     37     for (int i = 1; i < n; ++i) {
     38         if (x[n - i - 1] % 2 != x[n - 1] % 2) {
     39             right = i;
     40             break;
     41         }
     42     }
     43     cout << min(left, right) << '\n';
     44 }
     45 
     46 int main() {
     47     int t;
     48     cin >> t;
     49     while (t--) {
     50         solve();
     51     }
     52 }
     53 ```
     54 
     55 [2110B - Down with Brackets](/contest/2110/problem/B "Codeforces Round 1026 (Div. 2)")
     56 
     57 **Editorial**
     58 
     59 Tutorial is loading...
     60 
     61 **Solution**
     62 
     63 ```
     64 #include "bits/stdc++.h"
     65 #define int long long
     66 #define all(v) (v).begin(), (v).end()
     67 #define pb push_back
     68 #define em emplace_back
     69 #define mp make_pair
     70 #define F first
     71 #define S second
     72 
     73 using namespace std;
     74 template<class C>
     75 using vec = vector<C>;
     76 using vi = vector<int>;
     77 using vpi = vector<pair<int, int>>;
     78 using pii = pair<int, int>;
     79 
     80 void solve() {
     81   string s;
     82   cin >> s;
     83   int n = s.size();
     84   int bal = 0;
     85   for (int i = 1; i + 1 < n; i++) {
     86     if (s[i] == '(') bal++;
     87     else bal--;
     88     if (bal < 0) {
     89       cout << "YES\n";
     90       return;
     91     }
     92   }
     93   if (bal == 0) {
     94     cout << "NO\n";
     95   } else {
     96     cout << "YES\n";
     97   }
     98 }
     99 
    100 signed main() {
    101   int tt;
    102   cin >> tt;
    103   while (tt--) {
    104     solve();
    105   }
    106 }
    107 ```
    108 
    109 [2110C - Racing](/contest/2110/problem/C "Codeforces Round 1026 (Div. 2)")
    110 
    111 **Editorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution**
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119 
    120 using namespace std;
    121 
    122 void solve() {
    123     int n;
    124     cin >> n;
    125     vector<int> d(n);
    126     for (auto &x : d) {
    127         cin >> x;
    128     }
    129     vector<int> l(n), r(n);
    130     for (int i = 0; i < n; ++i) {
    131         cin >> l[i] >> r[i];
    132     }
    133     int left = 0;
    134     vector<int> last;
    135     for (int i = 0; i < n; ++i) {
    136         if (d[i] == -1) {
    137             last.push_back(i);
    138         } else {
    139             left += d[i];
    140         }
    141         while (left < l[i]) {
    142             if (last.empty()) {
    143                 cout << -1 << '\n';
    144                 return;
    145             }
    146             d[last.back()] = 1;
    147             ++left;
    148             last.pop_back();
    149         }
    150         while (left + last.size() > r[i]) {
    151             if (last.empty()) {
    152                 cout << -1 << '\n';
    153                 return;
    154             }
    155             d[last.back()] = 0;
    156             last.pop_back();
    157         }
    158     }
    159     for (auto &x : d) {
    160         cout << max(0, x) << " ";
    161     }
    162     cout << "\n";
    163     return;
    164 }
    165 
    166 signed main() {
    167     ios::sync_with_stdio(false);
    168     cin.tie(0);
    169     int t;
    170     cin >> t;
    171     while (t--) {
    172         solve();
    173     }
    174     return 0;
    175 }
    176 ```
    177 
    178 [2110D - Fewer Batteries](/contest/2110/problem/D "Codeforces Round 1026 (Div. 2)")
    179 
    180 **Editorial**
    181 
    182 Tutorial is loading...
    183 
    184 **Solution**
    185 
    186 ```
    187 #include <bits/stdc++.h>
    188 
    189 using namespace std;
    190 
    191 const int INF = 1e9 + 11;
    192 
    193 struct edge {
    194     int t, w;
    195     edge(int t, int w) : t(t), w(w) {}
    196 };
    197 
    198 void solve() {
    199     int n, m;
    200     cin >> n >> m;
    201     vector<int> b(n);
    202     for (auto &x : b) {
    203         cin >> x;
    204     }
    205     vector<vector<edge>> graph(n);
    206     for (int i = 0; i < m; ++i) {
    207         int s, t, w;
    208         cin >> s >> t >> w;
    209         --s; --t;
    210         graph[s].push_back(edge(t, w));
    211     }
    212     auto check = [&](int maxW) {
    213         vector<int> best(n, 0);
    214         for (int i = 0; i < n; ++i) {
    215             if (i > 0 && best[i] == 0) {
    216                 continue;
    217             }
    218             best[i] += b[i];
    219             best[i] = min(best[i], maxW);
    220             for (auto p : graph[i]) {
    221                 if (p.w <= best[i]) {
    222                     best[p.t] = max(best[p.t], best[i]);
    223                 }
    224             }
    225         }
    226         return (best.back() > 0);
    227     };
    228     if (!check(INF)) {
    229         cout << -1 << endl;
    230         return;
    231     }
    232     int l = 0, r = INF;
    233     while (r - l > 1) {
    234         int mid = (l + r) / 2;
    235         if (check(mid)) {
    236             r = mid;
    237         } else {
    238             l = mid;
    239         }
    240     }
    241     cout << r << endl;
    242 }
    243 
    244 int main() {
    245     ios::sync_with_stdio(false);
    246     cin.tie(0);
    247     int t;
    248     cin >> t;
    249     while (t--) {
    250         solve();
    251     }
    252     return 0;
    253 }
    254 ```
    255 
    256 [2110E - Melody](/contest/2110/problem/E "Codeforces Round 1026 (Div. 2)")
    257 
    258 **Editorial**
    259 
    260 Tutorial is loading...
    261 
    262 **Solution**
    263 
    264 ```
    265 #include <bits/stdc++.h>
    266 
    267 using namespace std;
    268 
    269 vector<set<int>> graph;
    270 vector<int> ans;
    271 
    272 void dfs(int v) {
    273     while (!graph[v].empty()) {
    274         int u = *graph[v].begin();
    275         graph[u].erase(v);
    276         graph[v].erase(u);
    277         dfs(u);
    278     }
    279     ans.push_back(v);
    280 }
    281 
    282 signed main() {
    283     int t;
    284     cin >> t;
    285     while (t--) {
    286         graph.clear();
    287         ans.clear();
    288         int n;
    289         cin >> n;
    290         map<int, int> p, v;
    291         map<pair<int, int>, int> toIndex;
    292         vector<pair<int, int>> part;
    293         for (int i = 1; i <= n; ++i) {
    294             int volume, pitch;
    295             cin >> volume >> pitch;
    296             toIndex[make_pair(volume, pitch)] = i;
    297             if (p.count(pitch) == 0) {
    298                 p[pitch] = graph.size();
    299                 graph.push_back(set<int>());
    300                 part.push_back(make_pair(0, pitch));
    301             }
    302             if (v.count(volume) == 0) {
    303                 v[volume] = graph.size();
    304                 graph.push_back(set<int>());
    305                 part.push_back(make_pair(volume, 0));
    306             }
    307             graph[v[volume]].insert(p[pitch]);
    308             graph[p[pitch]].insert(v[volume]);
    309         }
    310         int root = 0;
    311         int cnt = 0;
    312         for (int i = 0; i < graph.size(); ++i) {
    313             if (graph[i].size() % 2 == 1) {
    314                 ++cnt;
    315                 root = i;
    316             }
    317         }
    318         dfs(root);
    319         if (ans.size() != n + 1 || cnt > 2) {
    320             cout << "NO" << endl;
    321             continue;
    322         }
    323         vector<int> out;
    324         for (int i = 0; i < n; ++i) {
    325             auto p1 = part[ans[i]];
    326             auto p2 = part[ans[i + 1]];
    327             out.push_back(toIndex[make_pair(p1.first + p2.first, p1.second + p2.second)]);
    328             if (out[i] == 0) {
    329                 out.clear();
    330                 break;
    331             }
    332         }
    333         if (out.empty()) {
    334             cout << "NO" << endl;
    335         } else {
    336             cout << "YES" << endl;
    337             for (int i = 0; i < n; ++i) {
    338                 cout << out[i] << " ";
    339             }
    340             cout << endl;
    341         }
    342     }
    343     return 0;
    344 }
    345 ```
    346 
    347 [2110F - Faculty](/contest/2110/problem/F "Codeforces Round 1026 (Div. 2)")
    348 
    349 **Editorial**
    350 
    351 Tutorial is loading...
    352 
    353 **Solution**
    354 
    355 ```
    356 #include <bits/stdc++.h>
    357 
    358 using namespace std;
    359 
    360 int f(int x, int y) {
    361     return (x % y) + (y % x);
    362 }
    363 
    364 void Solve() {
    365     int n;
    366     cin >> n;
    367     vector<int> a(n);
    368     for (int i = 0; i < n; ++i) {
    369         cin >> a[i];
    370     }
    371     int ans = 0;
    372     int mx = a[0];
    373     for (int i = 0; i < n; ++i) {
    374         ans = max(ans, f(mx, a[i]));
    375         if (a[i] > mx) {
    376             if (a[i] >= mx * 2) {
    377                 mx = a[i];
    378                 for (int j = 0; j < i; ++j) {
    379                     ans = max(ans, f(a[i], a[j]));
    380                 }
    381             } else {
    382                 mx = a[i];
    383                 ans = mx;
    384             }
    385         }
    386         cout << ans << ' ';
    387     }
    388     cout << endl;
    389 }
    390 
    391 int main() {
    392     ios::sync_with_stdio(false);
    393     cin.tie(0);
    394     int t;
    395     cin >> t;
    396     while (t--) {
    397         Solve();
    398     }
    399     return 0;
    400 }
    401 ```