1684.md (12742B)
1 Source: https://codeforces.com/blog/entry/102995 2 3 We know about FST and we are really, really sorry about it. Even though we still hope that you liked the problems. 4 5 **A: Digit Minimization** 6 7 [1684A - Digit Minimization](/contest/1684/problem/A) 8 9 **Editorial** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 int main() { 20 int T; 21 cin >> T; 22 while (T --> 0) { 23 string n; 24 cin >> n; 25 if (n.size() == 2) { 26 cout << n[1] << '\n'; 27 } else { 28 cout << *min_element(n.begin(), n.end()) << '\n'; 29 } 30 } 31 return 0; 32 } 33 ``` 34 35 **B: Z mod X = C** 36 37 [1684B - Z mod X = C](/contest/1684/problem/B) 38 39 **Editorial** 40 41 Tutorial is loading... 42 43 **Implementation** 44 45 ``` 46 #include <bits/stdc++.h> 47 using namespace std; 48 49 void solve() { 50 int a, b, c; 51 cin >> a >> b >> c; 52 cout << a + b + c << " " << b + c << " " << c << "\n"; 53 } 54 55 int main() { 56 int t; 57 cin >> t; 58 while (t--) solve(); 59 return 0; 60 } 61 ``` 62 63 **C: Column Swapping** 64 65 [1684C - Column Swapping](/contest/1684/problem/C) 66 67 **Editorial** 68 69 Tutorial is loading... 70 71 **Implementation** 72 73 ``` 74 #include <bits/stdc++.h> 75 76 using namespace std; 77 78 void solve(vector<vector<int>> &a) { 79 int n = a.size(), m = a[0].size(); 80 vector<int> bad; 81 for (int i = 0; i < n && bad.empty(); i++) { 82 vector<int> b = a[i]; 83 sort(b.begin(), b.end()); 84 for (int j = 0; j < m; j++) { 85 if (a[i][j] != b[j]) bad.push_back(j); 86 } 87 } 88 if ((int)bad.size() == 0) { 89 cout << 1 << " " << 1 << "\n"; 90 return; 91 } 92 if ((int)bad.size() > 2) { 93 cout << -1 << "\n"; 94 return; 95 } 96 for (int i = 0; i < n; i++) { 97 swap(a[i][bad[0]], a[i][bad[1]]); 98 } 99 for (int i = 0; i < n; i++) { 100 for (int j = 1; j < m; j++) { 101 if (a[i][j] < a[i][j - 1]) { 102 cout << -1 << "\n"; 103 return; 104 } 105 } 106 } 107 cout << bad[0] + 1 << " " << bad[1] + 1 << "\n"; 108 return; 109 } 110 111 int main() { 112 #ifdef LOCAL 113 freopen("input.txt", "r", stdin); 114 freopen("output.txt", "w", stdout); 115 #else 116 ios_base::sync_with_stdio(0); 117 cin.tie(0); 118 cout.tie(0); 119 #endif 120 int T; 121 cin >> T; 122 while (T--) { 123 int n, m; 124 cin >> n >> m; 125 vector<vector<int>> a(n, vector<int>(m)); 126 for (int i = 0; i < n; i++) { 127 for (int j = 0; j < m; j++) { 128 cin >> a[i][j]; 129 } 130 } 131 solve(a); 132 } 133 return 0; 134 } 135 ``` 136 137 **D: Traps** 138 139 [1684D - Traps](/contest/1684/problem/D) 140 141 **Editorial** 142 143 Tutorial is loading... 144 145 **Implementation** 146 147 ``` 148 #include <bits/stdc++.h> 149 using namespace std; 150 151 #define all(x) (x).begin(), (x).end() 152 153 void solve() { 154 int n, k; 155 cin >> n >> k; 156 long long ans = 0; 157 vector<int> a(n); 158 for (int i = 0; i < n; i++) { 159 cin >> a[i]; 160 ans += a[i]; 161 a[i] += i + 1; 162 } 163 sort(all(a)); 164 reverse(all(a)); 165 for (int i = 0; i < k; i++) ans -= a[i]; 166 for (int i = 0; i < k; i++) { 167 ans += n; 168 ans -= i; 169 } 170 cout << ans << "\n"; 171 } 172 173 int main() { 174 #ifdef LOCAL 175 freopen("input.txt", "r", stdin); 176 freopen("output.txt", "w", stdout); 177 #else 178 ios_base::sync_with_stdio(0); 179 cin.tie(0); 180 cout.tie(0); 181 #endif 182 int t; 183 cin >> t; 184 while (t--) solve(); 185 return 0; 186 } 187 ``` 188 189 **E: MEX vs DIFF** 190 191 [1684E - MEX vs DIFF](/contest/1684/problem/E) 192 193 **Editorial** 194 195 Tutorial is loading... 196 197 **Implementation** 198 199 ``` 200 #include <bits/stdc++.h> 201 202 using namespace std; 203 204 #define pb emplace_back 205 #define all(x) (x).begin(), (x).end() 206 #define fi first 207 #define se second 208 #define pii pair<int, int> 209 #define puu pair<unsigned, unsigned> 210 #define ll long long 211 #define mp make_pair 212 #define ui unsigned 213 #define ull unsigned long long 214 #define ld double 215 #define pld pair<ld, ld> 216 #define pll pair<ll, ll> 217 218 const int INF = 1e9 + 1; 219 const ll INFLL = 1e18; 220 221 void solve() { 222 int n, k; 223 cin >> n >> k; 224 vector<int> a(n); 225 for (auto &c : a) cin >> c; 226 map<int, int> cnt; 227 for (auto &c : a) cnt[c]++; 228 set<pii> s1, s2; 229 int sum1 = 0; 230 for (auto &c : cnt) s2.insert(mp(c.se, c.fi)); 231 int ans = INF; 232 int skip = 0; 233 for (int x = 0; x <= n; x++) { 234 if (s1.find(mp(cnt[x - 1], x - 1)) != s1.end()) { 235 sum1 -= cnt[x - 1]; 236 s1.erase(mp(cnt[x - 1], x - 1)); 237 } 238 if (s2.find(mp(cnt[x - 1], x - 1)) != s2.end()) { 239 s2.erase(mp(cnt[x - 1], x - 1)); 240 } 241 while (s2.size() && sum1 + s2.begin()->fi <= k) { 242 s1.insert(*s2.begin()); 243 sum1 += s2.begin()->fi; 244 s2.erase(s2.begin()); 245 } 246 if (k < skip) break; 247 int now = x + s2.size(); 248 if (x == 0) { 249 now = max(1, (int)s2.size()); 250 } 251 ans = min(ans, now - x); 252 if (cnt[x] == 0) skip++; 253 } 254 cout << ans << "\n"; 255 } 256 257 int main() { 258 #ifdef LOCAL 259 freopen("input.txt", "r", stdin); 260 freopen("output.txt", "w", stdout); 261 #else 262 ios_base::sync_with_stdio(0); 263 cin.tie(0); 264 cout.tie(0); 265 #endif 266 int t; 267 cin >> t; 268 while (t--) solve(); 269 return 0; 270 } 271 ``` 272 273 **F: Diverse Segments** 274 275 [1684F - Diverse Segments](/contest/1684/problem/F) 276 277 **Editorial** 278 279 Tutorial is loading... 280 281 **Implementation** 282 283 ``` 284 #include <bits/stdc++.h> 285 286 using namespace std; 287 288 #define pb emplace_back 289 #define all(x) (x).begin(), (x).end() 290 #define fi first 291 #define se second 292 #define pii pair<int, int> 293 #define puu pair<unsigned, unsigned> 294 #define ll long long 295 #define mp make_pair 296 #define ui unsigned 297 #define ull unsigned long long 298 #define ld double 299 #define pld pair<ld, ld> 300 #define pll pair<ll, ll> 301 302 const int INF = 1e9 + 1; 303 const ll INFLL = 1e18; 304 305 vector<int> f; 306 307 void incr(int x, int d) { 308 for (; x < (int)f.size(); x |= (x + 1)) f[x] = max(f[x], d); 309 } 310 311 int get(int x) { 312 int ans = -1; 313 for (; x >= 0; x = (x & (x + 1)) - 1) ans = max(ans, f[x]); 314 return ans; 315 } 316 317 void solve() { 318 int n, m; 319 cin >> n >> m; 320 vector<int> a(n); 321 for (auto &c : a) cin >> c; 322 map<int, vector<int>> gist; 323 for (int i = 0; i < n; i++) gist[a[i]].pb(i); 324 vector<pii> seg(m); 325 f.assign(n, -1); 326 for (auto &c : seg) { 327 cin >> c.fi >> c.se; c.fi--; c.se--; 328 incr(c.fi, c.se); 329 } 330 vector<int> mnl(n); 331 set<int> s; 332 int l = n; 333 for (int r = n - 1; r >= 0; r--) { 334 while (l - 1 >= 0 && !s.count(a[l - 1])) { 335 l--; 336 s.insert(a[l]); 337 } 338 mnl[r] = l; 339 s.erase(a[r]); 340 } 341 int mnr = -1; 342 for (auto &c : seg) { 343 int l = c.fi, r = c.se; 344 if (mnl[r] <= l) continue; 345 mnr = max(mnr, mnl[r] - 1); 346 } 347 if (mnr == -1) { 348 cout << 0 << "\n"; 349 return; 350 } 351 int ans = mnr + 1; 352 for (int l = 0; l + 1 < n; l++) { 353 if (gist[a[l]][0] != l) { 354 int id = lower_bound(all(gist[a[l]]), l) - gist[a[l]].begin() - 1; 355 int pr = gist[a[l]][id]; 356 if (get(pr) >= l) { 357 break; 358 } 359 } 360 int id = upper_bound(all(gist[a[l]]), mnr) - gist[a[l]].begin(); 361 if (id != (int)gist[a[l]].size()) { 362 int nxt = gist[a[l]][id]; 363 if (get(l) >= nxt) { 364 mnr = nxt; 365 } 366 } 367 mnr = max(mnr, l + 1); 368 ans = min(ans, mnr - l); 369 } 370 cout << ans << "\n"; 371 } 372 373 int main() { 374 #ifdef LOCAL 375 freopen("input.txt", "r", stdin); 376 freopen("output.txt", "w", stdout); 377 #else 378 ios_base::sync_with_stdio(0); 379 cin.tie(0); 380 cout.tie(0); 381 #endif 382 int t; 383 cin >> t; 384 while (t--) solve(); 385 return 0; 386 } 387 ``` 388 389 **G: Euclid Guess** 390 391 [1684G - Euclid Guess](/contest/1684/problem/G) 392 393 **Editorial** 394 395 Tutorial is loading... 396 397 **Implementation** 398 399 ``` 400 #include <bits/stdc++.h> 401 402 using namespace std; 403 404 #define pb emplace_back 405 #define all(x) (x).begin(), (x).end() 406 #define fi first 407 #define se second 408 #define pii pair<int, int> 409 #define puu pair<unsigned, unsigned> 410 #define ll long long 411 #define mp make_pair 412 #define ui unsigned 413 #define ull unsigned long long 414 #define ld double 415 #define pld pair<ld, ld> 416 #define pll pair<ll, ll> 417 #define int ll 418 419 const int INF = 1e9 + 1; 420 const ll INFLL = 1e18; 421 422 vector<vector<int>> g; 423 vector<int> with; 424 vector<int> usd; 425 426 int dfs(int v) { 427 if (usd[v]) return 0; 428 usd[v] = 1; 429 for (auto &to : g[v]) { 430 if (with[to] == -1) { 431 with[to] = v; 432 return 1; 433 } 434 } 435 for (auto &to : g[v]) { 436 if (dfs(with[to])) { 437 with[to] = v; 438 return 1; 439 } 440 } 441 return 0; 442 } 443 444 signed main() { 445 #ifdef LOCAL 446 freopen("input.txt", "r", stdin); 447 freopen("output.txt", "w", stdout); 448 #else 449 ios_base::sync_with_stdio(0); 450 cin.tie(0); 451 cout.tie(0); 452 #endif 453 int n, A; 454 cin >> n >> A; 455 vector<int> a(n); 456 vector<int> l, r; 457 for (auto &c : a) { 458 cin >> c; 459 if (3 * c > A) { 460 l.pb(c); 461 } else { 462 r.pb(c); 463 } 464 } 465 g.resize(l.size()); 466 with.resize(r.size(), -1); 467 for (int i = 0; i < (int)l.size(); i++) { 468 for (int j = 0; j < (int)r.size(); j++) { 469 if (l[i] % r[j] == 0 && 2 * l[i] + r[j] <= A) { 470 g[i].pb(j); 471 } 472 } 473 } 474 int cnt = 0; 475 for (int i = 0; i < (int)l.size(); i++) { 476 usd.assign(l.size(), 0); 477 cnt += dfs(i); 478 } 479 if (cnt < (int)l.size()) { 480 cout << -1; 481 return 0; 482 } 483 vector<pii> ans; 484 for (int j = 0; j < (int)r.size(); j++) { 485 if (with[j] == -1) { 486 ans.pb(3 * r[j], 2 * r[j]); 487 } else { 488 ans.pb(2 * l[with[j]] + r[j], l[with[j]] + r[j]); 489 } 490 } 491 cout << ans.size() << "\n"; 492 for (auto &c : ans) cout << c.fi << " " << c.se << "\n"; 493 return 0; 494 } 495 ``` 496 497 **H: Hard Cut** 498 499 [1684H - Hard Cut](/contest/1684/problem/H) 500 501 **Editorial** 502 503 Tutorial is loading... 504 505 **Implementation** 506 507 ``` 508 #include <bits/stdc++.h> 509 using namespace std; 510 511 const int MAXN = 1e6; 512 int g[MAXN + 1]; 513 string s; 514 515 vector<pair<int, int>> segments; // [l, r] 516 517 int get(int k, int i) { // get k-th '1' on [i, |s|) 518 --i; 519 while (k --> 0) i = s.find('1', i + 1); 520 return i; 521 } 522 523 void five() { 524 int first = get(1, 0), last = get(5, 0); 525 int r = (int)s.size() - 1; 526 if (last - first + 1 == 5) { // creating 16: ['001111', '1', '0000'] 527 segments.emplace_back(0, last - 1); 528 segments.emplace_back(last, last); 529 if (last < r) segments.emplace_back(last + 1, r); 530 } else { // creating 8: cut out '101' or '100' and cut everything in single digits 531 int pos = s.find("101"); 532 if (pos == string::npos) pos = s.find("100"); 533 for (int i = 0; i < pos; ++i) segments.emplace_back(i, i); 534 segments.emplace_back(pos, pos + 2); 535 for (int i = pos + 3; i <= r; ++i) segments.emplace_back(i, i); 536 } 537 } 538 539 void solve(int l, int r, int k, int n) { // [l; r] 540 if (k == n) { // cutting into single digits 541 for (int i = l; i <= r; ++i) segments.emplace_back(i, i); 542 543 } else if (k == 2 && n == 3) { 544 int pos = get(1, l); 545 if (s[pos + 1] == '1') { // ['11', '00...00'] 546 segments.emplace_back(l, pos + 1); 547 if (pos + 2 <= r) segments.emplace_back(pos + 2, r); 548 549 } else { // ['10', '0001', '00000'] 550 int newpos = get(1, pos + 1); 551 segments.emplace_back(l, pos + 1); 552 segments.emplace_back(pos + 2, newpos); 553 if (newpos + 1 <= r) segments.emplace_back(newpos + 1, r); 554 } 555 556 } else if (3 * k / 2 >= n) { // using previous if technique 557 int pos = get(2, l); 558 solve(l, pos, 2, 3); 559 if (k > 2) solve(pos + 1, r, k - 2, n - 3); 560 561 } else if ((k == 4 && n == 8) || (k == 9 && n == 16)) { 562 int pos = get(1, l); 563 string sub = s.substr(pos, 3); 564 segments.emplace_back(l, pos + 2); 565 if (sub == "100") solve(pos + 3, r, k - 1, n - 4); 566 if (sub == "101") solve(pos + 3, r, k - 2, n - 5); 567 if (sub == "110") solve(pos + 3, r, k - 2, n - 6); 568 if (sub == "111") solve(pos + 3, r, k - 3, n - 7); 569 570 } else if ((k == 7 && n == 11) || (k == 10 && n == 16)) { 571 int mid = get(4, l); 572 solve(l, mid, 4, 8); 573 solve(mid + 1, r, k - 4, n - 8); 574 575 } else { // common case 576 int mid = get(k / 2, l); 577 solve(l, mid, k / 2, n / 2); 578 solve(mid + 1, r, k - k / 2, n / 2); 579 580 } 581 } 582 583 signed main() { 584 ios_base::sync_with_stdio(false); 585 cin.tie(nullptr); 586 g[1] = 1; 587 for (int i = 2; i <= MAXN; ++i) g[i] = g[(i + 1) / 2] * 2; 588 int T; 589 cin >> T; 590 while (T --> 0) { 591 cin >> s; 592 int k = count(s.begin(), s.end(), '1'); 593 if (!k) { 594 cout << -1 << '\n'; 595 continue; 596 } 597 segments.clear(); 598 if (k == 5) five(); 599 else solve(0, (int)s.size() - 1, k, g[k]); 600 cout << segments.size() << '\n'; 601 for (auto &[l, r] : segments) { 602 cout << l + 1 << ' ' << r + 1 << '\n'; 603 } 604 } 605 return 0; 606 } 607 ```