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