1619.md (10867B)
1 Source: https://codeforces.com/blog/entry/98159 2 3 [1619A - Квадратная строка?](/contest/1619/problem/A "Codeforces Round 762 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 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 20 int main() { 21 int t; 22 cin >> t; 23 forn(tt, t) { 24 string s; 25 cin >> s; 26 bool ok = true; 27 if (s.length() % 2 == 0) { 28 forn(i, s.length() / 2) 29 if (s[i] != s[i + s.length() / 2]) 30 ok = false; 31 } else 32 ok = false; 33 cout << (ok ? "YES" : "NO") << endl; 34 } 35 } 36 ``` 37 38 [1619B - Квадраты и кубы](/contest/1619/problem/B "Codeforces Round 762 (Div. 3)") 39 40 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 41 42 **Tutorial** 43 44 Tutorial is loading... 45 46 **Solution** 47 48 ``` 49 #include <bits/stdc++.h> 50 51 using namespace std; 52 53 #define forn(i, n) for (int i = 0; i < int(n); i++) 54 55 int main() { 56 int t; 57 cin >> t; 58 forn(tt, t) { 59 int n; 60 cin >> n; 61 set<int> a; 62 for (int i = 1; i * i <= n; i++) 63 a.insert(i * i); 64 for (int i = 1; i * i * i <= n; i++) 65 a.insert(i * i * i); 66 cout << a.size() << endl; 67 } 68 } 69 ``` 70 71 [1619C - Неправильное сложение](/contest/1619/problem/C "Codeforces Round 762 (Div. 3)") 72 73 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 74 75 **Tutorial** 76 77 Tutorial is loading... 78 79 **Solution** 80 81 ``` 82 #include<bits/stdc++.h> 83 #define len(s) (int)s.size() 84 using namespace std; 85 using ll = long long; 86 87 void solve(){ 88 ll a, s; 89 cin >> a >> s; 90 vector<int>b; 91 while(s){ 92 int x = a % 10; 93 int y = s % 10; 94 if(x <= y) b.emplace_back(y - x); 95 else{ 96 s /= 10; 97 y += 10 * (s % 10); 98 if(x < y && y >= 10 && y <= 19) b.emplace_back(y - x); 99 else{ 100 cout << -1 << '\n'; 101 return; 102 } 103 } 104 a /= 10; 105 s /= 10; 106 } 107 if(a) cout << -1 << '\n'; 108 else{ 109 while (b.back() == 0) b.pop_back(); 110 for(int i = len(b) - 1; i >= 0; i--) cout << b[i]; 111 cout << '\n'; 112 } 113 } 114 115 int main(){ 116 ios_base ::sync_with_stdio(false); 117 cin.tie(nullptr); 118 119 int t; 120 cin >> t; 121 while (t){ 122 solve(); 123 t--; 124 } 125 return 0; 126 } 127 ``` 128 129 [1619D - Новогодняя задача](/contest/1619/problem/D "Codeforces Round 762 (Div. 3)") 130 131 Idea: [Vladosiya](/profile/Vladosiya "Специалист Vladosiya") 132 133 **Tutorial** 134 135 Tutorial is loading... 136 137 **Solution** 138 139 ``` 140 // 141 // Created by Vlad on 17.12.2021. 142 // 143 144 #include <bits/stdc++.h> 145 146 #define int long long 147 #define mp make_pair 148 #define x first 149 #define y second 150 #define all(a) (a).begin(), (a).end() 151 #define rall(a) (a).rbegin(), (a).rend() 152 153 /*#pragma GCC optimize("Ofast") 154 #pragma GCC optimize("no-stack-protector") 155 #pragma GCC optimize("unroll-loops") 156 #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") 157 #pragma GCC optimize("fast-math") 158 */ 159 typedef long double ld; 160 typedef long long ll; 161 162 using namespace std; 163 164 mt19937 rnd(143); 165 166 const int inf = 1e10; 167 const int M = 998244353; 168 const ld pi = atan2(0, -1); 169 const ld eps = 1e-4; 170 171 int n, m; 172 vector<vector<int>> p; 173 174 bool check(int x){ 175 vector<bool> abl(m); 176 bool pair = false; 177 for(int i = 0; i < n; ++i){ 178 int c = 0; 179 for(int j = 0; j < m; ++j){ 180 if(p[i][j] >= x){ 181 abl[j] = true; 182 c++; 183 } 184 } 185 if(c > 1) pair = true; 186 } 187 if(!pair && m > 1) return false; 188 bool ans = true; 189 for(bool b: abl){ 190 ans = ans && b; 191 } 192 return ans; 193 } 194 195 void solve() { 196 cin >> n >> m; 197 p.assign(n, vector<int>(m)); 198 for(int i = 0; i < n; ++i){ 199 for(int j = 0; j < m; ++j){ 200 cin >> p[i][j]; 201 } 202 } 203 int l = 1, r = 2; 204 while (check(r)) r *= 2; 205 while (r - l > 1){ 206 int mid = (r + l) / 2; 207 if(check(mid)) l = mid; 208 else r = mid; 209 } 210 cout << l; 211 } 212 213 bool multi = true; 214 215 signed main() { 216 //freopen("in.txt", "r", stdin); 217 //freopen("in.txt", "w", stdout); 218 int t = 1; 219 if (multi) { 220 cin >> t; 221 } 222 for (; t != 0; --t) { 223 solve(); 224 cout << "\n"; 225 } 226 return 0; 227 } 228 ``` 229 230 [1619E - MEX и инкременты](/contest/1619/problem/E "Codeforces Round 762 (Div. 3)") 231 232 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Мастер ibraevdmitriy") 233 234 **Tutorial** 235 236 Tutorial is loading... 237 238 **Solution** 239 240 ``` 241 #include <iostream> 242 #include <vector> 243 #include <stack> 244 #include <algorithm> 245 246 using namespace std; 247 248 typedef long long ll; 249 const int MAX_N = 2e5; 250 251 int main() { 252 int t; 253 cin >> t; 254 for (int _ = 0; _ < t; ++_) { 255 int n; 256 cin >> n; 257 vector<int> a(n), cnt(n + 1); 258 for (int i = 0; i < n; ++i) { 259 cin >> a[i]; 260 cnt[a[i]]++; 261 } 262 sort(a.begin(), a.end()); 263 stack<int> st; 264 vector<ll> ans(n + 1, -1); 265 ll sum = 0; 266 for (int i = 0; i <= n; ++i) { 267 if (i > 0 && cnt[i - 1] == 0) { 268 if (st.empty()) { 269 break; 270 } 271 int j = st.top(); 272 st.pop(); 273 sum += i - j - 1; 274 } 275 ans[i] = sum + cnt[i]; 276 while (i > 0 && cnt[i - 1] > 1) { 277 cnt[i - 1]--; 278 st.push(i - 1); 279 } 280 } 281 for (ll x : ans) { 282 cout << x << ' '; 283 } 284 cout << '\n'; 285 } 286 } 287 ``` 288 289 [1619F - Сыграем в Шляпу?](/contest/1619/problem/F "Codeforces Round 762 (Div. 3)") 290 291 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Штаб, MikeMirzayanov") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 using namespace std; 303 304 #define forn(i, n) for (int i = 0; i < int(n); i++) 305 306 int main() { 307 int t; 308 cin >> t; 309 forn(tt, t) { 310 int n, m, k; 311 cin >> n >> m >> k; 312 vector<int> p(n); 313 forn(i, n) 314 p[i] = i; 315 if (tt > 0) 316 cout << endl; 317 forn(round, k) { 318 int index = 0; 319 forn(table, m) { 320 int size = n / m; 321 if (table < n % m) 322 size++; 323 cout << size; 324 forn(j, size) 325 cout << " " << p[index++] + 1; 326 cout << endl; 327 } 328 rotate(p.begin(), p.begin() + (n % m) * ((n + m - 1) / m), p.end()); 329 } 330 } 331 } 332 ``` 333 334 [1619G - Необычный сапёр](/contest/1619/problem/G "Codeforces Round 762 (Div. 3)") 335 336 Idea: [Gol_D](/profile/Gol_D "Кандидат в мастера Gol_D") 337 338 **Tutorial** 339 340 Tutorial is loading... 341 342 **Solution** 343 344 ``` 345 #include <bits/stdc++.h> 346 347 using namespace std; 348 349 typedef long long ll; 350 351 #define forn(i, n) for (int i = 0; i < int(n); i++) 352 353 int k; 354 355 map <int, vector<int>> mx; 356 map <int, vector<int>> my; 357 map <pair<int ,int>, bool> used; 358 map <pair<int, int>, int> time_of; 359 360 int dfs(int x, int y) { 361 used[{x, y}] = true; 362 int _min_ = time_of[{x, y}]; 363 364 auto i = lower_bound(mx[x].begin(), mx[x].end(), y); 365 auto j = lower_bound(my[y].begin(), my[y].end(), x); 366 367 if (++i != mx[x].end() && !used[{x, *i}] && abs(*i - y) <= k) { 368 _min_ = min(_min_, dfs(x, *i)); 369 } 370 --i; 371 if (i != mx[x].begin() && !used[{x, *(--i)}] && abs(*i - y) <= k) { 372 _min_ = min(_min_, dfs(x, *i)); 373 } 374 375 if (++j != my[y].end() && !used[{*j, y}] && abs(*j - x) <= k) { 376 _min_ = min(_min_, dfs(*j, y)); 377 } 378 --j; 379 if (j != my[y].begin() && !used[{*(--j), y}] && abs(*j - x) <= k) { 380 _min_ = min(_min_, dfs(*j, y)); 381 } 382 383 return _min_; 384 } 385 386 void solve() { 387 mx.clear(); 388 my.clear(); 389 used.clear(); 390 391 int n; 392 cin >> n >> k; 393 vector <pair<int, int>> a(n); 394 int x, y, timer; 395 396 for (int i = 0; i < n; ++i) { 397 cin >> x >> y >> timer; 398 a[i] = {x, y}; 399 time_of[{x, y}] = timer; 400 mx[x].push_back(y); 401 my[y].push_back(x); 402 } 403 vector<int> res; 404 405 for (auto now: mx) { 406 sort(mx[now.first].begin(), mx[now.first].end()); 407 } 408 for (auto now: my) { 409 sort(my[now.first].begin(), my[now.first].end()); 410 } 411 412 for (auto now: a) { 413 if (!used[now]) { 414 res.push_back(dfs(now.first, now.second)); 415 } 416 } 417 sort(res.begin(), res.end()); 418 419 int ans = res.size() - 1; 420 for (int i = 0; i < res.size(); ++i) { 421 ans = min(ans, max((int)res.size() - i - 2, res[i])); 422 } 423 cout << ans << '\n'; 424 } 425 int main() { 426 ios_base::sync_with_stdio(0); 427 cin.tie(nullptr); cout.tie(nullptr); 428 int tests; 429 cin >> tests; 430 forn(tt, tests) { 431 solve(); 432 } 433 } 434 ``` 435 436 [1619H - Перестановка и запросы](/contest/1619/problem/H "Codeforces Round 762 (Div. 3)") 437 438 Idea: [Brovko](/profile/Brovko "Международный мастер Brovko") 439 440 **Tutorial** 441 442 Tutorial is loading... 443 444 **Solution** 445 446 ``` 447 #include <bits/stdc++.h> 448 //#define int long long 449 #define ld long double 450 #define x first 451 #define y second 452 #define pb push_back 453 454 using namespace std; 455 const int Q = 100; 456 457 int n, q, p[100005], r[100005], a[100005]; 458 459 int32_t main() 460 { 461 ios_base::sync_with_stdio(0); 462 cin.tie(0); 463 cout.tie(0); 464 465 cin >> n >> q; 466 467 for(int i = 0; i < n; i++) 468 { 469 cin >> p[i]; 470 p[i]--; 471 } 472 473 for(int i = 0; i < n; i++) 474 r[p[i]] = i; 475 476 for(int i = 0; i < n; i++) 477 { 478 int x = i; 479 480 for(int j = 0; j < Q; j++) 481 x = p[x]; 482 483 a[i] = x; 484 } 485 486 while(q--) 487 { 488 int t, x, y; 489 cin >> t >> x >> y; 490 491 if(t == 2) 492 { 493 x--; 494 495 while(y >= Q) 496 { 497 y -= Q; 498 x = a[x]; 499 } 500 501 while(y--) 502 x = p[x]; 503 504 cout << x + 1 << "\n"; 505 } 506 else 507 { 508 x--; 509 y--; 510 511 swap(r[p[x]], r[p[y]]); 512 swap(p[x], p[y]); 513 514 int ax = x; 515 516 for(int i = 0; i < Q; i++) 517 ax = p[ax]; 518 519 int x2 = x; 520 521 for(int i = 0; i < Q; i++) 522 { 523 a[x] = ax; 524 x = r[x]; 525 ax = r[ax]; 526 } 527 528 swap(x, y); 529 530 ax = x; 531 532 for(int i = 0; i < Q; i++) 533 ax = p[ax]; 534 535 x2 = x; 536 537 for(int i = 0; i < Q; i++) 538 { 539 a[x] = ax; 540 x = r[x]; 541 ax = r[ax]; 542 } 543 } 544 } 545 } 546 ```