1611.md (10459B)
1 Source: https://codeforces.com/blog/entry/97288 2 3 [1611A - Make Even](/contest/1611/problem/A "Codeforces Round 756 (Div. 3)") 4 5 Idea: [MisterGu](/profile/MisterGu "Unrated, MisterGu") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include<bits/stdc++.h> 15 16 using namespace std; 17 18 int main() { 19 int t; 20 cin >> t; 21 while(t--) { 22 string n; 23 cin >> n; 24 if((n.back() - '0') % 2 == 0) { 25 cout << "0\n"; 26 continue; 27 } 28 if((n[0] - '0') % 2 == 0) { 29 cout << "1\n"; 30 continue; 31 } 32 int count_2 = count(n.begin(), n.end(), '2'); 33 int count_4 = count(n.begin(), n.end(), '4'); 34 int count_6 = count(n.begin(), n.end(), '6'); 35 int count_8 = count(n.begin(), n.end(), '8'); 36 if(count_2 > 0 || count_4 > 0 || count_6 > 0 || count_8 > 0) { 37 cout << "2\n"; 38 continue; 39 } 40 cout << "-1\n"; 41 } 42 return 0; 43 } 44 ``` 45 46 [1611B - Team Composition: Programmers and Mathematicians](/contest/1611/problem/B "Codeforces Round 756 (Div. 3)") 47 48 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 49 50 **Tutorial** 51 52 Tutorial is loading... 53 54 **Solution** 55 56 ``` 57 #include <bits/stdc++.h> 58 59 using namespace std; 60 using ll = long long; 61 62 void solve() { 63 ll a, b; 64 cin >> a >> b; 65 cout << min(min(a, b), (a + b) / 4) << '\n'; 66 } 67 68 int main() { 69 int t; 70 cin >> t; 71 for (int i = 0; i < t; ++i) { 72 solve(); 73 } 74 return 0; 75 } 76 ``` 77 78 [1611C - Polycarp Recovers the Permutation](/contest/1611/problem/C "Codeforces Round 756 (Div. 3)") 79 80 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 81 82 **Tutorial** 83 84 Tutorial is loading... 85 86 **Solution** 87 88 ``` 89 #include <bits/stdc++.h> 90 91 using namespace std; 92 93 #define forn(i, n) for (int i = 0; i < int(n); i++) 94 95 int main() { 96 int t; 97 cin >> t; 98 forn(tt, t) { 99 int n; 100 cin >> n; 101 vector<int> a(n); 102 forn(i, n) 103 cin >> a[i]; 104 if (a[0] != n && a[n - 1] != n) 105 cout << -1 << endl; 106 else { 107 for (int i = n - 1; i >= 0; i--) 108 cout << a[i] << " "; 109 cout << endl; 110 } 111 } 112 } 113 ``` 114 115 [1611D - Weights Assignment For Tree Edges](/contest/1611/problem/D "Codeforces Round 756 (Div. 3)") 116 117 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 118 119 **Tutorial** 120 121 Tutorial is loading... 122 123 **Solution** 124 125 ``` 126 #include <bits/stdc++.h> 127 128 using namespace std; 129 130 void solve(){ 131 int n; 132 cin >> n; 133 vector<int> b(n + 1), p(n + 1), dist(n + 1, -1); 134 135 for(int i = 1; i <= n; i++) 136 cin >> b[i]; 137 for(int i = 1; i <= n; i++) 138 cin >> p[i]; 139 140 if (b[p[1]] != p[1]){ 141 cout << -1 << '\n'; 142 return; 143 } 144 145 dist[p[1]] = 0; 146 for(int i = 2; i <= n; i++){ 147 if(dist[b[p[i]]] == -1){ 148 cout << -1 << '\n'; 149 return; 150 } 151 dist[p[i]] = dist[p[i - 1]] + 1; 152 } 153 154 for(int i = 1; i <= n; i++) { 155 cout << dist[i] - dist[b[i]] << ' '; 156 } 157 cout << '\n'; 158 } 159 160 int main() { 161 int t; 162 cin >> t; 163 while(t-- > 0) { 164 solve(); 165 } 166 } 167 ``` 168 169 [1611E1 - Escape The Maze (easy version)](/contest/1611/problem/E1 "Codeforces Round 756 (Div. 3)") 170 171 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 172 173 **Tutorial** 174 175 Tutorial is loading... 176 177 **Solution** 178 179 ``` 180 // 181 // Created by Vlad on 16.11.2021. 182 // 183 184 #include <bits/stdc++.h> 185 186 #define int long long 187 #define mp make_pair 188 #define x first 189 #define y second 190 #define all(a) (a).begin(), (a).end() 191 #define rall(a) (a).rbegin(), (a).rend() 192 193 typedef long double ld; 194 typedef long long ll; 195 196 using namespace std; 197 198 mt19937 rnd(143); 199 200 const int inf = 1e10; 201 const int M = 998244353; 202 const ld pi = atan2(0, -1); 203 const ld eps = 1e-4; 204 205 void solve() { 206 int n, k; 207 cin >> n >> k; 208 vector<int> color(n, -1); 209 deque<int> q; 210 for(int i = 0; i < k; ++i){ 211 int x; 212 cin >> x; 213 color[--x] = 0; 214 q.push_back(x); 215 } 216 color[0] = 1; 217 q.push_back(0); 218 vector<vector<int>> g(n); 219 for(int i = 0; i < n - 1; ++i){ 220 int u, v; 221 cin >> u >> v; 222 g[--u].push_back(--v); 223 g[v].push_back(u); 224 } 225 while(!q.empty()){ 226 int v = q.front(); 227 q.pop_front(); 228 for(int u: g[v]){ 229 if(color[u] == -1){ 230 color[u] = color[v]; 231 q.push_back(u); 232 } 233 } 234 } 235 for(int v = 1; v < n; ++v){ 236 if(g[v].size() == 1 && color[v] == 1){ 237 cout << "YES"; 238 return; 239 } 240 } 241 cout << "NO"; 242 } 243 244 bool multi = true; 245 246 signed main() { 247 int t = 1; 248 if (multi) { 249 cin >> t; 250 } 251 for (; t != 0; --t) { 252 solve(); 253 cout << "\n"; 254 } 255 return 0; 256 } 257 ``` 258 259 [1611E2 - Escape The Maze (hard version)](/contest/1611/problem/E2 "Codeforces Round 756 (Div. 3)") 260 261 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 262 263 **Tutorial** 264 265 Tutorial is loading... 266 267 **Solution** 268 269 ``` 270 #include <bits/stdc++.h> 271 272 #define int long long 273 #define mp make_pair 274 #define x first 275 #define y second 276 #define all(a) (a).begin(), (a).end() 277 #define rall(a) (a).rbegin(), (a).rend() 278 279 /*#pragma GCC optimize("Ofast") 280 #pragma GCC optimize("no-stack-protector") 281 #pragma GCC optimize("unroll-loops") 282 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 283 #pragma GCC optimize("fast-math") 284 */ 285 typedef long double ld; 286 typedef long long ll; 287 288 using namespace std; 289 290 mt19937 rnd(143); 291 292 const int inf = 1e10; 293 const int M = 998244353; 294 const ld pi = atan2(0, -1); 295 const ld eps = 1e-4; 296 297 vector<vector<int>> sl; 298 vector<int> nearest; 299 300 int count(int v, int dist, int p = -1){ 301 bool children = true; 302 int s = 0; 303 for(int u: sl[v]){ 304 if(u == p) continue; 305 int c = count(u, dist + 1, v); 306 if(c < 0) children = false; 307 nearest[v] = min(nearest[v], nearest[u] + 1); 308 s += c; 309 } 310 if(nearest[v] <= dist) return 1; 311 if(s == 0 || !children) return -1; 312 return s; 313 } 314 315 void solve() { 316 int n, k; 317 cin >> n >> k; 318 sl.assign(n, vector<int>(0)); 319 nearest.assign(n, n); 320 for(int i = 0; i < k; ++i){ 321 int x; 322 cin >> x; 323 --x; 324 nearest[x] = 0; 325 } 326 for(int i = 1; i < n; ++i){ 327 int u, v; 328 cin >> u >> v; 329 --u, --v; 330 sl[u].emplace_back(v); 331 sl[v].emplace_back(u); 332 } 333 cout << count(0, 0); 334 } 335 336 bool multi = true; 337 338 signed main() { 339 //freopen("in.txt", "r", stdin); 340 //freopen("in.txt", "w", stdout); 341 /*ios_base::sync_with_stdio(false); 342 cin.tie(nullptr); 343 cout.tie(nullptr);*/ 344 int t = 1; 345 if (multi) { 346 cin >> t; 347 } 348 for (; t != 0; --t) { 349 solve(); 350 cout << "\n"; 351 } 352 return 0; 353 } 354 ``` 355 356 [1611F - ATM and Students](/contest/1611/problem/F "Codeforces Round 756 (Div. 3)") 357 358 Idea: [Gol_D](/profile/Gol_D "Candidate Master Gol_D"), [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 359 360 **Tutorial** 361 362 Tutorial is loading... 363 364 **Solution** 365 366 ``` 367 #include <bits/stdc++.h> 368 369 using namespace std; 370 371 typedef long long ll; 372 373 #define forn(i, n) for (int i = 0; i < int(n); i++) 374 375 vector<ll> t, a; 376 ll s, tl; 377 378 const ll MAX = 1'000'000'000'000'000LL; 379 380 void build(int v, int l, int r) { 381 if (l == r) 382 t[v] = a[l]; 383 else { 384 int m = (l + r) / 2; 385 build (v * 2, l, m); 386 build (v * 2 + 1, m + 1, r); 387 t[v] = min(t[v * 2], t[v * 2 + 1]); 388 } 389 } 390 391 void update(int v, int l, int r) { 392 if (l == r) 393 t[v] = MAX; 394 else { 395 int m = (l + r) / 2; 396 if (tl <= m) 397 update(v * 2, l, m); 398 else 399 update(v * 2 + 1, m + 1, r); 400 t[v] = min(t[v * 2], t[v * 2 + 1]); 401 } 402 } 403 404 int lower_bound_s(int v, int l, int r) { 405 if (r < tl || (l == r && s < -t[v])) { 406 return -1; 407 } 408 if (l == r || -t[v] <= s) { 409 return r; 410 } 411 int m = (l + r) / 2; 412 413 if (m < tl) { 414 return lower_bound_s(2 * v + 1, m + 1, r); 415 } 416 if (s < -t[2 * v]) { 417 return lower_bound_s(2 * v, l, m); 418 } 419 int res = lower_bound_s(2 * v + 1, m + 1, r); 420 return (res == -1) ? m : res; 421 } 422 423 int main() { 424 int tests; 425 cin >> tests; 426 forn(tt, tests) { 427 int n; 428 cin >> n >> s; 429 t = vector<ll>(4 * n); 430 a = vector<ll>(n); 431 forn(i, n) { 432 cin >> a[i]; 433 } 434 for (int i = 1; i < n; ++i) { 435 a[i] += a[i - 1]; 436 } 437 build(1, 0, n - 1); 438 int first = -1, second = -2; 439 for (tl = 0; tl < n; ++tl) { 440 int v = lower_bound_s(1, 0, n - 1); 441 if (v != -1 && v - tl > second - first) { 442 first = tl + 1; 443 second = v + 1; 444 } 445 s -= a[tl]; 446 if (tl != 0) s += a[tl - 1]; 447 update(1, 0, n - 1); 448 } 449 if (first == -1) { 450 cout << -1; 451 } else { 452 cout << first << " " << second; 453 } 454 cout << endl; 455 } 456 } 457 ``` 458 459 [1611G - Robot and Candies](/contest/1611/problem/G "Codeforces Round 756 (Div. 3)") 460 461 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 462 463 **Tutorial** 464 465 Tutorial is loading... 466 467 **Solution** 468 469 ``` 470 #include <bits/stdc++.h> 471 472 using namespace std; 473 474 #define forn(i, n) for (int i = 0; i < int(n); i++) 475 #define sz(v) (int)v.size() 476 477 const int N = 1e6 + 50; 478 string a[N]; 479 480 int n,m; 481 int ans; 482 483 void solve(int sum0) { 484 vector<int> v; 485 for (int sum = sum0, ad = 0, pref = 0; sum < n + m; sum += 2, ad++) { 486 vector<int> cur; 487 int li = max(0, sum - m + 1), ri = min(n - 1, sum); 488 if (li > ri) continue; 489 490 for (int i = li; i <= ri; i++) { 491 int j = sum - i; 492 493 if (a[i][j] == '1') 494 cur.emplace_back(i); 495 } 496 497 while (pref != sz(v) && v[pref] + ad > ri) { 498 pref++; 499 } 500 for (int i = pref; i < sz(v); i++) { 501 int new_val = v[i]; 502 while (!cur.empty() && cur.back() - ad >= v[i]) { 503 new_val = max(new_val, cur.back() - ad); 504 cur.pop_back(); 505 } 506 v[i] = new_val; 507 } 508 if (!cur.empty()) { 509 v.emplace_back(cur.back() - ad); 510 ans++; 511 } 512 } 513 } 514 515 int main() { 516 int t; 517 cin >> t; 518 519 forn(tt, t) { 520 cin >> n >> m; 521 522 forn(i, n) { 523 string s; 524 cin >> a[i]; 525 } 526 527 ans = 0; 528 solve(0); 529 solve(1); 530 531 cout << ans << '\n'; 532 } 533 } 534 ```