2242.md (10381B)
1 Source: https://codeforces.com/blog/entry/155047 2 3 [2242A - Bigrams](/contest/2242/problem/A "Educational Codeforces Round 192 (Rated for Div. 2)") 4 5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (BledDest)** 12 13 ``` 14 t = int(input()) 15 for i in range(t): 16 k = int(input()) 17 a = list(map(int, input().split())) 18 if max(a) > 2 or a.count(2) > 1: 19 print('YES') 20 else: 21 print('NO') 22 ``` 23 24 [2242B - Predominant Frequency Division](/contest/2242/problem/B "Educational Codeforces Round 192 (Rated for Div. 2)") 25 26 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (FelixArg)** 33 34 ``` 35 #include <bits/stdc++.h> 36 37 using namespace std; 38 39 const int INF = 1'000'000'007; 40 41 void solve() { 42 int n; 43 cin >> n; 44 vector<int> a(n); 45 for (int i = 0; i < n; i++){ 46 cin >> a[i]; 47 } 48 49 vector<int> pref1(n + 1); 50 vector<int> pref2(n + 1); 51 for (int i = 0; i < n; i++){ 52 pref1[i + 1] = pref1[i] + (a[i] == 1 ? 1 : -1); 53 pref2[i + 1] = pref2[i] + (a[i] == 3 ? -1 : 1); 54 } 55 56 int mn = INF; 57 for (int i = 1; i < n; i++){ 58 if (pref2[i] - mn >= 0){ 59 cout << "YES\n"; 60 return; 61 } 62 if (pref1[i] >= 0){ 63 mn = min(mn, pref2[i]); 64 } 65 } 66 67 cout << "NO\n"; 68 } 69 70 71 signed main() 72 { 73 #ifdef FELIX 74 auto _clock_start = chrono::high_resolution_clock::now(); 75 #endif 76 ios_base::sync_with_stdio(false); 77 cin.tie(0); 78 cout.tie(0); 79 80 int tests = 1; 81 cin >> tests; 82 while(tests--){ 83 solve(); 84 } 85 86 #ifdef FELIX 87 cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>( 88 chrono::high_resolution_clock::now() 89 - _clock_start).count() << "ms." << endl; 90 #endif 91 return 0; 92 } 93 ``` 94 95 [2242C - Unstable Elements](/contest/2242/problem/C "Educational Codeforces Round 192 (Rated for Div. 2)") 96 97 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 98 99 **Tutorial** 100 101 Tutorial is loading... 102 103 **Solution (BledDest)** 104 105 ``` 106 #include <bits/stdc++.h> 107 108 using namespace std; 109 110 void solve() 111 { 112 int n, k; 113 cin >> n >> k; 114 115 vector<int> a(n); 116 for (int i = 0; i < n; i++) 117 { 118 cin >> a[i]; 119 } 120 121 vector<int> lens; 122 123 int cur = 1; 124 for (int i = 1; i < n; i++) 125 if (a[i] != a[i - 1]) 126 { 127 lens.push_back(cur); 128 cur = 1; 129 } 130 else cur++; 131 lens.push_back(cur); 132 sort(lens.begin(), lens.end()); 133 134 int m = (int)lens.size(); 135 int d = 0; 136 137 int ans = 0; 138 int i = 0; 139 while(i < m) 140 { 141 int len = lens[i]; 142 int x = len - 1; 143 int q = m - i; 144 int curLen = n - d - x * q; 145 if (curLen <= k && (k - curLen) % q == 0) 146 ans++; 147 148 int j = i; 149 while (j < m && lens[j] == len) 150 j++; 151 d += (j - i) * lens[i]; 152 i = j; 153 } 154 155 cout << ans << '\n'; 156 } 157 158 int main() 159 { 160 ios_base::sync_with_stdio(0); 161 cin.tie(0); 162 int t; 163 cin >> t; 164 for(int i = 0; i < t; i++) 165 solve(); 166 return 0; 167 } 168 ``` 169 170 [2242D - Two Digit Strings](/contest/2242/problem/D "Educational Codeforces Round 192 (Rated for Div. 2)") 171 172 Idea: [Roms](/profile/Roms "Master Roms") 173 174 **Tutorial** 175 176 Tutorial is loading... 177 178 **Solution (BledDest)** 179 180 ``` 181 #include<bits/stdc++.h> 182 183 using namespace std; 184 185 const int MOD = 998244353; 186 187 void upd(int& x, int y) 188 { 189 if(x < y) x = y; 190 } 191 192 void solve() 193 { 194 string s, t; 195 cin >> s >> t; 196 int n = s.size(); 197 int m = t.size(); 198 vector<int> ps(n + 1), pt(m + 1); 199 for(int i = 0; i < n; i++) 200 ps[i + 1] = (ps[i] + (s[i] - '0')) % 10; 201 for(int i = 0; i < m; i++) 202 pt[i + 1] = (pt[i] + (t[i] - '0')) % 10; 203 n++; 204 m++; 205 if(ps.back() != pt.back()) 206 { 207 cout << -1 << "\n"; 208 return; 209 } 210 211 vector<vector<int>> dp(n + 1, vector<int>(m + 1)); 212 for(int i = 0; i <= n; i++) 213 for(int j = 0; j <= m; j++) 214 { 215 if(i < n) upd(dp[i + 1][j], dp[i][j]); 216 if(j < m) upd(dp[i][j + 1], dp[i][j]); 217 if(i < n && j < m && ps[i] == pt[j]) upd(dp[i + 1][j + 1], dp[i][j] + 1); 218 } 219 cout << dp[n][m] - 1 << "\n"; 220 } 221 222 int main() 223 { 224 int t; 225 cin >> t; 226 for(int i = 0; i < t; i++) 227 solve(); 228 return 0; 229 } 230 ``` 231 232 [2242E - Product of Closures](/contest/2242/problem/E "Educational Codeforces Round 192 (Rated for Div. 2)") 233 234 Idea: [adedalic](/profile/adedalic "International Master adedalic") 235 236 **Tutorial** 237 238 Tutorial is loading... 239 240 **Solution (adedalic)** 241 242 ``` 243 #include<bits/stdc++.h> 244 245 using namespace std; 246 247 #define fore(i, l, r) for(int i = int(l); i < int(r); i++) 248 #define sz(a) int((a).size()) 249 250 #define x first 251 #define y second 252 253 typedef long long li; 254 typedef long double ld; 255 typedef pair<int, int> pt; 256 257 template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) { 258 return out << "(" << p.x << ", " << p.y << ")"; 259 } 260 template<class A> ostream& operator <<(ostream& out, const vector<A> &v) { 261 fore(i, 0, sz(v)) { 262 if(i) out << " "; 263 out << v[i]; 264 } 265 return out; 266 } 267 268 const int INF = int(1e9); 269 const li INF64 = li(1e18); 270 const ld EPS = 1e-9; 271 272 int l, r, n; 273 274 void solve() { 275 cin >> l >> r >> n; 276 277 int k = 63 - __builtin_clzll(r); 278 int x = -1, y = -1; 279 if (l >= (1ll << k)) { 280 int p = 30; 281 while (((l >> p) & 1) == ((r >> p) & 1)) 282 p--; 283 assert(p >= 0); 284 x = l; 285 y = l - (l & ((1 << p) - 1)) + (1 << p); 286 } 287 else { 288 x = max(l, (1 << (k - 1))); 289 y = 1ll << k; 290 } 291 cerr << l << " " << r << ": " << x << " " << y << endl; 292 assert(l <= x && x < y && y <= r); 293 294 auto getBinary = [](int v) { 295 vector<int> rep; 296 while (v > 0) { 297 rep.push_back(v & 1); 298 v >>= 1; 299 } 300 reverse(rep.begin(), rep.end()); 301 return rep; 302 }; 303 304 auto x_bits = getBinary(x); 305 auto y_bits = getBinary(y); 306 307 string ans(n, '0'); 308 fore (i, 0, n) 309 ans[i] = '0' + (x_bits[i % x_bits.size()] & y_bits[i % y_bits.size()]); 310 cout << ans << endl; 311 } 312 313 int main() { 314 #ifdef _DEBUG 315 freopen("input.txt", "r", stdin); 316 int tt = clock(); 317 #endif 318 ios_base::sync_with_stdio(false); 319 cin.tie(0), cout.tie(0); 320 cout << fixed << setprecision(15); 321 322 int t; cin >> t; 323 while (t--) { 324 solve(); 325 326 #ifdef _DEBUG 327 cerr << "TIME = " << clock() - tt << endl; 328 tt = clock(); 329 #endif 330 } 331 return 0; 332 } 333 ``` 334 335 [2242F - Summer Vacation](/contest/2242/problem/F "Educational Codeforces Round 192 (Rated for Div. 2)") 336 337 Idea: [FelixArg](/profile/FelixArg "Master FelixArg") 338 339 **Tutorial** 340 341 Tutorial is loading... 342 343 **Solution (FelixArg)** 344 345 ``` 346 #include <bits/stdc++.h> 347 348 using namespace std; 349 350 mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count()); 351 352 const int MX = 200000; 353 const int REBUILD_EVERY = 5000; 354 355 struct item { 356 int value, cnt; 357 int l, r; 358 359 item(): value(0), cnt(0), l(0), r(0) {} 360 item(int x): value(x), cnt(1), l(0), r(0) {} 361 }; 362 363 vector<item> treap(1); 364 365 int copy(int v) { 366 treap.push_back(treap[v]); 367 return int(treap.size()) - 1; 368 } 369 370 int cnt(int v) { 371 return v ? treap[v].cnt : 0; 372 } 373 374 void upd_cnt(int v) { 375 if (v) { 376 treap[v].cnt = cnt(treap[v].l) + cnt(treap[v].r) + 1; 377 } 378 } 379 380 int merge(int l, int r) { 381 if (!l || !r) { 382 return l ? l : r; 383 } 384 385 int rang = rng() % (cnt(l) + cnt(r)); 386 387 if (rang < cnt(l)) { 388 int res = copy(l); 389 treap[res].r = merge(treap[res].r, r); 390 upd_cnt(res); 391 return res; 392 } else { 393 int res = copy(r); 394 treap[res].l = merge(l, treap[res].l); 395 upd_cnt(res); 396 return res; 397 } 398 } 399 400 int find_first(int v) { 401 if (!treap[v].l) { 402 return treap[v].value; 403 } else { 404 return find_first(treap[v].l); 405 } 406 } 407 408 void dfs(int v) { 409 if (!v) { 410 return; 411 } 412 413 if (treap[v].l) { 414 dfs(treap[v].l); 415 } 416 417 cout << treap[v].value << ' '; 418 419 if (treap[v].r) { 420 dfs(treap[v].r); 421 } 422 } 423 424 pair<int, int> split(int t, int key, int add = 0) { 425 if (!t) { 426 return make_pair(0, 0); 427 } 428 429 t = copy(t); 430 431 int cur_key = add + cnt(treap[t].l); 432 433 if (key <= cur_key) { 434 auto [l, r] = split(treap[t].l, key, add); 435 treap[t].l = r; 436 r = t; 437 upd_cnt(t); 438 return {l, r}; 439 } else { 440 auto [l, r] = split(treap[t].r, key, add + 1 + cnt(treap[t].l)); 441 treap[t].r = l; 442 l = t; 443 upd_cnt(t); 444 return {l, r}; 445 } 446 } 447 448 int change(int x, int it) { 449 auto [l, r] = split(it, x, 0); 450 auto [rl, rr] = split(r, x, 0); 451 auto [l1, r1] = split(it, MX - x, 0); 452 return merge(rl, l1); 453 } 454 455 void collect_values(int v, vector<int>& values) { 456 if (!v) { 457 return; 458 } 459 460 collect_values(treap[v].l, values); 461 values.push_back(treap[v].value); 462 collect_values(treap[v].r, values); 463 } 464 465 int build_balanced(const vector<int>& values, int l, int r) { 466 if (l >= r) { 467 return 0; 468 } 469 470 int m = (l + r) / 2; 471 472 treap.emplace_back(values[m]); 473 int v = int(treap.size()) - 1; 474 475 treap[v].l = build_balanced(values, l, m); 476 treap[v].r = build_balanced(values, m + 1, r); 477 478 upd_cnt(v); 479 return v; 480 } 481 482 int rebuild(int tr) { 483 vector<int> values; 484 values.reserve(cnt(tr)); 485 486 collect_values(tr, values); 487 488 treap.clear(); 489 treap.emplace_back(); 490 491 return build_balanced(values, 0, int(values.size())); 492 } 493 494 void solve() { 495 int n; 496 cin >> n; 497 498 vector<int> a(n); 499 for (int i = 0; i < n; i++) { 500 cin >> a[i]; 501 } 502 503 vector<int> ans(n); 504 505 treap.reserve((size_t)((1 << 25) * 1.5)); 506 507 int tr = 0; 508 509 for (int i = 0; i < MX; i++) { 510 treap.emplace_back(i); 511 tr = merge(tr, int(treap.size()) - 1); 512 } 513 514 int changed_iterations = 0; 515 516 for (int i = n - 1; i >= 0; i--) { 517 tr = change(a[i], tr); 518 ans[i] = find_first(tr); 519 520 changed_iterations++; 521 522 if (changed_iterations % REBUILD_EVERY == 0) { 523 tr = rebuild(tr); 524 } 525 } 526 527 for (int i = n - 1; i >= 0; i--) { 528 cout << ans[i] << ' '; 529 } 530 } 531 532 signed main() { 533 #ifdef FELIX 534 auto _clock_start = chrono::high_resolution_clock::now(); 535 #endif 536 537 ios_base::sync_with_stdio(false); 538 cin.tie(0); 539 cout.tie(0); 540 541 int tests = 1; 542 // cin >> tests; 543 544 while (tests--) { 545 solve(); 546 } 547 548 #ifdef FELIX 549 cerr << "Executed in " 550 << chrono::duration_cast<chrono::milliseconds>( 551 chrono::high_resolution_clock::now() - _clock_start 552 ).count() 553 << "ms." 554 << endl; 555 #endif 556 557 return 0; 558 } 559 ```