1665.md (22508B)
1 Source: https://codeforces.com/blog/entry/101663 2 3 Again, I hope that you liked all the problems. Share your ideas and solutions in the comments, because there are always different ones! So, the editorial: 4 5 **A: GCD vs LCM** 6 7 [1665A - GCD vs LCM](/contest/1665/problem/A "Codeforces Round 781 (Div. 2)") 8 9 **Editorial** 10 11 In this problem it is enough to print $n - 3$, $1$, $1$, $1$. It is easy to see that this answer is correct for any $n \ge 4$. 12 13 **Implementation (C++, shishyando)** 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 int n; 24 cin >> n; 25 cout << n - 3 << ' ' << 1 << ' ' << 1 << ' ' << 1 << '\n'; 26 } 27 return 0; 28 } 29 ``` 30 31 **B: Array Cloning Technique** 32 33 [1665B - Array Cloning Technique](/contest/1665/problem/B "Codeforces Round 781 (Div. 2)") 34 35 **Editorial** 36 37 We will use a greedy technique. Let's find the most common element in the array. Let it be $x$ and let it occur $k$ times in the array. Then let's make a copy where all elements are $x$. To do that we can make a copy of the given array and put all $x$ in one array. Now we will repeat the algorithm for the new array until we get a copy with $n$ numbers $x$. 38 39 **Implementation (C++, shishyando)** 40 41 ``` 42 #include <bits/stdc++.h> 43 using namespace std; 44 45 int main() { 46 ios_base::sync_with_stdio(false); 47 cin.tie(nullptr); 48 cout.tie(nullptr); 49 int T; 50 cin >> T; 51 while (T --> 0) { 52 int n; 53 cin >> n; 54 map<int, int> q; 55 for (int i = 0; i < n; ++i) { 56 int x; 57 cin >> x; 58 ++q[x]; 59 } 60 int am = 0; 61 for (auto &[x, y] : q) { 62 am = max(am, y); 63 } 64 int ans = 0; 65 while (am < n) { 66 int d = min(n - am, am); 67 ans += 1 + d; 68 am += d; 69 } 70 cout << ans << '\n'; 71 } 72 return 0; 73 } 74 ``` 75 76 **C: Tree Infection** 77 78 [1665C - Tree Infection](/contest/1665/problem/C "Codeforces Round 781 (Div. 2)") 79 80 **Editorial** 81 82 Firstly, we can see that for any two different vertices, their children are independent. It means that infection can not spread from children of one vertex to children of another. Also it does not matter how the infection spreads among the children of some vertex, so we only need to know the amount of vertices with the same parent. 83 84 Using this knowledge we can reduce the problem to this one: You are given an array of $k$ positive integers, each integer denotes the amount of healthy vertices with the same parent. Each second you can infect an integer in this array (by injection). Also each second all infected integers decrease by 1 (because of spreading). 85 86 Let's now use a greedy algorithm. We will sort this array in the decreasing order and infect all integers one by one. These injections are always needed because the integers are independent. After that each second all numbers decrease by 1 and we can choose one number to be decreased once more in the same second. This should be the max number. 87 88 This problem can be solved by simulating the whole process, because the sum of all integers in the beginning is $n$. 89 90 **Implementation (C++, shishyando)** 91 92 ``` 93 #include <bits/stdc++.h> 94 using namespace std; 95 96 int ans; 97 98 void proc(vector<int>& a) { 99 if (a.empty()) return; 100 int n = a.size(); 101 int last = 0; 102 for (int i = 0; i < n; ++i) { 103 if (a[i] == a[0]) { 104 last = i; 105 } else { 106 break; 107 } 108 } 109 --a[last]; 110 for (int i = 0; i < n; ++i) --a[i]; 111 ++ans; 112 while (!a.empty() && a.back() <= 0) { 113 a.pop_back(); 114 } 115 proc(a); 116 } 117 118 int main() { 119 ios_base::sync_with_stdio(false); 120 cin.tie(nullptr); 121 cout.tie(nullptr); 122 int T; 123 cin >> T; 124 while (T --> 0) { 125 int n; 126 cin >> n; 127 vector<int> a(n); 128 ans = 0; 129 for (int i = 1; i < n; ++i) { 130 int x; 131 cin >> x; 132 ++a[--x]; 133 } 134 a.emplace_back(1); 135 sort(a.rbegin(), a.rend()); 136 while (!a.empty() && a.back() <= 0) a.pop_back(); 137 n = a.size(); 138 for (int i = 0; i < n; ++i) { 139 a[i] = a[i] - (n - i); 140 ++ans; 141 } 142 sort(a.rbegin(), a.rend()); 143 while (!a.empty() && a.back() <= 0) a.pop_back(); 144 proc(a); 145 cout << ans << '\n'; 146 } 147 return 0; 148 } 149 ``` 150 151 **D: GCD Guess** 152 153 [1665D - GCD Guess](/contest/1665/problem/D "Codeforces Round 781 (Div. 2)") 154 155 **Editorial** 156 157 **Solution 1** 158 159 Let's iteratively find the remainder of $x \bmod$ each power of $2$. Initially, we know that $x \bmod 2^0 = x \bmod 1 = 0$. If we know that $x \bmod 2^k = r$, then how do we find $x \bmod 2^{k + 1}$? To do that let's ask $\gcd(x + 2^k - r, 2^{k + 1}) = \gcd(x + 2^k - r, x + 2^k - r + 2^{k + 1})$. If $\gcd = 2^{k + 1}$, then $x \bmod 2^{k + 1} = r + 2^{k - 1}$ else $x \bmod 2^{k + 1} = r$. Using this algorithm we will find $x \bmod 2^{30}$ which is just $x$. It takes exactly $30$ queries. 160 161 **Solution 2** 162 163 Let's consider a set of pairwise coprime numbers ${23, 19, 17, 13, 11, 9, 7, 5, 4}$. Their $\text{lcm} \gt 10^9$ that's why $x \bmod \text{lcm} = x$. Let's find $x \bmod$ each of these numbers. To do that, for each $1 \le i \le 23$ we can ask $\gcd(x + i, x + \text{lcm} + i)$ (the query is $(i, \text{lcm} + i)$). If the $\gcd$ is a multiple of some number from our set then $x \bmod$ this number is $-i$. After that we can use the [chinese remainder theorem](https://en.wikipedia.org/wiki/Chinese_remainder_theorem) to find $x$ that gives the same remainders for numbers from the set. This solution asks only $23$ queries. 164 165 *Observation 1*: It's enough to make only $22$ queries, because if we did not find anything for $1 \le i \le 22$ then we can guarantee that $i = 23$ will do. 166 167 *Observation 2*: All moduli are small, that's why it is possible to use a simplified CRT (check the implementation). 168 169 **Implementation (C++, Artyom123)** 170 171 ``` 172 #include<bits/stdc++.h> 173 174 using namespace std; 175 176 int ask(int a, int b) { 177 cout << '?' << " " << a << " " << a + b << endl; 178 int ans; 179 cin >> ans; 180 return ans; 181 } 182 183 void solve() { 184 int r = 0; 185 for (int i = 1; i <= 30; i++) { 186 int ans = ask((1 << (i - 1)) - r, (1 << i)); 187 if (ans == (1 << i)) r += (1 << (i - 1)); 188 } 189 cout << '!' << " " << r << endl; 190 } 191 192 int main() { 193 int t; 194 cin >> t; 195 while (t--) solve(); 196 return 0; 197 } 198 ``` 199 200 **Implementation with CRT (C++, TheScrasse)** 201 202 ``` 203 #include <bits/stdc++.h> 204 using namespace std; 205 206 #define nl "\n" 207 #define nf endl 208 #define ll long long 209 #define pb push_back 210 #define _ << ' ' << 211 212 #define INF (ll)1e18 213 #define mod 998244353 214 #define maxn 110 215 #define lc 1338557220 216 217 ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b; 218 ll x, rs[maxn], p; 219 vector<ll> pw = {23, 19, 17, 13, 11, 9, 7, 5, 4}; 220 221 ll ask(ll a, ll b) { 222 cout << "?" _ a _ b << nf; 223 ll x; cin >> x; return x; 224 } 225 226 void clm(ll x) { 227 cout << "!" _ x << nf; 228 } 229 230 int main() { 231 ios::sync_with_stdio(0); 232 cin.tie(0); 233 234 /* #if !ONLINE_JUDGE && !EVAL 235 ifstream cin("input.txt"); 236 ofstream cout("output.txt"); 237 #endif */ 238 239 // kudos for automatic wa 240 241 cin >> t; 242 while (t--) { 243 for (i = 1; i <= 23; i++) { 244 k = ask(x + i, lc + i); 245 for (j = 0; j < 9; j++) { 246 if (k % pw[j] == 0) rs[j] = i % pw[j]; 247 } 248 } 249 250 k = 1; p = 1; 251 for (j = 0; j < 9; j++) { 252 // cout << "p =" _ p << nf; 253 while (p % pw[j] != rs[j]) p += k; 254 k *= pw[j]; 255 } 256 257 clm(lc - p); 258 } 259 260 return 0; 261 } 262 ``` 263 264 **E: MinimizOR** 265 266 [1665E - MinimizOR](/contest/1665/problem/E "Codeforces Round 781 (Div. 2)") 267 268 **Editorial** 269 270 The key idea for the solution is that the answer always lies among no more than 31 minimal numbers. According to this idea, it is possible to build a segment tree for minimum on a segment. After that we only need to find no more than 31 minimums on the segment (each time we find one we change it to $\infty$) and, finally, we can find all $OR$s pairwise among these 31 numbers. 271 272 It is also possible to use the Merge Sort Tree and the same idea. 273 274 Now let's prove the key idea: let's prove by induction that if all numbers are less than $2^k$ then it's enough to consider $k + 1$ minimal numbers. 275 276 **Base case**: $k=1$, all numbers are from $0$ to $1$ and the proof is obvious. 277 278 **Inductive step**: 279 280 Let's show that for any $k \ge 1$ if for $k$ the statement is true then it's true for $k + 1$. 281 282 If all numbers have 1 in $k$-th bit then the $k$-th bit of the answer is also 1, that's why we only have to minimize the remaining bits. For these bits we can apply the induction hypothesis that $k + 1$ minimal numbers are enough. If at least two numbers have 0 in their $k$-th bit then the $k$-th bit in the answer is also 0. That's why we only consider only numbers with 0 in $k$-th bit and we have to minimize the remaining bits. Again applying the induction hypothesis, $k + 1$ minimal numbers are enough. If there is exactly one number with 0 in $k$-th bit then the $k$-th bit in the answer is 1 and we have to find $k + 1$ minimal numbers over $k$ bits. They are among $k + 2$ minimal numbers over $k + 1$ bits, so $k + 2$ minimal numbers are enough. 283 284 **Implementation (C++, Artyom123)** 285 286 ``` 287 #include<bits/stdc++.h> 288 289 using namespace std; 290 291 const int MAXK = 31; 292 const int INF = (1 << 30); 293 294 vector<pair<int, int>> t; 295 296 pair<int, int> get(int v, int vl, int vr, int l, int r) { 297 if (vl >= l && vr <= r) return t[v]; 298 if (r <= vl || l >= vr) return make_pair(INF, INF); 299 int vm = (vl + vr) / 2; 300 return min(get(2 * v + 1, vl, vm, l, r), get(2 * v + 2, vm, vr, l, r)); 301 } 302 303 void mod(int v, int vl, int vr, int id, int val) { 304 if (vr - vl == 1) { 305 t[v] = make_pair(val, id); 306 return; 307 } 308 int vm = (vl + vr) / 2; 309 if (id < vm) mod(2 * v + 1, vl, vm, id, val); 310 else mod(2 * v + 2, vm, vr, id, val); 311 t[v] = min(t[2 * v + 1], t[2 * v + 2]); 312 } 313 314 void solve() { 315 int n; 316 cin >> n; 317 vector<int> a(n); 318 for (auto &c : a) cin >> c; 319 t.resize(4 * n); 320 for (int i = 0; i < n; i++) mod(0, 0, n, i, a[i]); 321 int q; 322 cin >> q; 323 while (q--) { 324 int l, r; 325 cin >> l >> r; 326 l--; 327 vector<pair<int, int>> b; 328 for (int i = 0; i < min(r - l, MAXK); i++) { 329 auto now = get(0, 0, n, l, r); 330 b.push_back(now); 331 mod(0, 0, n, now.second, INF); 332 } 333 int ans = (1LL << 31) - 1; 334 for (int i = 0; i < (int)b.size(); i++) { 335 for (int j = i + 1; j < (int)b.size(); j++) ans = min(ans, b[i].first | b[j].first); 336 } 337 for (auto &c : b) mod(0, 0, n, c.second, c.first); 338 cout << ans << "\n"; 339 } 340 } 341 342 int main() { 343 ios_base::sync_with_stdio(0); 344 cin.tie(0); 345 cout.tie(0); 346 int t; 347 cin >> t; 348 while (t--) solve(); 349 return 0; 350 } 351 ``` 352 353 **Other solutions (?)** 354 355 **MO's algorithm + van Emde Boas tree :) (C++, wery0)** 356 357 ``` 358 #pragma GCC optimize("Ofast") 359 // #pragma GCC target("avx,avx2,fma") 360 361 #include <bits/stdc++.h> 362 363 #define F first 364 #define S second 365 #define vec vector 366 #define pb push_back 367 #define cld complex<ld> 368 #define pll pair<ll, ll> 369 #define pdd pair<ld, ld> 370 #define umap unordered_map 371 #define uset unordered_set 372 #define pii pair<int, int> 373 #define pnn pair<Node*, Node*> 374 #define all(m) m.begin(), m.end() 375 #define uid uniform_int_distribution 376 #define fast cin.tie(0); cout.tie(0); cin.sync_with_stdio(0); cout.sync_with_stdio(0); 377 using namespace std; 378 using str = string; 379 using ll = long long; 380 using ld = long double; 381 using uint = unsigned int; 382 using ull = unsigned long long; 383 mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); 384 template<typename T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;} 385 template<typename T> bool chmax(T& a, const T& b) {return b > a ? a = b, 1 : 0;} 386 387 const uint NO = 1<<30; 388 template<unsigned K> 389 struct VebTree{ 390 uint mn, mx; 391 VebTree<(K>>1)> *m[1<<((K+1)>>1)]; 392 VebTree<((K+1)>>1)> *aux; 393 394 VebTree(){ 395 memset(m, 0, sizeof(m)); 396 aux = 0; 397 mn = mx = NO; 398 } 399 400 inline bool empty() const{ 401 return mx==NO; 402 } 403 404 inline uint high(uint x) const{ 405 return x>>(K>>1); 406 } 407 408 inline uint low(uint x) const{ 409 return x&((1<<(K>>1))-1); 410 } 411 412 inline uint merge(uint x, uint y) const{ 413 return (x<<(K>>1))+y; 414 } 415 416 bool find(uint x){ 417 if(x==mn || x==mx) return 1; 418 return m[high(x)] && m[high(x)]->find(low(x)); 419 } 420 421 void insert(uint x){ 422 if(mx==NO) mn = mx = x; 423 else if(mn==mx) mn = min(mn, x), mx = max(mx, x); 424 else if(x<mn || x>mx){ 425 uint add = x<mn ? mn : mx; 426 mn = min(mn, x); 427 mx = max(mx, x); 428 insert(add); 429 } 430 else if(K>1){ 431 uint hi = high(x), lo = low(x); 432 if(!m[hi]) m[hi] = new VebTree<(K>>1)>(); 433 if(m[hi]->empty()){ 434 if(!aux) aux = new VebTree<((K+1)>>1)>(); 435 aux->insert(hi); 436 } 437 m[hi]->insert(lo); 438 } 439 } 440 441 void rem(uint x){ 442 if(mn==mx){ 443 mn = mx = NO; 444 return; 445 } 446 if(x==mn){ 447 if(!aux || aux->empty()) {mn=mx; return;} 448 else mn = x = merge(aux->mn, m[aux->mn]->mn); 449 } 450 else if(x==mx){ 451 if(!aux || aux->empty()) {mx = mn; return;} 452 else mx = x = merge(aux->mx, m[aux->mx]->mx); 453 } 454 uint hi = high(x), lo = low(x); 455 m[hi]->rem(lo); 456 if(m[hi]->empty()) aux->rem(hi); 457 } 458 459 uint next(uint x){ 460 if(empty() || x>=mx) return NO; 461 if(x<mn) return mn; 462 if(K==1) return mx; 463 uint hi = high(x), lo = low(x); 464 if(m[hi] && !m[hi]->empty() && m[hi]->mx > lo) return merge(hi, m[hi]->next(lo)); 465 uint next_hi = aux ? aux->next(hi) : NO; 466 return next_hi==NO ? mx : merge(next_hi, m[next_hi]->mn); 467 } 468 469 uint prev(uint x){ 470 if(empty() || x<=mn) return NO; 471 if(x>mx) return mx; 472 if(K==1) return mn; 473 uint hi = high(x), lo = low(x); 474 if(m[hi] && !m[hi]->empty() && m[hi]->mn < lo) return merge(hi, m[hi]->prev(lo)); 475 uint prev_hi = aux ? aux->prev(hi) : NO; 476 return prev_hi==NO ? mn : merge(prev_hi, m[prev_hi]->mx); 477 } 478 }; 479 480 const int G = 1e5 + 5, SZB = 300; 481 int a, z; 482 int m[G], ans[G]; 483 int cng[G], cnt[G]; 484 array<int, 3> que[G]; 485 int cl, cr; 486 VebTree<32> veb, lox; 487 488 void add(int ps) { 489 int res = ++cnt[cng[ps]]; 490 if(res==1){ 491 veb.insert(m[ps]); 492 } 493 if(res==2){ 494 lox.insert(m[ps]); 495 } 496 } 497 498 void rem(int ps) { 499 int res = --cnt[cng[ps]]; 500 if(res==0){ 501 veb.rem(m[ps]); 502 } 503 if(res==1){ 504 lox.rem(m[ps]); 505 } 506 } 507 508 uint go() { 509 uint o = 0; 510 uint mn = NO; 511 vec<int> del; 512 for(int k=29; k>=0; k--){ 513 uint x = o+(1<<k); 514 uint cur = veb.prev(x), sz = 0; 515 if(cur!=NO && cur>=o){ 516 ++sz; 517 cur = veb.prev(cur); 518 if(cur!=NO && cur>=o){ 519 ++sz; 520 } 521 } 522 if(sz==0) o += 1<<k; 523 else if(sz==1){ 524 uint c = veb.prev(x)+(1<<k); 525 if(veb.find(c)) chmin(mn, c); 526 else { 527 veb.insert(c); 528 del.pb(c); 529 } 530 o += 1<<k; 531 } 532 } 533 for(uint i : del) veb.rem(i); 534 return min({mn, o, lox.mn}); 535 } 536 537 void compress(){ 538 vec<int> kek(a); 539 for(int q=0; q<a; q++) kek[q] = m[q]; 540 sort(all(kek)); 541 kek.erase(unique(all(kek)), kek.end()); 542 for(int q=0; q<a; q++){ 543 cng[q] = lower_bound(all(kek), m[q])-kek.begin(); 544 } 545 } 546 547 void solve() { 548 cin >> a; 549 for (int q = 0; q < a; q++) cin >> m[q]; 550 cin >> z; 551 for (int q = 0; q < z; q++) { 552 int l, r; cin >> l >> r; l--; r--; 553 que[q] = {l, r, q}; 554 } 555 sort(que, que + z, [](array<int, 3> & p1, array<int, 3> & p2) { 556 int l1 = p1[0] / SZB; 557 int l2 = p2[0] / SZB; 558 if (l1 != l2) return l1 < l2; 559 return l1 % 2 == 0 ? p1[1] < p2[1] : p1[1] > p2[1]; 560 }); 561 cl = cr = 0; 562 compress(); 563 fill(cnt, cnt+a, 0); 564 add(0); 565 for (int i = 0; i < z; i++) { 566 int ql = que[i][0]; 567 int qr = que[i][1]; 568 for (; cr + 1 <= qr; ) add(++cr); 569 for (; cl - 1 >= ql; ) add(--cl); 570 for (; cr > qr;) rem(cr--); 571 for (; cl < ql; ) rem(cl++); 572 ans[que[i][2]] = go(); 573 } 574 for(; cl<=cr;) rem(cr--); 575 for (int q = 0; q < z; q++) cout << ans[q] << "\n"; 576 } 577 578 int main() { 579 fast; 580 int z; cin >> z; 581 for (; z--;) { 582 solve(); 583 } 584 } 585 ``` 586 587 **DATA STRUCTURES!!! (C++, AlperenT)** 588 589 ``` 590 #include <bits/stdc++.h> 591 592 using namespace std; 593 594 const size_t MEMSIZE = 1e9 / 3.8; // in bytes 595 596 constexpr size_t MX_ALIGN = alignof(std::max_align_t); 597 char __attribute__((aligned(MX_ALIGN))) memory[MEMSIZE]; 598 size_t memorypos; 599 void * operator new(size_t n){ 600 if (memorypos + n >= MEMSIZE) { 601 memorypos = MEMSIZE / 3; 602 } 603 char *ret = memory + memorypos; 604 memorypos = size_t((memorypos+n+MX_ALIGN-1)&-MX_ALIGN); 605 return (void*)ret; 606 } 607 void operator delete(void *){} 608 void operator delete(void *, size_t){} 609 610 struct Node{ 611 int l, r, cnt, val; 612 613 Node *lptr = nullptr, *rptr = nullptr; 614 615 Node(int l, int r, int cnt = 0, int val = -1) : l(l), r(r), cnt(cnt), val(val){} 616 617 Node(Node* lptr, Node* rptr) : lptr(lptr), rptr(rptr) { 618 l = lptr->l, r = rptr->r; 619 620 cnt = lptr->cnt + rptr->cnt; 621 622 val = max(lptr->val, rptr->val); 623 } 624 625 void extend(){ 626 if(!lptr && l != r){ 627 int m = l + (r - l) / 2; 628 629 lptr = new Node(l, m); 630 rptr = new Node(m + 1, r); 631 } 632 } 633 634 pair<int, int> merge(pair<int, int> a, pair<int, int> b){ 635 return {a.first + b.first, max(a.second, b.second)}; 636 } 637 638 pair<int, int> query(int lq, int rq){ 639 if(lq > rq) return {0, -1}; 640 641 extend(); 642 643 if(lq == l && rq == r) return {cnt, val}; 644 else{ 645 int m = l + (r - l) / 2; 646 647 pair<int, int> a = lptr->query(lq, min(m, rq)), b = rptr->query(max(m + 1, lq), rq); 648 649 return merge(a, b); 650 } 651 } 652 }; 653 654 Node* update(Node* v, int k, int indx){ 655 v->extend(); 656 657 if(v->l == v->r) return new Node(v->l, v->r, v->cnt + 1, indx); 658 else{ 659 if(k <= v->lptr->r) return new Node(update(v->lptr, k, indx), v->rptr); 660 else return new Node(v->lptr, update(v->rptr, k, indx)); 661 } 662 } 663 664 const int N = 1e5 + 5; 665 666 int t, n, q, arr[N], l, r, curnum; 667 668 Node* roots[N]; 669 670 vector<int> vec; 671 672 pair<int, int> query(int l, int r, int lnum, int rnum){ 673 pair<int, int> p; 674 675 p.first = roots[r]->query(lnum, rnum).first - roots[l - 1]->query(lnum, rnum).first; 676 p.second = (p.first ? roots[r]->query(lnum, rnum).second : -1); 677 678 for(auto i : vec) if(i >= lnum && i <= rnum) p.first++; 679 680 return p; 681 } 682 683 void solve(){ 684 cin >> n; 685 686 for(int i = 1; i <= n; i++) cin >> arr[i]; 687 688 roots[0] = new Node(0, 1 << 30); 689 690 for(int i = 1; i <= n; i++) roots[i] = update(roots[i - 1], arr[i], i); 691 692 cin >> q; 693 694 while(q--){ 695 cin >> l >> r; 696 697 curnum = 0; 698 699 vec.clear(); 700 701 for(int i = 29; i >= 0; i--){ 702 pair<int, int> p = query(l, r, curnum, curnum + (1 << i) - 1); 703 704 if(p.first >= 2) continue; 705 else if(p.first >= 1 && p.second != -1){ 706 vec.push_back(arr[p.second] | (1 << i)); 707 curnum += 1 << i; 708 } 709 else{ 710 curnum += 1 << i; 711 for(auto &j : vec) j |= (1 << i); 712 } 713 } 714 715 cout << curnum << "\n"; 716 } 717 } 718 719 int main(){ 720 ios_base::sync_with_stdio(false);cin.tie(NULL); 721 722 cin >> t; 723 724 while(t--){ 725 solve(); 726 } 727 } 728 ``` 729 730 **No data structures... (C++, vsinitsynav)** 731 732 ``` 733 #include <bits/stdc++.h> 734 735 #define F first 736 #define S second 737 #define all(a) a.begin(), a.end() 738 739 using namespace std; 740 using ll = long long; 741 742 template<class T> bool ckmin(T &a, T b) { return a > b ? a = b, true : false; } 743 template<class T> bool ckmax(T &a, T b) { return a < b ? a = b, true : false; } 744 745 void solve() { 746 int n; cin >> n; 747 vector<int> a(n); for (auto &x : a) cin >> x; 748 vector<unordered_map<int, vector<int>>> cnt(30); 749 for (int i = 0; i < n; ++i) { 750 for (int j = 0; j < 30; ++j) { 751 cnt[29-j][a[i]>>j].push_back(i); 752 } 753 } 754 int q; cin >> q; 755 while (q--) { 756 int l, r; cin >> l >> r; l--; r--; 757 int x = 0, pref = 0; 758 vector<int> tmp; 759 for (int j = 0; j < 30; ++j) { 760 pref*=2; 761 vector<int> newtmp; 762 int k = upper_bound(all(cnt[j][pref]), r) - lower_bound(all(cnt[j][pref]), l); 763 int k0 = k; 764 for (auto y : tmp) { 765 if (((y>>(29-j))&1) == 0) k++, newtmp.push_back(y); 766 } 767 if (k0 == 1) { 768 int id = lower_bound(all(cnt[j][pref]), l) - cnt[j][pref].begin(); 769 tmp.push_back(a[cnt[j][pref][id]]); 770 } 771 if (k < 2) pref++; 772 else tmp.swap(newtmp); 773 } 774 cout << pref << "\n"; 775 } 776 } 777 778 int main() { 779 ios::sync_with_stdio(0); cin.tie(0); 780 int t; cin >> t; 781 while (t--) solve(); 782 return 228/1337; 783 } 784 ``` 785 786 **Who did what?** 787 788 * Problem A 789 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 790 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 791 * Problem B 792 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 793 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 794 * Problem C 795 + Idea: [shishyando](/profile/shishyando "Expert shishyando") 796 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 797 * Problem D 798 + Idea: [Artyom123](/profile/Artyom123 "Grandmaster Artyom123") 799 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 800 * Problem E 801 + Idea: [Kirill22](/profile/Kirill22 "International Grandmaster Kirill22") 802 + Polygon: [shishyando](/profile/shishyando "Expert shishyando") 803 * English translation: [shishyando](/profile/shishyando "Expert shishyando") 804 * Special thanks: [KAN](/profile/KAN "Legendary Grandmaster KAN") for coordinating the coordinator and double checking everything 805 * Another special thanks: [NEAR](https://near.org/) for supporting the Codeforces Community! 806 * Yet another special thanks: everyone who participated and tested!