1847.md (17425B)
1 Source: https://codeforces.com/blog/entry/117928 2 3 [1847:A — The Man who became a God](https://codeforces.com/contest/1847/problem/A) 4 5 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus") 6 7 **tutorial** 8 9 Tutorial is loading... 10 11 **solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 using namespace std; 16 #define ll long long 17 #define ull unsigned long long 18 #define pb(e) push_back(e) 19 #define sv(a) sort(a.begin(),a.end()) 20 #define sa(a,n) sort(a,a+n) 21 #define mp(a,b) make_pair(a,b) 22 #define all(x) x.begin(),x.end() 23 24 void solve(){ 25 int n , k; 26 cin >> n >> k; 27 ll arr[n]; 28 for(int i = 0; i < n; i++)cin >> arr[i]; 29 vector<ll> v; 30 ll sum = 0; 31 for(int i = 1; i < n; i++){ 32 v.pb(abs(arr[i] - arr[i-1])); 33 sum += v.back(); 34 } 35 sort(all(v)); 36 for(int groups = 1; groups < k; groups++){ 37 sum -= v.back(); 38 v.pop_back(); 39 } 40 cout << sum << '\n'; 41 } 42 43 int main(){ 44 ios_base::sync_with_stdio(false); 45 cin.tie(NULL); 46 int t;cin >> t;while(t--) 47 solve(); 48 return 0; 49 } 50 ``` 51 52 [1847:B — Hamon Odyssey](https://codeforces.com/contest/1847/problem/B) 53 54 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus") 55 56 **tutorial** 57 58 Tutorial is loading... 59 60 **solution** 61 62 ``` 63 #include <iostream> 64 #include <vector> 65 using namespace std; 66 #define ll long long 67 #define ull unsigned long long 68 #define pb(e) push_back(e) 69 #define sv(a) sort(a.begin(),a.end()) 70 #define sa(a,n) sort(a,a+n) 71 #define mp(a,b) make_pair(a,b) 72 #define all(x) x.begin(),x.end() 73 74 void solve(){ 75 int n; 76 cin >> n; 77 int arr[n]; 78 for(int i = 0; i < n; i++)cin >> arr[i]; 79 int cur = arr[0]; 80 int part = 1; 81 for(int i = 0; i < n; i++){ 82 cur &= arr[i]; 83 if(cur == 0){ 84 if(i == n-1)break; 85 part++; 86 cur = arr[i + 1]; 87 } 88 } 89 if(cur != 0)part--; 90 part = max(part,1); 91 cout << part << '\n'; 92 } 93 94 int main(){ 95 ios_base::sync_with_stdio(false); 96 cin.tie(NULL); 97 int t;cin >> t;while(t--) 98 solve(); 99 return 0; 100 } 101 ``` 102 103 [1847:C-Vampiric Powers, anyone?](https://codeforces.com/contest/1847/problem/C) 104 105 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus") 106 107 **tutorial** 108 109 ### [1847C — Vampiric Powers, anyone?](https://codeforces.com/contest/1847/problem/C) 110 111 At the end of the array, you can only achieve xor of any subarray of the original array. 112 113 **proof** 114 115 Lets denote $f(u,v) =$ xor of all $a_i$ such that $min(u,v) \leq i \lt max(u,v)$. In the first operation you add $f(n,i)$. I.e. $[u_1,v_1)=[n,i)$. It can be proven that $f(u_k,v_k) = f(v_{k-1},v_k)$ in the $k$-th operation which is a range. 116 117 **proof** 118 119 Suppose we have taken $k$ ranges that already satisfy this property. Now, I add a new $k+1$-th range. So, first I need to take the $k$-th range $f(u_k,v_k)$. Now I'm xoring it with the range $f(u_{k - 1}, v_{k - 1})$. As [ $u_k, v_k$) and [ $u_{k - 1}, v_{k - 1}$) share an endpoint, the result for these ranges will be a range. 120 121 **proof** 122 123 For two ranges $f(x,y)$ and $f(y,z)$, if the two ranges do not intersect, the result will be the sum of the two ranges $f(x,z)$. If the two ranges intersect, then the intersections will be cancelled out, and the result will be the difference $f(x,z)$. 124 125 Now, we maintain a boolean array $b$ where $b_i$ is $1$ if there is some $j$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_j = i$. Initially, $b$ is all $0$. We loop $j$ from $1$ to $n$ and check for each $k$ if $b_k=1$. If it is, then there is some position $p \lt j$ such that $a_1 \oplus a_2 \oplus \cdots \oplus a_p = k$. If we take xor of range from $(p,j]$, then it will be $k \oplus a_1 \oplus a_2 \oplus \cdots \oplus a_j$ (as $a_1 \oplus a_2 \oplus \cdots \oplus a_p$ gets cancelled). This $a_1 \oplus a_2 \oplus \cdots \oplus a_j$ can be stored as we loop ahead. We are looping all possible prefix xors and not all prefix positions because $n$ is large. 126 127 Time Complexity — $O(n \cdot 2^8)$. 128 129 **solution** 130 131 ``` 132 #include <bits/stdc++.h> 133 using namespace std; 134 135 int main() { 136 cin.tie(0)->sync_with_stdio(0); 137 int ntest; 138 cin >> ntest; 139 while (ntest--) { 140 int n; 141 cin >> n; 142 vector<int> a(n); 143 for (auto &i : a) 144 cin >> i; 145 146 int const max_value = 1 << 8; 147 vector<char> has_pref(max_value); 148 has_pref[0] = true; 149 int cur_xor = 0; 150 int ans = 0; 151 for (auto i : a) { 152 cur_xor ^= i; 153 for (int pref = 0; pref < max_value; ++pref) { 154 if (has_pref[pref]) { 155 ans = max(ans, pref ^ cur_xor); 156 } 157 } 158 has_pref[cur_xor] = true; 159 } 160 161 cout << ans << '\n'; 162 } 163 } 164 ``` 165 166 [1847:D Professor Higashikata](https://codeforces.com/contest/1847/problem/D) 167 168 * Author — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus") 169 170 **tutorial** 171 172 Tutorial is loading... 173 174 **solution** 175 176 ``` 177 #include <bits/stdc++.h> 178 using namespace std; 179 #define ll long long 180 #define ull unsigned long long 181 #define pb(e) push_back(e) 182 #define sv(a) sort(a.begin(),a.end()) 183 #define sa(a,n) sort(a,a+n) 184 #define mp(a,b) make_pair(a,b) 185 #define vf first 186 #define vs second 187 #define all(x) x.begin(),x.end() 188 189 void solve(){ 190 int n , m , q; 191 cin >> n >> m >> q; 192 string st; 193 cin >> st; 194 vector<pair<int,int>> ranges; 195 for(int i = 0; i < m; i++){ 196 int l , r; 197 cin >> l >> r; 198 l--; 199 r--; 200 ranges.pb(mp(l,r)); 201 } 202 set<int> s; 203 for(int i = 0; i < n; i++)s.insert(i); 204 vector<int> v; 205 int pos_in_v[n]; 206 memset(pos_in_v,-1,sizeof pos_in_v); 207 for(int i = 0; i < m; i++){ 208 auto it = s.lower_bound(ranges[i].vf); 209 vector<int> toerase; 210 while(it != s.end() && (*it) <= ranges[i].vs){ 211 toerase.pb((*it)); 212 v.pb(toerase.back()); 213 pos_in_v[toerase.back()] = v.size()-1; 214 it++; 215 } 216 while(toerase.size()){ 217 s.erase(toerase.back()); 218 toerase.pop_back(); 219 } 220 } 221 int cnt = 0; 222 for(int i = 0; i < n; i++){ 223 if(st[i] == '1')cnt++; 224 } 225 int ans = 0; 226 for(int i = 0; i < min(cnt , (int)v.size()); i++){ 227 if(st[v[i]] == '0')ans++; 228 } 229 230 while(q--){ 231 int pos; 232 cin >> pos; 233 pos--; 234 if(pos_in_v[pos] != -1 && pos_in_v[pos] < cnt){ 235 if(st[pos] == '0'){ 236 ans--; 237 } 238 else ans++; 239 } 240 if(st[pos] == '0'){ 241 st[pos] = '1'; 242 cnt++; 243 if(cnt <= v.size() && st[v[cnt-1]] == '0')ans++; 244 } 245 else { 246 st[pos] = '0'; 247 if(cnt > 0 && cnt <= v.size() && st[v[cnt-1]] == '0')ans--; 248 cnt--; 249 } 250 cout << ans << '\n'; 251 } 252 } 253 254 int main(){ 255 ios_base::sync_with_stdio(false); 256 cin.tie(NULL); 257 //int t;cin >> t;while(t--) 258 solve(); 259 return 0; 260 } 261 ``` 262 263 [1847:E Triangle Platinum?](https://codeforces.com/contest/1847/problem/E) 264 265 * Author — [StArChAn](/profile/StArChAn "Эксперт StArChAn") 266 267 **tutorial** 268 269 Tutorial is loading... 270 271 **deterministic solution** 272 273 ``` 274 #include<bits/stdc++.h> 275 using namespace std; 276 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 277 int n, ans[5005], holy[10][10][10]; 278 map<vector<int>, int> GG; 279 int area(int x, int y, int z) 280 { 281 int ok = max(x, max(y, z)); 282 int sum = x+y+z; 283 if(2*ok >= sum) return 0; 284 return sum*(sum-2*x)*(sum-2*y)*(sum-2*z); 285 } 286 int query(vector<int> v) 287 { 288 sort(v.begin(), v.end()); 289 if(GG.find(v) != GG.end()) return GG[v]; 290 cout << "? " << v[0] << " " << v[1] << " " << v[2] << endl; 291 int ret; cin >> ret; assert(ret != -1); return GG[v] = ret; 292 } 293 void print(bool found = true) 294 { 295 if(!found) 296 { 297 cout << "! -1" << endl; 298 exit(0); 299 } 300 cout << "! "; 301 for(int i = 1; i <= n; i++) cout << ans[i] << " "; 302 cout << endl; exit(0); 303 } 304 bool works() 305 { 306 for(int i = 1; i <= n; i++) 307 { 308 for(int j = i+1; j <= n; j++) 309 { 310 for(int k = j+1; k <= n; k++) 311 { 312 if(area(ans[i], ans[j], ans[k]) != holy[i][j][k]) 313 return false; 314 } 315 } 316 } 317 return true; 318 } 319 void brute() 320 { 321 for(int i = 1; i <= n; i++) 322 { 323 for(int j = i+1; j <= n; j++) 324 { 325 for(int k = j+1; k <= n; k++) 326 holy[i][j][k] = query({i, j, k}); 327 } 328 } 329 int mask = 1<<(2*n); 330 int lol = 0; 331 int workser = -1; 332 for(int i = 0; i < mask; i++) 333 { 334 int copy = i; 335 for(int k = 1; k <= n; k++) 336 { 337 ans[k] = 1+copy%4; 338 copy/=4; 339 } 340 if(works()) 341 { 342 workser = i; 343 lol++; 344 } 345 } 346 assert(lol); 347 if(lol > 1) print(false); 348 int copy = workser; 349 for(int k = 1; k <= n; k++) 350 { 351 ans[k] = 1+copy%4; 352 copy/=4; 353 } 354 print(); 355 } 356 357 signed main() 358 { 359 ios_base::sync_with_stdio(false); cin >> n; 360 if(n <= 8) brute(); 361 map<int, int> nice; 362 for(int i = 1; i <= 4; i++) nice[area(i, i, i)] = i; 363 int a, b, X; 364 365 { 366 bool found = false; 367 for(int i = 1; i <= min(n, 9) && !found; i++) 368 { 369 for(int j = i+1; j <= min(n, 9) && !found; j++) 370 { 371 for(int k = j+1; k <= min(n, 9) && !found; k++) 372 { 373 if(nice[query({i, j, k})]) 374 { 375 a = i; 376 b = j; 377 X = nice[query({i, j, k})]; 378 found = true; 379 } 380 } 381 } 382 } 383 } 384 if(X > 1) 385 { 386 map<int, int> ok; 387 for(int i = 1; i <= 4; i++) ok[area(i, X, X)] = i; 388 for(int i = 1; i <= n; i++) ans[i] = ((i==a) || (i==b))? X : ok[query({a, b, i})]; 389 print(); 390 return 0; 391 } 392 vector<int> non_ones; 393 for(int i = 1; i <= n; i++) 394 { 395 if(i == a || i == b || query({i, a, b})) 396 ans[i] = 1; 397 else 398 non_ones.push_back(i); 399 if(non_ones.size() == 4) break; 400 } 401 if(non_ones.empty()) print(); 402 map<int, int> ok; 403 for(int i = 2; i <= 4; i++) ok[area(1, i, i)] = i; 404 int x, y, Z; x = y = -1; Z = 0; 405 for(int i = 0; i < non_ones.size() && (Z == 0); i++) 406 { 407 for(int j = i+1; j < non_ones.size() && (Z == 0); j++) 408 { 409 if(ok[query({a, non_ones[i], non_ones[j]})]) 410 { 411 x = non_ones[i]; 412 y = non_ones[j]; 413 Z = ok[query({a, non_ones[i], non_ones[j]})]; 414 } 415 } 416 } 417 if(x == -1) print(false); 418 map<int, int> fin; ans[x] = ans[y] = Z; 419 for(int i = 1; i <= 4; i++) fin[area(Z, Z, i)] = i; 420 for(int i = 1; i <= n; i++) ans[i] = ans[i]? ans[i] : fin[query({x, y, i})]; 421 print(); 422 return 0; 423 } 424 ``` 425 426 **randomisation solution** 427 428 ``` 429 #include <bits/stdc++.h> 430 using namespace std; 431 #define int long long 432 #define INF (int)1e18 433 #define f first 434 #define s second 435 436 mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); 437 const int N = 5005; 438 int ans[N]; 439 int n; 440 int dp[5][5][5]; 441 int holy[11][11][11]; 442 443 int area(int a, int b, int c){ 444 if (a >= b + c) return 0; 445 if (b >= a + c) return 0; 446 if (c >= a + b) return 0; 447 448 int s = (a + b + c); 449 return s * (s - 2 * a) * (s - 2 * b) * (s - 2 * c); 450 } 451 452 int query(int a, int b, int c){ 453 cout << "? " << a << " " << b << " " << c << endl; 454 int ans; cin >> ans; 455 return ans; 456 } 457 458 void print(bool found = true){ 459 if (!found){ 460 cout << "! -1\n"; 461 exit(0); 462 } else { 463 cout << "! "; 464 for (int i = 1; i <= n; i++) cout << ans[i] << " "; 465 cout << endl; 466 exit(0); 467 } 468 } 469 470 bool works(){ 471 for (int i = 1; i <= n; i++){ 472 for (int j = i + 1; j <= n; j++){ 473 for (int k = j + 1; k <= n; k++){ 474 if (area(ans[i], ans[j], ans[k]) != holy[i][j][k]) 475 return false; 476 } 477 } 478 } 479 480 return true; 481 } 482 483 void brutesmall(){ 484 for (int i = 1; i <= n; i++){ 485 for (int j = i + 1; j <= n; j++){ 486 for (int k = j + 1; k <= n; k++){ 487 holy[i][j][k] = query(i, j, k); 488 } 489 } 490 } 491 492 int mask = 1 << (2 * n); 493 int lol = 0; 494 for (int i = 0; i < mask; i++){ 495 int copy = i; 496 497 for (int i = 1; i <= n; i++){ 498 ans[i] = 1 + copy % 4; 499 copy /= 4; 500 } 501 502 if (works()){ 503 lol++; 504 } 505 } 506 507 if (lol > 1) print(false); 508 509 for (int i = 0; i < mask; i++){ 510 int copy = i; 511 512 for (int i = 1; i <= n; i++){ 513 ans[i] = 1 + copy % 4; 514 copy /= 4; 515 } 516 517 if (works()){ 518 print(); 519 } 520 } 521 } 522 523 void Solve() 524 { 525 cin >> n; 526 527 for (int i = 1; i <= 4; i++){ 528 for (int j = 1; j <= 4; j++){ 529 for (int k = 1; k <= 4; k++){ 530 dp[i][j][k] = area(i, j, k); 531 } 532 } 533 } 534 535 if (n < 9){ 536 brutesmall(); 537 } 538 539 vector <int> tuple(4, -1); 540 while (true){ 541 if (tuple[0] != -1) break; 542 int p1 = 1 + RNG() % n; 543 int p2 = 1 + RNG() % n; 544 int p3 = 1 + RNG() % n; 545 546 if (p1 == p2 || p2 == p3 || p3 == p1) continue; 547 int ar = query(p1, p2, p3); 548 for (int j = 1; j <= 4; j++){ 549 if (ar == dp[j][j][j]){ 550 tuple[0] = p1; 551 tuple[1] = p2; 552 tuple[2] = p3; 553 tuple[3] = j; 554 } 555 } 556 } 557 558 for (int i = 0; i < 3; i++) ans[tuple[i]] = tuple[3]; 559 560 if (tuple[3] == 1){ 561 vector <int> nv; 562 for (int i = 1; i <= n; i++){ 563 if (ans[i] > 0) continue; 564 565 int fetch = query(tuple[0], tuple[1], i); 566 if (fetch == 0) { 567 nv.push_back(i); 568 if (nv.size() > 3) break; 569 } else { 570 ans[i] = 1; 571 } 572 } 573 574 if (nv.size() == 0) print(); 575 576 vector <int> ntuple(3, -1); 577 for (int i1 = 0; i1 < nv.size(); i1++){ 578 for (int i2 = i1 + 1; i2 < nv.size(); i2++){ 579 int ok = query(tuple[0], nv[i1], nv[i2]); 580 581 for (int j = 2; j <= 4; j++){ 582 if (ok == dp[1][j][j]){ 583 ntuple[0] = nv[i1]; 584 ntuple[1] = nv[i2]; 585 ntuple[2] = j; 586 } 587 } 588 } 589 } 590 591 if (ntuple[0] == -1) print(false); 592 ans[ntuple[0]] = ntuple[2]; 593 ans[ntuple[1]] = ntuple[2]; 594 595 tuple[0] = ntuple[0]; 596 tuple[1] = ntuple[1]; 597 tuple[2] = -1; 598 tuple[3] = ntuple[2]; 599 } 600 601 for (int i = 1; i <= n; i++){ 602 if (ans[i] > 0) continue; 603 604 int fetch = query(tuple[0], tuple[1], i); 605 for (int j = 1; j <= 4; j++){ 606 if (dp[tuple[3]][tuple[3]][j] == fetch) 607 ans[i] = j; 608 } 609 } 610 611 print(); 612 } 613 614 int32_t main() 615 { 616 auto begin = std::chrono::high_resolution_clock::now(); 617 ios_base::sync_with_stdio(0); 618 cin.tie(0); 619 int t = 1; 620 // cin >> t; 621 for(int i = 1; i <= t; i++) 622 { 623 Solve(); 624 } 625 return 0; 626 } 627 ``` 628 629 [1847:F The Boss's Identity](https://codeforces.com/contest/1847/problem/F) 630 631 * Idea — [astoria](/profile/astoria "Кандидат в мастера astoria") 632 * Prepared by — [PoPularPlusPlus](/profile/PoPularPlusPlus "Мастер PoPularPlusPlus") 633 634 **tutorial** 635 636 Tutorial is loading... 637 638 **solution** 639 640 ``` 641 #include <bits/stdc++.h> 642 using namespace std; 643 #define ll long long 644 #define ull unsigned long long 645 #define pb(e) push_back(e) 646 #define sv(a) sort(a.begin(),a.end()) 647 #define sa(a,n) sort(a,a+n) 648 #define mp(a,b) make_pair(a,b) 649 #define vf first 650 #define vs second 651 #define all(x) x.begin(),x.end() 652 653 const int B = 31; 654 655 struct item { 656 ll pos , bit, idx; 657 }; 658 659 item make(ll pos , ll bit , ll idx){ 660 item res; 661 res.pos = pos; 662 res.bit = bit; 663 res.idx = idx; 664 return res; 665 } 666 667 void solve(){ 668 int n; 669 cin >> n; 670 int qu; 671 cin >> qu; 672 int arr[n]; 673 for(int i = 0; i < n; i++)cin >> arr[i]; 674 if(n == 1){ 675 while(qu--){ 676 int x; 677 cin >> x; 678 if(x < arr[0])cout << 1 << '\n'; 679 else cout << -1 << '\n'; 680 } 681 return; 682 } 683 vector<pair<ll,ll>> v; 684 queue<item> q; 685 bool vis[n][B]; 686 memset(vis,0,sizeof vis); 687 for(int i = 0; i < n; i++){ 688 for(int j = 0; j < B; j++){ 689 if((arr[i] & (1 << j)) > 0){ 690 vis[i][j] = 1; 691 } 692 } 693 v.pb(mp(i , arr[i])); 694 } 695 for(int i = 0; i < n - 1; i++){ 696 v.pb(mp(n+i,arr[i]|arr[i+1])); 697 } 698 for(int j = 0; j < B; j++){ 699 if(vis[n-1][j])q.push(make(n+n-1,j,0)); 700 } 701 for(int i = 0; i < n - 1; i++){ 702 for(int j = 0; j < B; j++){ 703 if(vis[i][j])q.push(make(n+n+i,j,(i+1)%(n-1))); 704 } 705 } 706 int val[n-1]; 707 for(int i = 0; i < n-1; i++)val[i] = arr[i]|arr[i+1]; 708 while(q.size()){ 709 item it = q.front(); 710 q.pop(); 711 if((val[it.idx] & (1 << it.bit)) > 0){ 712 continue; 713 } 714 val[it.idx] += (1 << it.bit); 715 if(v.back().vf == it.pos){ 716 v.pop_back(); 717 } 718 v.pb(mp(it.pos , val[it.idx])); 719 q.push(make(it.pos + n , it.bit , (it.idx + 1)%(n-1))); 720 } 721 722 // first part gets over where v[i].first contains position in ascending order and v[i].second contains the value to what has become on that position. 723 724 725 for(int i = 1; i < v.size(); i++){ 726 v[i].vs = max(v[i].vs , v[i-1].vs); 727 } 728 729 while(qu--){ 730 int x; 731 cin >> x; 732 ll l = 0 , r = v.size()-1; 733 ll res = -1; 734 while(l <= r){ 735 int mid = (l + r)/2; 736 if(v[mid].vs <= x){ 737 l = mid + 1; 738 } 739 else { 740 r = mid - 1; 741 res = v[mid].vf+1; 742 } 743 } 744 cout << res << '\n'; 745 } 746 } 747 748 int main(){ 749 ios_base::sync_with_stdio(false); 750 cin.tie(NULL); 751 int t;cin >> t;while(t--) 752 solve(); 753 return 0; 754 } 755 ```