codeforces-scrape

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

2113.md (11151B)


      1 Source: https://codeforces.com/blog/entry/143785
      2 
      3 [2113A - Shashliks](/contest/2113/problem/A "Codeforces Round 1031 (Div. 2)")
      4 
      5 **Tutorial**
      6 
      7 Tutorial is loading...
      8 
      9 **Code**
     10 
     11 ```
     12 #include <iostream>
     13 
     14 using namespace std;
     15 
     16 void solve() {
     17     int t, a, b, x, y;
     18     cin >> t >> a >> b >> x >> y;
     19     auto solve = [&](int t, int a, int b, int x, int y) {
     20         int cur = 0;
     21         cur += max((t - a + x) / x, 0);
     22         t -= max((t - a + x) / x, 0) * x;
     23         cur += max((t - b + y) / y, 0);
     24         return cur;
     25     };
     26     cout << max(solve(t, a, b, x, y), solve(t, b, a, y, x)) << endl;
     27 }
     28 
     29 signed main() {
     30     int q = 1;
     31     cin >> q;
     32     while (q --> 0)
     33         solve();
     34     return 0;
     35 }
     36 ```
     37 
     38 [2113B - Good Start](/contest/2113/problem/B "Codeforces Round 1031 (Div. 2)")
     39 
     40 **Tutorial**
     41 
     42 Tutorial is loading...
     43 
     44 **Code**
     45 
     46 ```
     47 def solve():
     48     w, h, a, b = map(int, input().split())
     49     x1, y1, x2, y2 = map(int, input().split())
     50  
     51     if x1 == x2:
     52         if abs(y1 - y2) % b == 0:
     53             return "Yes"
     54         else:
     55             return "No"
     56  
     57     if y1 == y2:
     58         if abs(x1 - x2) % a == 0:
     59             return "Yes"
     60         else:
     61             return "No"
     62  
     63     if (x1 - x2) % a == 0 or (y1 - y2) % b == 0:
     64         return "Yes"
     65     return "No"
     66  
     67 t = int(input())
     68 for _ in range(t):
     69     print(solve())
     70 ```
     71 
     72 [2113C - Smilo and Minecraft](/contest/2113/problem/C "Codeforces Round 1031 (Div. 2)")
     73 
     74 **Tutorial**
     75 
     76 Tutorial is loading...
     77 
     78 **Code**
     79 
     80 ```
     81 #include <algorithm>
     82 #include <iostream>
     83 #include <vector>
     84 #include <string>
     85 #include <map>
     86 #include <set>
     87 #include <unordered_map>
     88 #include <random>
     89 #include <chrono>
     90 #include <cassert>
     91 #include <numeric>
     92 #include <bitset>
     93 #include <iomanip>
     94 #include <queue>
     95 #include <unordered_set>
     96 #include <fstream>
     97 #include <random>
     98 
     99 using namespace std;
    100 
    101 using ll = long long;
    102 
    103 mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
    104 const int MAXN = 500;
    105 int sum[MAXN + 1][MAXN + 1];
    106 
    107 int n, m, k;
    108 int check(int i, int mx) {
    109 	return min(max(i, 0), mx);
    110 }
    111 
    112 int pref(int i, int j) {
    113 	return sum[check(i, n)][check(j, m)];
    114 }
    115 
    116 void solve() {
    117 	cin >> n >> m >> k; k--;
    118 	vector<string> mine(n);
    119 	int all_gold = 0;
    120 	for (int i = 0; i < n; i++) {
    121 		cin >> mine[i];
    122 		for (int j = 0; j < m; j++) {
    123 			all_gold += (mine[i][j] == 'g');
    124 		}
    125 	}
    126 	for (int i = 0; i < n; i++) {
    127 		for (int j = 0; j < m; j++) {
    128 			sum[i + 1][j + 1] = sum[i + 1][j] + sum[i][j + 1] - sum[i][j] + (mine[i][j] == 'g');
    129 		}
    130 	}
    131 	int ans = all_gold;
    132 	for (int i = 0; i < n; i++) {
    133 		for (int j = 0; j < m; j++) {
    134 			if (mine[i][j] == '.') {
    135 				int a = i - k, b = i + k + 1, c = j - k, d = j + k + 1;
    136 				ans = min(ans, pref(b, d) - pref(a, d) - pref(b, c) + pref(a, c));
    137 			}
    138 		}
    139 	}
    140 	cout << all_gold - ans << "\n";
    141 }
    142 
    143 int main() {
    144 	ios_base::sync_with_stdio(false); cin.tie(0);
    145 	int t = 1;
    146 	cin >> t;
    147 	while (t--) {
    148 		solve();
    149 	}
    150 }
    151 ```
    152 
    153 [2113D - Cheater](/contest/2113/problem/D "Codeforces Round 1031 (Div. 2)")
    154 
    155 **Tutorial**
    156 
    157 Tutorial is loading...
    158 
    159 **Code**
    160 
    161 ```
    162 #include <bits/stdc++.h>
    163 
    164 using namespace std;
    165 
    166 #define sz(x) (int) ((x).size())
    167 #define all(x) (x).begin(), (x).end()
    168 #define rall(x) (x).rbegin(), (x).rend()
    169 
    170 typedef long long ll;
    171 typedef long double ld;
    172 typedef pair<int, int> pii;
    173 typedef pair<ll, ll> pll;
    174 
    175 const char en = '\n';
    176 const int INF = 1e9 + 7;
    177 const ll INFLL = 1e18;
    178 
    179 mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
    180 
    181 #ifdef LOCAL
    182 #include "debug.h"
    183 #define numtest(x) cerr << "Test #" << (x) << ": " << endl;
    184 #else
    185 #define debug(...) 42
    186 #define numtest(x) 42
    187 #endif
    188 
    189 int merge(const vector<int> &a, const vector<int> &b) {
    190     int n = sz(a);
    191     int res = 0;
    192     for (int c = 0, i = 0, j = 0; c < n; ++c) {
    193         if (a[i] > b[j]) {
    194             ++res;
    195             ++i;
    196         } else if (a[i] < b[j]) {
    197             ++j;
    198         } else {
    199             assert(0);
    200         }
    201     }
    202     return res;
    203 }
    204 
    205 void solve() {
    206     int n;
    207     cin >> n;
    208     vector<int> a(n), b(n);
    209     for (int i = 0; i < n; ++i) {
    210         cin >> a[i];
    211     }
    212     for (int i = 0; i < n; ++i) {
    213         cin >> b[i];
    214     }
    215     vector<int> pref_min(n), suf_max(n);
    216     pref_min[0] = 0;
    217     for (int i = 1; i < n; ++i) {
    218         pref_min[i] = pref_min[i - 1];
    219         if (a[i] < a[pref_min[i - 1]]) {
    220             pref_min[i] = i;
    221         }
    222     }
    223     suf_max[n - 1] = n - 1;
    224     for (int i = n - 2; i >= 0; --i) {
    225         suf_max[i] = suf_max[i + 1];
    226         if (a[i] > a[suf_max[i + 1]]) {
    227             suf_max[i] = i;
    228         }
    229     }
    230     int cur = merge(a, b);
    231     int l = cur, r = n;
    232     while (r - l > 1) {
    233         int m = l + (r - l) / 2;
    234         swap(a[pref_min[m - 1]], a[suf_max[m]]);
    235         if (merge(a, b) >= m) {
    236             l = m;
    237         } else {
    238             r = m;
    239         }
    240         swap(a[pref_min[m - 1]], a[suf_max[m]]);
    241     }
    242     cout << l << en;
    243 }
    244 
    245 int32_t main() {
    246     int tests = 1;
    247 #ifdef LOCAL
    248     freopen("input.txt", "r", stdin);
    249     tests = 1;
    250 #else
    251     ios_base::sync_with_stdio(0);
    252     cin.tie(0);
    253 #endif
    254     cin >> tests;
    255     for (int testcase = 1; testcase <= tests; ++testcase) {
    256         solve();
    257     }
    258     return 0;
    259 }
    260 ```
    261 
    262 [2113E - From Kazan with Love](/contest/2113/problem/E "Codeforces Round 1031 (Div. 2)")
    263 
    264 **Tutorial**
    265 
    266 Tutorial is loading...
    267 
    268 **Code**
    269 
    270 ```
    271 //#pragma GCC optimize("Ofast")
    272 
    273 #include "bits/stdc++.h"
    274 
    275 #define rep(i, n) for (int i = 0; i < (n); ++i)
    276 #define rep1(i, n) for (int i = 1; i < (n); ++i)
    277 #define rep1n(i, n) for (int i = 1; i <= (n); ++i)
    278 #define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
    279 //#define pb push_back
    280 #define eb emplace_back
    281 #define all(a) (a).begin(), (a).end()
    282 #define rall(a) (a).rbegin(), (a).rend()
    283 #define each(x, a) for (auto &x : a)
    284 #define ar array
    285 #define vec vector
    286 #define range(i, n) rep(i, n)
    287 
    288 using namespace std;
    289 
    290 using ll = long long;
    291 using ull = unsigned long long;
    292 using ld = double;
    293 using str = string;
    294 using pi = pair<int, int>;
    295 using pl = pair<ll, ll>;
    296 
    297 using vi = vector<int>;
    298 using vl = vector<ll>;
    299 using vpi = vector<pair<int, int>>;
    300 using vvi = vector<vi>;
    301 
    302 int Bit(int mask, int b) { return (mask >> b) & 1; }
    303 
    304 template<class T>
    305 bool ckmin(T &a, const T &b) {
    306     if (b < a) {
    307         a = b;
    308         return true;
    309     }
    310     return false;
    311 }
    312 
    313 template<class T>
    314 bool ckmax(T &a, const T &b) {
    315     if (b > a) {
    316         a = b;
    317         return true;
    318     }
    319     return false;
    320 }
    321 
    322 // [l, r)
    323 template<typename T, typename F>
    324 T FindFirstTrue(T l, T r, const F &predicat) {
    325     --l;
    326     while (r - l > 1) {
    327         T mid = l + (r - l) / 2;
    328         if (predicat(mid)) {
    329             r = mid;
    330         } else {
    331             l = mid;
    332         }
    333     }
    334     return r;
    335 }
    336 
    337 template<typename T, typename F>
    338 T FindLastFalse(T l, T r, const F &predicat) {
    339     return FindFirstTrue(l, r, predicat) - 1;
    340 }
    341 
    342 const int INFi = 2e9;
    343 const ll INF = 2e18;
    344 
    345 void solve() {
    346     int n, m, x, y; cin >> n >> m >> x >> y;
    347     x--;
    348     y--;
    349     vvi g(n);
    350     rep(_, n - 1) {
    351         int u, v; cin >> u >> v;
    352         u--;
    353         v--;
    354         g[u].push_back(v);
    355         g[v].push_back(u);
    356     }
    357 
    358     vector<vi> block;
    359 
    360     vi path;
    361     auto dfs = [&] (auto &&self, int v, int p, int t) -> bool {
    362         path.push_back(v);
    363         if (v == t) return true;
    364         for(auto &u : g[v]) {
    365             if (u == p) continue;
    366             if (self(self, u, v, t)) return true;
    367         }
    368         path.pop_back();
    369         return false;
    370     };
    371 
    372     rep(i, m) {
    373         int a, b; cin >> a >> b;
    374         a--;
    375         b--;
    376 
    377         dfs(dfs, a, -1, b);
    378         assert(!path.empty());
    379 
    380         if (block.size() < path.size()) block.resize(path.size());
    381 
    382         rep(j, path.size()) block[j].push_back(path[j]);
    383         path.clear();
    384     }
    385 
    386     vector<bool> ok(n, false);
    387     vi q;
    388     q.push_back(x);
    389 
    390     vector<bool> cur(n, false);
    391     vi was(n, -1);
    392     for(int t = 0;;++t) {
    393 
    394         if (t < block.size()) for(auto &u : block[t]) cur[u] = true;
    395         vi nxt;
    396         for(auto &v : q) {
    397             if (ok[v] || cur[v] || was[v] == t) continue;
    398             was[v] = t;
    399             bool nei = 0;
    400             for(auto &u : g[v]) nei |= ok[u];
    401             if (t && !nei) continue;
    402             nxt.push_back(v);
    403         }
    404 
    405         q.clear();
    406         if (t < block.size()) {
    407             for(auto &u : block[t]) {
    408                 cur[u] = false;
    409                 if (ok[u]) {
    410                     ok[u] = false;
    411                 }
    412                 q.push_back(u);
    413             }
    414         }
    415 
    416         for(auto &v : nxt) {
    417             assert(!ok[v]);
    418             ok[v] = true;
    419             for(auto &u : g[v]) {
    420                 if (!ok[u]) {
    421                     q.push_back(u);
    422                 }
    423             }
    424         }
    425 
    426         if (ok[y]) {
    427             cout << t + 1 << '\n';
    428             return;
    429         }
    430 
    431         if (t > (int)block.size() && q.empty()) {
    432             cout << "-1\n";
    433             return;
    434         }
    435     }
    436 }
    437 
    438 signed main() {
    439     ios_base::sync_with_stdio(false);
    440     cin.tie(0);
    441     cout << setprecision(12) << fixed;
    442     int t = 1;
    443     cin >> t;
    444     rep(_, t) {
    445         solve();
    446     }
    447 
    448     return 0;
    449 }
    450 ```
    451 
    452 [2113F - Two Arrays](/contest/2113/problem/F "Codeforces Round 1031 (Div. 2)")
    453 
    454 **Tutorial**
    455 
    456 Tutorial is loading...
    457 
    458 **Code**
    459 
    460 ```
    461 #include "bits/stdc++.h"
    462  
    463 using namespace std;
    464  
    465 void solve() {
    466     int n;
    467     cin >> n;
    468     vector<int> a(n);
    469     for (int i = 0; i < n; i++) {
    470         cin >> a[i];
    471     }
    472     vector<int> b(n);
    473     for (int i = 0; i < n; i++) {
    474         cin >> b[i];
    475     }
    476     vector<int> want(n);
    477     auto make = [&] (int i, int x, int y) {
    478         if (!want[i]) {
    479             if (a[i] != x) {
    480                 swap(a[i], b[i]);
    481             }
    482             want[i] = 1;
    483         }
    484     };
    485     const int N = 2 * n + 22;
    486     vector<vector<pair<int, int>>> g(N);
    487     for (int i = 0; i < n; i++) {
    488         g[a[i]].push_back({b[i], i});
    489         g[b[i]].push_back({a[i], i});
    490     }
    491     vector<int> used(N);
    492     auto dfs = [&] (auto&& dfs, int v, int h) -> void {
    493         used[v] = h;
    494         for (auto& [u, i] : g[v]) {
    495             if (used[u] <= 0) {
    496                 make(i, v, u);
    497                 dfs(dfs, u, h + 1);
    498             } else if (used[u] < used[v]) {
    499                 make(i, v, u);
    500             }
    501         }
    502     };
    503     for (int i = 0; i < N; i++) {
    504         if (used[i] == 0 && int(g[i].size()) == 1) {
    505             dfs(dfs, i, 1);
    506         }
    507     }
    508     int rt;
    509     auto find = [&] (auto&& find, int v, int pr) -> void {
    510         used[v] = -1;
    511         for (auto& [u, i] : g[v]) {
    512             if (used[u] == 0) {
    513                 find(find, u, i);
    514             } else if (i != pr) {
    515                 rt = u;
    516             }
    517         }
    518     };
    519     for (int i = 0; i < N; i++) {
    520         if (used[i] == 0 && !g[i].empty()) {
    521             rt = -1;
    522             find(find, i, -1);
    523             dfs(dfs, rt, 1);
    524         }
    525     }
    526     cout << set<int>(a.begin(), a.end()).size() + set<int>(b.begin(), b.end()).size() << '\n';
    527     for (int i = 0; i < n; i++) {
    528         cout << a[i] << " ";
    529     }
    530     cout << '\n';
    531     for (int i = 0; i < n; i++) {
    532         cout << b[i] << " ";
    533     }
    534     cout << '\n';
    535 }
    536  
    537 int main() {
    538     ios_base::sync_with_stdio(0);
    539     cin.tie(0);
    540     cout.tie(0);
    541     int t;
    542     cin >> t;
    543     while (t--) {
    544         solve();
    545     }
    546 }
    547 ```