1851.md (9732B)
1 Source: https://codeforces.com/blog/entry/118667 2 3 [1851A - Escalator Conversations](/contest/1851/problem/A "Codeforces Round 888 (Div. 3)") 4 5 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Aris](/profile/Aris "Candidate Master Aris") 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 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 #define sz(v) (int)v.size() 20 #define all(v) v.begin(),v.end() 21 #define eb emplace_back 22 23 void solve() { 24 int n,m,k,H; cin >> n >> m >> k >> H; 25 int ans = 0; 26 forn(i, n) { 27 int x; cin >> x; 28 ans += (H != x) && abs(H - x) % k == 0 && abs(H-x) <= (m-1) * k; 29 } 30 cout << ans << endl; 31 } 32 33 int main() { 34 int t; 35 cin >> t; 36 37 forn(tt, t) { 38 solve(); 39 } 40 } 41 ``` 42 43 [1851B - Parity Sort](/contest/1851/problem/B "Codeforces Round 888 (Div. 3)") 44 45 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [myav](/profile/myav "Pupil myav") 46 47 **Tutorial** 48 49 Tutorial is loading... 50 51 **Solution** 52 53 ``` 54 #include<bits/stdc++.h> 55 using namespace std; 56 57 bool solve(){ 58 int n; 59 cin >> n; 60 vector<int>a(n), b(n); 61 for(int i = 0; i < n; i++){ 62 cin >> a[i]; 63 b[i] = a[i]; 64 } 65 sort(b.begin(), b.end()); 66 for(int i = 0; i < n; i++){ 67 if((a[i] % 2) != (b[i] % 2)) return false; 68 } 69 return true; 70 71 } 72 73 int main(){ 74 int t; 75 cin >> t; 76 while(t--){ 77 cout << (solve() ? "YES" : "NO") << "\n"; 78 } 79 return 0; 80 } 81 ``` 82 83 [1851C - Tiles Comeback](/contest/1851/problem/C "Codeforces Round 888 (Div. 3)") 84 85 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [myav](/profile/myav "Pupil myav") 86 87 **Tutorial** 88 89 Tutorial is loading... 90 91 **Solution** 92 93 ``` 94 #include "bits/stdc++.h" 95 using namespace std; 96 97 bool solve(){ 98 int n, k; 99 cin >> n >> k; 100 vector<int>c(n); 101 for(int i = 0; i < n; i++) cin >> c[i]; 102 int left = 0, right = 0, i = 0, j = n - 1; 103 int k_left = k, k_right = k; 104 105 if (c[0] == c[n - 1]){ 106 k_left = k / 2; 107 k_right = k - k_left; 108 } 109 for(; i < n && left < k_left; i++){ 110 if(c[i] == c[0]) left++; 111 } 112 for(; j >= 0 && right < k_right; j--){ 113 if(c[j] == c[n - 1]) right++; 114 } 115 return (i - 1) < (j + 1); 116 } 117 118 int main(){ 119 int t; 120 cin >> t; 121 while(t--){ 122 cout << (solve() ? "YES" : "NO") << "\n"; 123 } 124 125 } 126 ``` 127 128 [1851D - Prefix Permutation Sums](/contest/1851/problem/D "Codeforces Round 888 (Div. 3)") 129 130 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 131 132 **Tutorial** 133 134 Tutorial is loading... 135 136 **Solution** 137 138 ``` 139 #include <iostream> 140 #include <vector> 141 #include <set> 142 #include <map> 143 144 using namespace std; 145 146 typedef long long ll; 147 148 ll n; 149 150 bool isPermutation(vector<ll> a) { 151 for (int i = 0; i < n; ++i) { 152 if (a[i] <= 0 || a[i] > n) { 153 return false; 154 } 155 } 156 set<ll> s(a.begin(), a.end()); 157 return s.size() == n; 158 } 159 160 vector<ll> prefSumToArray(vector<ll> p) { 161 vector<ll> res(n); 162 res[0] = p[0]; 163 for (int i = 1; i < n; ++i) { 164 res[i] = p[i] - p[i - 1]; 165 } 166 return res; 167 } 168 169 void solve() { 170 cin >> n; 171 vector<ll> a(n - 1); 172 for (int i = 0; i + 1 < n; ++i) { 173 cin >> a[i]; 174 } 175 ll x = n * (n + 1) / 2; 176 if (a.back() != x) { 177 a.push_back(x); 178 vector<ll> b = prefSumToArray(a); 179 if (isPermutation(b)) { 180 cout << "YES\n"; 181 } else { 182 cout << "NO\n"; 183 } 184 return; 185 } 186 map<ll, int> cnt; 187 cnt[a[0]]++; 188 for (int i = 1; i < n - 1; ++i) { 189 cnt[a[i] - a[i - 1]]++; 190 } 191 vector<int> cntGt1; 192 for (auto p: cnt) { 193 if (p.second > 1) { 194 cntGt1.push_back(p.first); 195 } 196 } 197 if (cntGt1.size() > 1) { 198 cout << "NO\n"; 199 return; 200 } 201 if (cntGt1.size() == 1) { 202 int x1 = cntGt1[0]; 203 if (cnt[x1] > 2) { 204 cout << "NO\n"; 205 return; 206 } 207 } 208 vector<int> cnt0; 209 for (int i = 1; i <= n; ++i) { 210 if (cnt[i] == 0) { 211 cnt0.push_back(i); 212 } 213 } 214 if (cnt0.size() != 2) { 215 cout << "NO\n"; 216 return; 217 } 218 cout << "YES\n"; 219 } 220 221 int main() { 222 ios_base::sync_with_stdio(0); 223 cin.tie(0), cout.tie(0); 224 int t; 225 cin >> t; 226 for (int _ = 0; _ < t; ++_) { 227 solve(); 228 } 229 return 0; 230 } 231 ``` 232 233 [1851E - Nastya and Potions](/contest/1851/problem/E "Codeforces Round 888 (Div. 3)") 234 235 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 236 237 **Tutorial** 238 239 Tutorial is loading... 240 241 **Solution** 242 243 ``` 244 #include <bits/stdc++.h> 245 246 #define int long long 247 248 using namespace std; 249 250 vector<int> dp; 251 vector<bool> used; 252 vector<vector<int>> sl; 253 254 int get(int v){ 255 if(used[v]){ 256 return dp[v]; 257 } 258 used[v] = true; 259 int s = 0; 260 for(int u: sl[v]){ 261 s += get(u); 262 } 263 if(!sl[v].empty()) dp[v] = min(dp[v], s); 264 return dp[v]; 265 } 266 267 void solve(int tc) { 268 int n, k; 269 cin >> n >> k; 270 dp.resize(n); 271 used.assign(n, false); 272 sl.assign(n, vector<int>(0)); 273 for(int &e: dp) cin >> e; 274 for(int i = 0; i < k; ++i){ 275 int e; 276 cin >> e; 277 dp[--e] = 0; 278 } 279 for(int i = 0; i < n; ++i){ 280 int m; 281 cin >> m; 282 sl[i].resize(m); 283 for(int &e: sl[i]){ 284 cin >> e; 285 --e; 286 } 287 } 288 for(int i = 0; i < n; ++i){ 289 get(i); 290 } 291 for(int e: dp) cout << e << " "; 292 } 293 294 bool multi = true; 295 296 signed main() { 297 int t = 1; 298 if(multi) cin >> t; 299 for (int i = 1; i <= t; ++i) { 300 solve(i); 301 cout << "\n"; 302 } 303 return 0; 304 } 305 ``` 306 307 [1851F - Lisa and the Martians](/contest/1851/problem/F "Codeforces Round 888 (Div. 3)") 308 309 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40"), prepared: [Gornak40](/profile/Gornak40 "Expert Gornak40") 310 311 **Tutorial** 312 313 Tutorial is loading... 314 315 **Solution** 316 317 ``` 318 #include <bits/stdc++.h> 319 #define all(arr) arr.begin(), arr.end() 320 321 using namespace std; 322 323 const int MAXN = 200200; 324 const int MAXK = 30; 325 const int MAXMEM = MAXN * MAXK; 326 327 mt19937 rng(07062006); 328 329 struct node { 330 node *chi[2] {nullptr}; 331 int sz = 0, id = -1; 332 }; 333 334 int n, k; 335 int arr[MAXN]; 336 node *mem = new node[MAXMEM]; 337 node *root, *mpos; 338 339 void add_num(node* &v, int val, int i, int id) { 340 if (v == nullptr) *(v = mpos++) = node(); 341 v->sz++; 342 if (i == -1) { 343 v->id = id; 344 return; 345 } 346 add_num(v->chi[val >> i & 1], val, i - 1, id); 347 } 348 349 int down(node *v, int val, int i, int &x, int &jans) { 350 if (i == -1) { 351 jans = v->id; 352 return 0; 353 } 354 int b = val >> i & 1; 355 if (v->chi[b]) 356 return down(v->chi[b], val, i - 1, x ^= ((1 ^ b) << i), jans) | (1 << i); 357 return down(v->chi[b ^ 1], val, i - 1, x ^= ((rng() & 1) << i), jans); 358 } 359 360 void build() { 361 root = nullptr; 362 mpos = mem; 363 add_num(root, *arr, k - 1, 0); 364 } 365 366 tuple<int, int, int> solve() { 367 int ians = 0, jans = 1, xans = 0; 368 for (int i = 1; i < n; ++i) { 369 int x = 0, j = -1; 370 int cur = down(root, arr[i], k - 1, x, j); 371 if (cur > ((arr[ians] ^ xans) & (arr[jans] ^ xans))) 372 ians = j, jans = i, xans = x; 373 add_num(root, arr[i], k - 1, i); 374 } 375 return {ians, jans, xans}; 376 } 377 378 int main() { 379 int t; cin >> t; 380 while (t--) { 381 cin >> n >> k; 382 for (int i = 0; i < n; ++i) 383 cin >> arr[i]; 384 build(); 385 auto [ians, jans, xans] = solve(); 386 cout << ++ians << ' ' << ++jans << ' ' << xans << endl; 387 } 388 } 389 ``` 390 391 [1851G - Vlad and the Mountains](/contest/1851/problem/G "Codeforces Round 888 (Div. 3)") 392 393 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya"), prepared: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 394 395 **Tutorial** 396 397 Tutorial is loading... 398 399 **Solution** 400 401 ``` 402 #include <bits/stdc++.h> 403 404 #define x first 405 #define y second 406 #define all(a) a.begin(), a.end() 407 #define rall(a) a.rbegin(), a.rend() 408 409 typedef long double ld; 410 typedef long long ll; 411 412 using namespace std; 413 414 struct dsu{ 415 vector<int> p, lvl; 416 417 dsu(int n){ 418 p.resize(n); 419 lvl.assign(n, 0); 420 iota(all(p), 0); 421 } 422 423 int get(int i){ 424 if(i == p[i]) return i; 425 return p[i] = get(p[i]); 426 } 427 428 bool unite(int a, int b){ 429 a = get(a); 430 b = get(b); 431 if(a == b){ 432 return false; 433 } 434 if(lvl[a] < lvl[b])swap(a, b); 435 p[b] = a; 436 if(lvl[a] == lvl[b]){ 437 ++lvl[a]; 438 } 439 return true; 440 } 441 442 bool reachable(int a, int b){ 443 return get(a) == get(b); 444 } 445 }; 446 447 void solve(int tc) { 448 int n, m; 449 cin >> n >> m; 450 vector<pair<int, int>> h(n); 451 for(auto &e: h) cin >> e.x; 452 for(int i = 0; i < n; ++i){ 453 h[i].y = i; 454 } 455 dsu graph(n); 456 vector<vector<int>> sl(n); 457 for(int i = 0; i < m; ++i){ 458 int u, v; 459 cin >> u >> v; 460 --u, --v; 461 if(h[u].x > h[v].x) sl[u].emplace_back(v); 462 else sl[v].emplace_back(u); 463 } 464 int q; 465 cin >> q; 466 vector<pair<pair<int, int>, pair<int, int>>> req(q); 467 for(auto &e: req){ 468 cin >> e.y.x >> e.y.y >> e.x.x; 469 --e.y.x, --e.y.y; 470 e.x.x += h[e.y.x].x; 471 } 472 for(int i = 0; i < q; ++i){ 473 req[i].x.y = i; 474 } 475 476 sort(all(h)); 477 sort(all(req)); 478 vector<bool> ans(q); 479 int j = 0; 480 for(auto e: req){ 481 while (j < n && h[j].x <= e.x.x) { 482 for(int u: sl[h[j].y]){ 483 graph.unite(h[j].y, u); 484 } 485 ++j; 486 } 487 ans[e.x.y] = graph.reachable(e.y.x, e.y.y); 488 } 489 for(bool e: ans) cout << (e? "YES": "NO") << "\n"; 490 } 491 492 bool multi = true; 493 494 signed main() { 495 int t = 1; 496 if(multi) cin >> t; 497 for (int i = 1; i <= t; ++i) { 498 solve(i); 499 if(i < t) cout << "\n"; 500 } 501 return 0; 502 } 503 ```