1980.md (12394B)
1 Source: https://codeforces.com/blog/entry/130135 2 3 [1980A - Problem Generator](/contest/1980/problem/A "Codeforces Round 950 (Div. 3)") 4 5 Idea: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 def solve(): 15 n, m = map(int, input().split()) 16 a = input() 17 ans = 0 18 for ch in range(ord('A'), ord('H')): 19 ans += max(0, m - a.count(chr(ch))) 20 print(ans) 21 22 23 for _ in range(int(input())): 24 solve() 25 ``` 26 27 [1980B - Choosing Cubes](/contest/1980/problem/B "Codeforces Round 950 (Div. 3)") 28 29 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 30 31 **Tutorial** 32 33 Tutorial is loading... 34 35 **Solution** 36 37 ``` 38 def solve(): 39 n, f, k = map(int, input().split()) 40 f -= 1 41 k -= 1 42 a = list(map(int, input().split())) 43 x = a[f] 44 a.sort(reverse=True) 45 if a[k] > x: 46 print("NO") 47 elif a[k] < x: 48 print("YES") 49 else: 50 print("YES" if k == n - 1 or a[k + 1] < x else "MAYBE") 51 52 t = int(input()) 53 for _ in range(t): 54 solve() 55 ``` 56 57 [1980C - Sofia and the Lost Operations](/contest/1980/problem/C "Codeforces Round 950 (Div. 3)") 58 59 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40") 60 61 **Tutorial** 62 63 Tutorial is loading... 64 65 **Solution** 66 67 ``` 68 #include <stdio.h> 69 #include <stdbool.h> 70 71 #define MAXN 200200 72 #define MAXM 200200 73 74 int n, m, k; 75 int arr[MAXN], brr[MAXN], drr[MAXM], buf[MAXN]; 76 77 int cmp_i32(const void* pa, const void* pb) { 78 return *(const int*)pa - *(const int*)pb; 79 } 80 81 void build() { 82 k = 0; 83 for (int i = 0; i < n; ++i) { 84 if (arr[i] != brr[i]) 85 buf[k++] = brr[i]; 86 } 87 qsort(buf, k, sizeof(*buf), cmp_i32); 88 } 89 90 bool check() { 91 for (int i = 0; i < n; ++i) 92 if (brr[i] == drr[m - 1]) 93 return true; 94 return false; 95 } 96 97 bool solve() { 98 if (!check()) return false; 99 qsort(drr, m, sizeof(*drr), cmp_i32); 100 int ib = 0, id = 0; 101 while (ib < k && id < m) { 102 if (buf[ib] == drr[id]) 103 ++ib, ++id; 104 else if (buf[ib] < drr[id]) 105 return false; 106 else ++id; 107 } 108 return ib == k; 109 } 110 111 int main() { 112 int t; scanf("%d", &t); 113 while (t--) { 114 scanf("%d", &n); 115 for (int i = 0; i < n; ++i) 116 scanf("%d", arr + i); 117 for (int i = 0; i < n; ++i) 118 scanf("%d", brr + i); 119 scanf("%d", &m); 120 for (int j = 0; j < m; ++j) 121 scanf("%d", drr + j); 122 build(); 123 if (solve()) printf("YES\n"); 124 else printf("NO\n"); 125 } 126 } 127 ``` 128 129 [1980D - GCD-sequence](/contest/1980/problem/D "Codeforces Round 950 (Div. 3)") 130 131 Idea: [myav](/profile/myav "Pupil myav") Prepared by: [myav](/profile/myav "Pupil myav") 132 133 **Tutorial** 134 135 Tutorial is loading... 136 137 **Solution** 138 139 ``` 140 #include <bits/stdc++.h> 141 using namespace std; 142 143 bool good(vector<int>&b){ 144 int g = __gcd(b[0], b[1]); 145 for(int i = 1; i < int(b.size()) - 1; i++){ 146 int cur_gcd = __gcd(b[i], b[i + 1]); 147 if(g > cur_gcd) return false; 148 g = cur_gcd; 149 } 150 return true; 151 } 152 153 bool solve(){ 154 int n; 155 cin >> n; 156 vector<int>a(n); 157 for(int i = 0; i < n; i++){ 158 cin >> a[i]; 159 } 160 161 int g = -1; 162 int to_del = -1; 163 for(int i = 0; i < n - 1; i++){ 164 int cur_gcd = __gcd(a[i], a[i + 1]); 165 if(cur_gcd < g){ 166 to_del = i; 167 break; 168 } 169 g = cur_gcd; 170 } 171 if(to_del == -1) return true; 172 vector<int>b0 = a, b1 = a, b2 = a; 173 if(to_del > 0) b0.erase(b0.begin() + to_del - 1); 174 b1.erase(b1.begin() + to_del); 175 if(to_del < n - 1) b2.erase(b2.begin() + to_del + 1); 176 return good(b0) || good(b1) || good(b2); 177 } 178 179 int main(){ 180 int t; 181 cin >> t; 182 while(t--){ 183 cout << (solve() ? "YES" : "NO") << "\n"; 184 } 185 } 186 ``` 187 188 [1980E - Permutation of Rows and Columns](/contest/1980/problem/E "Codeforces Round 950 (Div. 3)") 189 190 Idea: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") Prepared by: [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 191 192 **Tutorial** 193 194 Tutorial is loading... 195 196 **Solution** 197 198 ``` 199 #include <iostream> 200 #include <vector> 201 #include <algorithm> 202 #include <set> 203 204 using namespace std; 205 206 typedef long long ll; 207 typedef vector<int> vi; 208 typedef vector<vi> vvi; 209 210 vi read_ints(int n) { 211 vi res(n); 212 for (int i = 0; i < n; ++i) { 213 cin >> res[i]; 214 } 215 return res; 216 } 217 218 vvi read_matrix(int n, int m) { 219 vvi res(n); 220 for (int i = 0; i < n; ++i) { 221 res[i] = read_ints(m); 222 } 223 return res; 224 } 225 226 void solve() { 227 int n, m; 228 cin >> n >> m; 229 vvi a = read_matrix(n, m), b = read_matrix(n, m); 230 int nm = n * m; 231 vi pos1i(nm), pos2i(nm), pos1j(nm), pos2j(nm); 232 for (int i = 0; i < n; ++i) { 233 for (int j = 0; j < m; ++j) { 234 int x = a[i][j] - 1; 235 int y = b[i][j] - 1; 236 pos1i[x] = pos2i[y] = i; 237 pos1j[x] = pos2j[y] = j; 238 } 239 } 240 vector<set<int>> pi(nm), pj(nm); 241 for (int x = 0; x < nm; ++x) { 242 int i1 = pos1i[x], i2 = pos2i[x]; 243 int j1 = pos1j[x], j2 = pos2j[x]; 244 pi[i1].insert(i2); 245 pj[j1].insert(j2); 246 } 247 for (int x = 0; x < nm; ++x) { 248 if (pi[x].size() > 1 || pj[x].size() > 1) { 249 cout << "NO\n"; 250 return; 251 } 252 } 253 cout << "YES\n"; 254 } 255 256 int main() { 257 int t; 258 cin >> t; 259 for (int _ = 0; _ < t; ++_) { 260 solve(); 261 } 262 return 0; 263 } 264 ``` 265 266 [1980F1 - Field Division (easy version)](/contest/1980/problem/F1 "Codeforces Round 950 (Div. 3)") 267 268 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 269 270 **Tutorial** 271 272 Tutorial is loading... 273 274 **Solution** 275 276 ``` 277 #include <bits/stdc++.h> 278 279 #define int long long 280 #define pb emplace_back 281 #define mp make_pair 282 #define x first 283 #define y second 284 #define all(a) a.begin(), a.end() 285 #define rall(a) a.rbegin(), a.rend() 286 287 typedef long double ld; 288 typedef long long ll; 289 290 using namespace std; 291 292 mt19937 rnd(time(nullptr)); 293 294 const ll inf = 1e9 + 1; 295 const ll M = 998244353; 296 const ld pi = atan2(0, -1); 297 const ld eps = 1e-6; 298 299 bool cmp(pair<int, int> &a, pair<int, int> &b){ 300 if(a.x != b.x) return a.x > b.x; 301 return a.y < b.y; 302 } 303 304 void solve(int tc){ 305 int n, m, k; 306 cin >> n >> m >> k; 307 vector<pair<int, int>> a(k); 308 map<pair<int, int>, int> idx; 309 for(int i = 0; i < k; ++i){ 310 cin >> a[i].x >> a[i].y; 311 idx[a[i]] = i; 312 } 313 sort(all(a), cmp); 314 vector<int> ans(k); 315 int total = 0; 316 int cur = m + 1; 317 int last = n; 318 for(auto e: a){ 319 if(cur > e.y) { 320 ans[idx[e]] = 1; 321 total += (cur - 1) * (last - e.x); 322 cur = e.y; 323 last = e.x; 324 } 325 } 326 total += (cur - 1) * last; 327 cout << total << "\n"; 328 for(int e: ans) cout << e << " "; 329 } 330 331 bool multi = true; 332 333 signed main() { 334 int t = 1; 335 if (multi)cin >> t; 336 for (int i = 1; i <= t; ++i) { 337 solve(i); 338 cout << "\n"; 339 } 340 return 0; 341 } 342 ``` 343 344 [1980F2 - Field Division (hard version)](/contest/1980/problem/F2 "Codeforces Round 950 (Div. 3)") 345 346 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") Prepared by: [Vladosiya](/profile/Vladosiya "Candidate Master Vladosiya") 347 348 **Tutorial** 349 350 Tutorial is loading... 351 352 **Solution** 353 354 ``` 355 #include <bits/stdc++.h> 356 357 #define int long long 358 #define pb emplace_back 359 #define mp make_pair 360 #define x first 361 #define y second 362 #define all(a) a.begin(), a.end() 363 #define rall(a) a.rbegin(), a.rend() 364 365 typedef long double ld; 366 typedef long long ll; 367 368 using namespace std; 369 370 mt19937 rnd(time(nullptr)); 371 372 const ll inf = 1e9 + 1; 373 const ll M = 998244353; 374 const ld pi = atan2(0, -1); 375 const ld eps = 1e-6; 376 377 bool cmp(pair<int, int> &a, pair<int, int> &b){ 378 if(a.x != b.x) return a.x > b.x; 379 return a.y < b.y; 380 } 381 382 void solve(int tc){ 383 int n, m, k; 384 cin >> n >> m >> k; 385 vector<pair<int, int>> a(k); 386 map<pair<int, int>, int> idx; 387 for(int i = 0; i < k; ++i){ 388 cin >> a[i].x >> a[i].y; 389 idx[a[i]] = i; 390 } 391 idx[{0, 0}] = k++; 392 a.emplace_back(0, 0); 393 sort(all(a), cmp); 394 vector<int> ans(k); 395 vector<int> total(k + 1), cur(k + 1, m + 1), last(k + 1, n); 396 for(int i = 1; i <= k; ++i){ 397 auto e = a[i - 1]; 398 total[i] = total[i - 1]; 399 cur[i] = cur[i - 1]; 400 last[i] = last[i - 1]; 401 if(cur[i] > e.y) { 402 ans[idx[e]] = 1; 403 total[i] += (cur[i] - 1) * (last[i] - e.x); 404 cur[i] = e.y; 405 last[i] = e.x; 406 } 407 } 408 cout << total[k] << "\n"; 409 for(int i = 1; i <= k; ++i){ 410 auto e = a[i - 1]; 411 if(ans[idx[e]] == 0)continue; 412 int tot = total[i - 1]; 413 int cr = cur[i - 1]; 414 int lst = last[i - 1]; 415 for(int j = i + 1; j <= k; ++j){ 416 auto ee = a[j - 1]; 417 if(cr > ee.y){ 418 tot += (cr - 1) * (lst - ee.x); 419 cr = ee.y; 420 lst = ee.x; 421 } 422 if(ans[idx[ee]] == 1){ 423 ans[idx[e]] = tot - total[j]; 424 break; 425 } 426 } 427 } 428 ans.pop_back(); 429 for(int e: ans) cout << e << " "; 430 } 431 432 bool multi = true; 433 434 signed main() { 435 int t = 1; 436 if (multi)cin >> t; 437 for (int i = 1; i <= t; ++i) { 438 solve(i); 439 cout << "\n"; 440 } 441 return 0; 442 } 443 ``` 444 445 [1980G - Yasya and the Mysterious Tree](/contest/1980/problem/G "Codeforces Round 950 (Div. 3)") 446 447 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") Prepared by: [Gornak40](/profile/Gornak40 "Expert Gornak40") 448 449 **Tutorial** 450 451 Tutorial is loading... 452 453 **Solution** 454 455 ``` 456 #include <bits/stdc++.h> 457 using namespace std; 458 459 struct trie { 460 int l, c; 461 vector<array<int, 2>> node; 462 vector<int> cnt; 463 trie(int l, int max_members) : l(l), c(0), node((l + 2) * max_members + 3), cnt((l + 2) * max_members + 3) {} 464 void add(int x) { 465 int cur = 0; 466 for (int i = l; i >= 0; --i) { 467 bool has_bit = (1 << i) & x; 468 if (!node[cur][has_bit]) { 469 node[cur][has_bit] = ++c; 470 } 471 cur = node[cur][has_bit]; 472 ++cnt[cur]; 473 } 474 } 475 void remove(int x) { 476 int cur = 0; 477 for (int i = l; i >= 0; --i) { 478 bool has_bit = (1 << i) & x; 479 if (!node[cur][has_bit]) { 480 node[cur][has_bit] = ++c; 481 } 482 cur = node[cur][has_bit]; 483 --cnt[cur]; 484 } 485 } 486 int find_max(int x) { 487 int cur = 0, ans = 0; 488 for (int i = l; i >= 0; --i) { 489 bool has_bit = (1 << i) & x; 490 if (node[cur][!has_bit] && cnt[node[cur][!has_bit]]) { 491 ans += 1 << i; 492 cur = node[cur][!has_bit]; 493 } 494 else { 495 cur = node[cur][has_bit]; 496 } 497 } 498 return ans; 499 } 500 }; 501 502 const int N = 2e5 + 2; 503 int x[N]; 504 bitset<N> dp; 505 vector<array<int, 2>> e[N]; 506 507 void dfs(int c, int p) { 508 for (auto [i, w] : e[c]) { 509 if (i == p) { 510 continue; 511 } 512 dp[i] = !dp[c]; 513 x[i] = x[c] ^ w; 514 dfs(i, c); 515 } 516 } 517 518 void solve() { 519 int n, m, gx = 0; 520 cin >> n >> m; 521 for (int i = 1; i <= n; ++i) { 522 e[i].clear(); 523 } 524 for (int i = 1, u, v, w; i < n; ++i) { 525 cin >> u >> v >> w; 526 e[u].push_back({v, w}); 527 e[v].push_back({u, w}); 528 } 529 dfs(1, 0); 530 vector<trie> t(2, trie(30, n)); 531 for (int i = 1; i <= n; ++i) { 532 t[dp[i]].add(x[i]); 533 } 534 while (m--) { 535 char c; 536 cin >> c; 537 if (c == '^') { 538 int y; 539 cin >> y; 540 gx ^= y; 541 } 542 else { 543 int a, b; 544 cin >> a >> b; 545 t[dp[a]].remove(x[a]); 546 int same_group = t[dp[a]].find_max(x[a] ^ b); 547 int diff_group = t[1 - dp[a]].find_max(x[a] ^ b ^ gx); 548 t[dp[a]].add(x[a]); 549 cout << max(same_group, diff_group) << "\n"; 550 } 551 } 552 } 553 554 int main() { 555 ios_base::sync_with_stdio(0); cin.tie(0); 556 int t; 557 cin >> t; 558 while (t--) { 559 solve(); 560 } 561 return 0; 562 } 563 ```