2059.md (11734B)
1 Source: https://codeforces.com/blog/entry/139094 2 3 Thank you for participating! We hope you enjoyed our problems 4 5 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 6 7 ## [2059A - Milya and Two Arrays](/contest/2059/problem/A "Codeforces Round 1002 (Div. 2)") 8 9 **Solution** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <bits/stdc++.h> 17 using namespace std; 18 19 int a[55],b[55]; 20 21 void solve(){ 22 int n;cin>>n; 23 set<int> sa,sb; 24 for(int i=1;i<=n;i++)cin>>a[i],sa.insert(a[i]); 25 for(int i=1;i<=n;i++)cin>>b[i],sb.insert(b[i]); 26 if(sa.size()+sb.size()<4){ 27 cout<<"NO\n"; 28 }else{ 29 cout<<"YES\n"; 30 } 31 } 32 33 int main(){ 34 ios_base::sync_with_stdio(0); 35 cin.tie(0); 36 37 int t;cin>>t; 38 while(t--){ 39 solve(); 40 } 41 42 return 0; 43 } 44 ``` 45 46 ## [2059B - Cost of the Array](/contest/2059/problem/B "Codeforces Round 1002 (Div. 2)") 47 48 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 49 50 **Solution** 51 52 Tutorial is loading... 53 54 **Implementation** 55 56 ``` 57 #include <bits/stdc++.h> 58 using namespace std; 59 60 void solve() { 61 int n, k; 62 cin >> n >> k; 63 k /= 2; 64 vector<int> a(n); 65 for (auto &it: a) cin >> it; 66 if (2 * k == n) { 67 for (int i = 1; i < n; i += 2) { 68 if (a[i] != (i + 1) / 2) { 69 cout << (i + 1) / 2 << '\n'; 70 return; 71 } 72 } 73 cout << k + 1 << '\n'; 74 } else { 75 for (int i = 1; i <= n - 2 * k + 1; i++) { 76 if (a[i] != 1) { 77 cout << "1\n"; 78 return; 79 } 80 } 81 cout << "2\n"; 82 } 83 } 84 85 int main() { 86 int T = 1; 87 cin >> T; 88 while (T--) { 89 solve(); 90 } 91 } 92 ``` 93 94 ## [2059C - Customer Service](/contest/2059/problem/C "Codeforces Round 1002 (Div. 2)") 95 96 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 97 98 **Solution** 99 100 Tutorial is loading... 101 102 **Implementation** 103 104 ``` 105 #include <bits/stdc++.h> 106 using namespace std; 107 108 const int N=305; 109 110 int a[N][N],suff[N]; 111 112 void solve(){ 113 int n;cin>>n; 114 for(int i=1;i<=n;i++){ 115 suff[i]=0; 116 for(int j=1;j<=n;j++){ 117 cin>>a[i][j]; 118 } 119 } 120 for(int i=1;i<=n;i++){ 121 for(int j=n;j>=1;j--){ 122 if(a[i][j]!=1)break; 123 suff[i]++; 124 } 125 } 126 multiset<int> s; 127 for(int i=1;i<=n;i++){ 128 s.insert(suff[i]); 129 } 130 int ans=1; 131 while(!s.empty()){ 132 int cur=*s.begin(); 133 if(cur>=ans){ 134 ans++; 135 } 136 s.extract(cur); 137 } 138 cout<<min(ans,n)<<'\n'; 139 } 140 141 int main(){ 142 ios_base::sync_with_stdio(0); 143 cin.tie(0); 144 145 int t;cin>>t; 146 while(t--){ 147 solve(); 148 } 149 150 return 0; 151 } 152 ``` 153 154 ## [2059D - Graph and Graph](/contest/2059/problem/D "Codeforces Round 1002 (Div. 2)") 155 156 Author and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 157 158 **Solution** 159 160 Tutorial is loading... 161 162 **Implementation** 163 164 ``` 165 #include "bits/stdc++.h" 166 using namespace std; 167 168 #define int long long 169 #define eb emplace_back 170 171 const int INF = 1e18; 172 173 void solve() { 174 int n, s1, s2; 175 cin >> n >> s1 >> s2; 176 s1--, s2--; 177 vector<vector<int>> g1(n), g2(n); 178 vector<bool> good(n); 179 set<pair<int, int>> edges; 180 int m1; 181 cin >> m1; 182 for (int i = 0; i < m1; i++) { 183 int v, u; 184 cin >> v >> u; 185 v--, u--; 186 if (v > u) 187 swap(v, u); 188 edges.insert({v, u}); 189 g1[v].eb(u); 190 g1[u].eb(v); 191 } 192 int m2; 193 cin >> m2; 194 for (int i = 0; i < m2; i++) { 195 int v, u; 196 cin >> v >> u; 197 v--, u--; 198 if (v > u) 199 swap(v, u); 200 if (edges.find({v, u}) != edges.end()) 201 good[v] = true, good[u] = true; 202 g2[v].eb(u); 203 g2[u].eb(v); 204 } 205 vector<vector<int>> d(n, vector<int> (n, INF)); 206 d[s1][s2] = 0; 207 set<pair<int, pair<int, int>>> st; 208 st.insert({0, {s1, s2}}); 209 while (!st.empty()) { 210 auto [v, u] = st.begin()->second; 211 st.erase(st.begin()); 212 for (auto to1 : g1[v]) { 213 for (auto to2 : g2[u]) { 214 int w = abs(to1 - to2); 215 if (d[to1][to2] > d[v][u] + w) { 216 st.erase({d[to1][to2], {to1, to2}}); 217 d[to1][to2] = d[v][u] + w; 218 st.insert({d[to1][to2], {to1, to2}}); 219 } 220 } 221 } 222 } 223 int ans = INF; 224 for (int i = 0; i < n; i++) { 225 if (!good[i]) 226 continue; 227 ans = min(ans, d[i][i]); 228 } 229 if (ans == INF) 230 ans = -1; 231 cout << ans << '\n'; 232 } 233 234 signed main() { 235 //cout << fixed << setprecision(5); 236 ios::sync_with_stdio(false); 237 cin.tie(nullptr); 238 int T = 1; 239 cin >> T; 240 //cin >> G; 241 while (T--) 242 solve(); 243 return 0; 244 } 245 ``` 246 247 ## [2059E1 - Stop Gaming (Easy Version)](/contest/2059/problem/E1 "Codeforces Round 1002 (Div. 2)") 248 249 Author [shfs](/profile/shfs "Candidate Master shfs") and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 250 251 **Hint 1** 252 253 To minimize the number of operations, it is necessary to leave as many elements as possible in the original array. What are these elements? 254 255 **Hint 2** 256 257 These elements must form the initial array prefix and the final array subsequence. 258 259 **Hint 3** 260 261 What other condition needs to be imposed on the prefix so that additions can be used to obtain the final array? 262 263 **Solution** 264 265 Tutorial is loading... 266 267 **Implementation** 268 269 ``` 270 #include "bits/stdc++.h" 271 using namespace std; 272 273 void solve() { 274 int n, m; 275 cin >> n >> m; 276 vector<int> a(n * m + 1), b(n * m + 1); 277 vector<deque<int>> mat(n + 1, deque<int> (m)); 278 for (int i = 1; i <= n; i++) { 279 for (int j = 0; j < m; j++) { 280 int ind = j + 1 + (i - 1) * m; 281 mat[i][j] = ind; 282 cin >> a[ind]; 283 } 284 } 285 for (int i = 1; i <= n * m; i++) 286 cin >> b[i]; 287 map<int, int> mp; 288 for (int i = 1; i <= n * m; i++) 289 mp[b[i]] = i; 290 vector<int> s(n * m + 1), pos(n * m + 1, -1); 291 for (int i = 1; i <= n * m; i++) { 292 if (mp.find(a[i]) != mp.end()) 293 pos[i] = mp[a[i]]; 294 else 295 break; 296 } 297 pos[0] = 0; 298 int skipped = 0, pref = 0; 299 bool prev = true; 300 for (int i = 1; i <= n * m; i++) { 301 if (pos[i - 1] > pos[i]) 302 break; 303 int d = pos[i] - pos[i - 1] - 1; 304 if (prev) 305 skipped += d; 306 else if (d > 0) 307 break; 308 if (skipped >= m - 1) 309 prev = true; 310 else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0) 311 prev = true; 312 else 313 prev = false; 314 if (prev) 315 pref = i; 316 } 317 cout << n * m - pref << '\n'; 318 } 319 320 signed main() { 321 ios::sync_with_stdio(false); 322 cin.tie(nullptr); 323 int T = 1; 324 cin >> T; 325 while (T--) 326 solve(); 327 return 0; 328 } 329 ``` 330 331 ## [2059E2 - Stop Gaming (Hard Version)](/contest/2059/problem/E2 "Codeforces Round 1002 (Div. 2)") 332 333 Author [shfs](/profile/shfs "Candidate Master shfs") and developer is [yunetive29](/profile/yunetive29 "Master yunetive29") 334 335 **Solution** 336 337 Tutorial is loading... 338 339 **Implementation** 340 341 ``` 342 #include <bits/stdc++.h> 343 using namespace std; 344 345 #define eb emplace_back 346 #define int long long 347 #define all(x) x.begin(), x.end() 348 #define fi first 349 #define se second 350 351 const int INF = 1e9 + 1000; 352 353 struct segtree { 354 vector<pair<int, int>> tree; 355 vector<int> ass; 356 int size = 1; 357 358 void init(vector<int> &a) { 359 while (a.size() >= size) { 360 size <<= 1; 361 } 362 tree.assign(2 * size, {}); 363 ass.assign(2 * size, 0); 364 build(0, 0, size, a); 365 } 366 367 void build(int x, int lx, int rx, vector<int> &a) { 368 if (rx - lx == 1) { 369 tree[x].se = lx; 370 if (lx < a.size()) { 371 tree[x].fi = a[lx]; 372 } else { 373 tree[x].fi = INF; 374 } 375 return; 376 } 377 int m = (lx + rx) / 2; 378 build(2 * x + 1, lx, m, a); 379 build(2 * x + 2, m, rx, a); 380 tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]); 381 } 382 383 void push(int x, int lx, int rx) { 384 tree[x].fi += ass[x]; 385 if (rx - lx == 1) { 386 ass[x] = 0; 387 return; 388 } 389 ass[2 * x + 1] += ass[x]; 390 ass[2 * x + 2] += ass[x]; 391 ass[x] = 0; 392 } 393 394 void update(int l, int r, int val, int x, int lx, int rx) { 395 push(x, lx, rx); 396 if (l <= lx && rx <= r) { 397 ass[x] += val; 398 push(x, lx, rx); 399 return; 400 } 401 if (rx <= l || r <= lx) { 402 return; 403 } 404 int m = (lx + rx) / 2; 405 update(l, r, val, 2 * x + 1, lx, m); 406 update(l, r, val, 2 * x + 2, m, rx); 407 tree[x] = min(tree[2 * x + 1], tree[2 * x + 2]); 408 } 409 410 void update(int l, int r, int val) { 411 update(l, r + 1, val, 0, 0, size); 412 } 413 414 int req(int x, int lx, int rx) { 415 push(x, lx, rx); 416 if (rx - lx == 1) { 417 return tree[x].se; 418 } 419 int m = (lx + rx) / 2; 420 push(2 * x + 1, lx, m); 421 push(2 * x + 2, m, rx); 422 if (tree[2 * x + 2].fi == 0) { 423 return req(2 * x + 2, m, rx); 424 } else { 425 return req(2 * x + 1, lx, m); 426 } 427 } 428 429 int req() { 430 return req(0, 0, size); 431 } 432 }; 433 434 void solve() { 435 int n, m; 436 cin >> n >> m; 437 vector<int> a(n * m + 1), b(n * m + 1); 438 for (int i = 1; i <= n; i++) { 439 for (int j = 0; j < m; j++) { 440 int ind = j + 1 + (i - 1) * m; 441 cin >> a[ind]; 442 } 443 } 444 for (int i = 1; i <= n * m; i++) 445 cin >> b[i]; 446 map<int, int> mp; 447 for (int i = 1; i <= n * m; i++) 448 mp[b[i]] = i; 449 vector<int> s(n * m + 1), pos(n * m + 1, -1); 450 for (int i = 1; i <= n * m; i++) { 451 if (mp.find(a[i]) != mp.end()) 452 pos[i] = mp[a[i]]; 453 else 454 break; 455 } 456 pos[0] = 0; 457 int skipped = 0, pref = 0; 458 bool prev = true; 459 for (int i = 1; i <= n * m; i++) { 460 if (pos[i - 1] > pos[i]) 461 break; 462 int d = pos[i] - pos[i - 1] - 1; 463 if (prev) 464 skipped += d; 465 else if (d > 0) 466 break; 467 if (skipped >= m - 1) 468 prev = true; 469 else if ((i - 1) % m > (i + skipped - 1) % m || (i + skipped) % m == 0) 470 prev = true; 471 else 472 prev = false; 473 if (prev) 474 pref = i; 475 } 476 for (int i = 1; i <= pref; i++) { 477 s[i - 1] = pos[i] - pos[i - 1] - 1; 478 } 479 s[pref] = n * m - pos[pref]; 480 481 vector<pair<int, int>> ans; 482 483 int res = 0; 484 for (int i = 0; i <= n * m; i++) { 485 res += s[i]; 486 } 487 vector<int> ost(pref + 1); 488 for (int i = 1; i <= pref; i++) { 489 ost[i] = (m - i % m) % m; 490 } 491 for (int i = 0; i <= pref; i++) { 492 if (s[i] == 0) { 493 ost[i] = INF; 494 } 495 } 496 vector<int> gol(pref + 1); 497 gol[0] = 1; 498 for (int i = 1; i <= pref; i++) { 499 gol[i] = (i + m - 1) / m + 1; 500 } 501 502 segtree tree; 503 504 tree.init(ost); 505 506 for (int step = 0; step < res; step++) { 507 int chel = tree.req(); 508 ans.eb(gol[chel], b[pos[chel] + s[chel]]); 509 tree.update(chel + 1, pref, -1); 510 s[chel]--; 511 if (s[chel] == 0) { 512 tree.update(chel, chel, INF); 513 } 514 } 515 516 cout << ans.size() << '\n'; 517 for (auto [i, col] : ans) { 518 cout << i << " " << col << '\n'; 519 } 520 } 521 522 signed main() { 523 //cout << fixed << setprecision(5); 524 ios::sync_with_stdio(false); 525 cin.tie(nullptr); 526 int T = 1; 527 cin >> T; 528 //cin >> G; 529 while (T--) 530 solve(); 531 return 0; 532 } 533 ```