1491.md (43060B)
1 Source: https://codeforces.com/blog/entry/88248 2 3 ## [1491A - K-th Largest Value](/contest/1491/problem/A "Codeforces Global Round 13") 4 5 Setter: [syksykCCC](/profile/syksykCCC "Master syksykCCC") 6 Prepared by: [syksykCCC](/profile/syksykCCC "Master syksykCCC") 7 8 **Hint 1** 9 10 How can we find the largest $k$ such that the $k$-th smallest element of the array is $0$? 11 12 **Hint 2** 13 14 How can we maintain $k$? 15 16 **Solution** 17 18 Let's define $cnt$ to represent the number of 1s in the array. 19 20 For the modifications, if $a_i$ is already $1$ now, then we let $cnt \gets cnt - 1$. Otherwise, let $cnt \gets cnt + 1$. 21 22 For the querys, just compare $cnt$ with $k$. If $cnt \ge k$, the answer will be $1$. Otherwise, the answer will be $0$. 23 24 The complexity : $O(n + q)$. 25 26 **Code (C++)** 27 28 ``` 29 #include <bits/stdc++.h> 30 using namespace std; 31 const int N = 1e6 + 5; 32 int n, q, a[N], cnt; 33 int main() 34 { 35 scanf("%d%d",&n,&q); 36 for(int i = 1; i <= n; ++i) 37 { 38 scanf("%d",a+i); 39 cnt += a[i]; 40 } 41 while(q--) 42 { 43 int opt, x; 44 scanf("%d%d",&opt,&x); 45 if(opt == 1) 46 { 47 if(a[x]) cnt--; 48 else cnt++; 49 a[x] = 1 - a[x]; 50 } 51 else 52 { 53 if(cnt >= x) puts("1"); 54 else puts("0"); 55 } 56 } 57 return 0; 58 } 59 ``` 60 61 **Code (Python) (vim1729)** 62 63 ``` 64 n, q = map(int,input().split()) 65 a = list(map(int,input().split())) 66 zero = a.count(0) 67 one = n - zero 68 for _ in range(q): 69 t, x = map(int,input().split()) 70 if t == 1: 71 if a[x-1] == 1: 72 zero += 1 73 one -= 1 74 a[x-1] = 0 75 else: 76 zero -= 1 77 one += 1 78 a[x-1] = 1 79 else: 80 if x<=one: 81 print(1) 82 else: 83 print(0) 84 ``` 85 86 ## [1491B - Minimal Cost](/contest/1491/problem/B "Codeforces Global Round 13") 87 88 Setter: [syksykCCC](/profile/syksykCCC "Master syksykCCC") 89 Prepared by: [syksykCCC](/profile/syksykCCC "Master syksykCCC") 90 91 **Hint 1** 92 93 When is the answer $0$? Or rather, when do you not have to make any moves? 94 95 **Hint 2** 96 97 What happens if $a[i]$ is same for all $i$? 98 99 **Solution** 100 101 Consider the following situations: 102 103 * $\forall i \in [2,n], |a_i - a_{i - 1}| = 0$, then the answer will be $v + \min(u, v)$. 104 * $\exists i \in [2,n], |a_i - a_{i - 1}| \gt 1$, then the answer will be $0$. 105 * Otherwise, the answer will be $\min(u, v)$. 106 107 **Code (C++)** 108 109 ``` 110 #include <bits/stdc++.h> 111 using namespace std; 112 const int N = 1e6 + 5; 113 int n, a[N], ans = INT_MAX, u, v, T; 114 int main() 115 { 116 ios::sync_with_stdio(false); 117 cin>>T; 118 while(T--){ 119 ans = INT_MAX; 120 cin >> n >> u >> v; 121 for(int i = 1; i <= n; i++) 122 cin >> a[i]; 123 for(int i = 2; i <= n; i++) 124 { 125 if(abs(a[i] - a[i - 1]) >= 2) ans = 0; 126 if(abs(a[i] - a[i - 1]) == 1) ans = min(ans, min(u, v)); 127 if(a[i] == a[i - 1]) ans = min(ans, v + min(u, v)); 128 } 129 cout << ans << endl; 130 } 131 132 return 0; 133 } 134 ``` 135 136 ## [1491C - Pekora and Trampoline](/contest/1491/problem/C "Codeforces Global Round 13") 137 138 Setter: [oolimry](/profile/oolimry "Master oolimry") 139 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 140 141 **Hint 1** 142 143 Think greedily! 144 145 **Hint 2** 146 147 By exchange argument, where can Pekora start her pass in an optimal solution? 148 149 **Solution** 150 151 For a series of passes, we can describe it as an array $P$ where $P_i$ is the trampoline Pekora starts at in the $i$-th pass. We claim that the final state of trampolines after performing any **permutation** of $P$ will be the same. 152 153 **Proof** 154 155 Focus on $2$ adjacent passes. We realize that if we swap those $2$ passes, the jumps done on both these passes are the same. 156 157  158 159 Since swapping any $2$ adjacent passes does not change the final state of trampolines, any permutation of $P$ will not change the final state of trampolines. 160 161 Now, we can claim that there is an optimal solution with $P$ being non-decreasing. Since Pekora can only move right, we must put Pekora on the first trampoline such that $S_i \ne 1$. 162 163 However, we cannot directly simulate putting Pekora on the first trampoline such that $S_i \ne 1$. This actually uses $O(N^3)$. 164 165 **Countertest** 166 167 `5000 4999 4998 4997 ... 2 1` 168 169 However, we can simulate this in $O(N^2)$ by the following. Instead of simulating passes individually, we will combine them. The main idea is that when Pekora jumps on a trampoline of strength $S_i$, we just add another Pekora on trampoline $S_i+i$ and process it later. 170 171 So, when we process trampolines from $1$ to $N$, we keep track of how many Pekoras there are on trampoline $i$, which we will denote as $C_i$. Then, we only add extra Pekoras to trampoline $i$ if $S_i \gt C_i+1$. Now, we have some Pekoras on trampoline $i$ and we need to update other values of $C_i$. 172 173 If $S_i=4$ and $C_i=6$ for example, we would add $1$ Pekora each trampolines to $i+2,i+3,i+4$ to reduce $S_i$ to 1. Then, the rest of the Pekoras will be moved to trampoline $i+1$. 174 175 This algorithm runs in $O(N^2)$ as we only need to update $O(N)$ other trampolines at each step. 176 177 Bonus: solve this problem in $O(N)$. (This was the original constraints but it was later changed since it was too hard for its position.) 178 179 **Code (C++)** 180 181 ``` 182 //雪花飄飄北風嘯嘯 183 //天地一片蒼茫 184 185 #include <bits/stdc++.h> 186 #include <ext/pb_ds/assoc_container.hpp> 187 #include <ext/pb_ds/tree_policy.hpp> 188 #include <ext/rope> 189 using namespace std; 190 using namespace __gnu_pbds; 191 using namespace __gnu_cxx; 192 #define ll long long 193 #define ii pair<ll,ll> 194 #define iii pair<ii,ll> 195 #define fi first 196 #define se second 197 #define endl '\n' 198 #define debug(x) cout << #x << " is " << x << endl 199 200 #define pub push_back 201 #define pob pop_back 202 #define puf push_front 203 #define pof pop_front 204 #define lb lower_bound 205 #define up upper_bound 206 207 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 208 #define all(x) (x).begin(),(x).end() 209 #define sz(x) (int)(x).size() 210 211 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 212 //change less to less_equal for non distinct pbds, but erase will bug 213 214 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 215 216 int n; 217 int arr[5005]; 218 ll curr[5005]; 219 220 int main(){ 221 ios::sync_with_stdio(0); 222 cin.tie(0); 223 cout.tie(0); 224 cin.exceptions(ios::badbit | ios::failbit); 225 226 int TC; 227 cin>>TC; 228 while (TC--){ 229 cin>>n; 230 rep(x,0,n) cin>>arr[x]; 231 rep(x,0,n) curr[x]=0; 232 233 ll ans=0; 234 235 rep(x,0,n){ 236 ll temp=curr[x]; 237 238 if (temp<arr[x]-1){ 239 ans+=arr[x]-1-temp; 240 temp+=arr[x]-1-temp; 241 } 242 243 curr[x+1]+=temp-arr[x]+1; 244 if (x+2<n) rep(y,x+2,min(n,x+arr[x]+1)) curr[y]++; 245 } 246 247 cout<<ans<<endl; 248 } 249 } 250 ``` 251 252 **Code (Python)** 253 254 ``` 255 TC=int(input()) 256 257 for tc in range(TC): 258 n=int(input()) 259 arr=list(map(int,input().split())) 260 261 curr=[0]*(n+5) 262 263 ans=0 264 265 for x in range(n): 266 temp=curr[x] 267 268 if (temp<arr[x]-1): 269 ans+=arr[x]-1-temp 270 temp+=arr[x]-1-temp 271 272 curr[x+1]+=temp-arr[x]+1 273 for y in range(x+2,min(n,x+arr[x]+1)): 274 curr[y]+=1 275 276 print(ans) 277 ``` 278 279 ## [1491D - Zookeeper and The Infinite Zoo](/contest/1491/problem/D "Codeforces Global Round 13") 280 281 Setter: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 282 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 283 284 **Hint 1** 285 286 Since $\&$ is a bitwise operation, represent the number in binary form! 287 288 **Hint 2** 289 290 We can convert any $u+v$ move to a series of $u+v'$ moves where $u\&v'=v'$ and $v'=2^k$. 291 292 **Hint 3** 293 294 Such a move converts a substring of the binary string of the form $01\ldots11$ into $10\ldots00$. 295 296 **Hint 4** 297 298 Focus on converting $01$ into $10$. 299 300 **Solution** 301 302 Firstly, we can show that the reachability graph is equivalent if we restrict to a directed edge between vertices $u$ and $u+v$ if $u\&v=v$ and that $v=2^k$ for some $k$. 303 304 This is because we can add each bit from $v$ from $u$ from the highest bit as adding a bit to a number will not affect lower bits. 305 306 Now, we observe that such as operation converts a binary string of the form $01\ldots11$ into $10\ldots00$ for some substring when we represent $u$ as a binary string. (more significant bits are to the left). 307 308 Now, we consider $s$ and $t$ as binary strings. 309 310 If and only if there is a matching from bits in $t$ to a lower bit in $s$ and $t$ > $s$, then $t$ is reachable from $s$. 311 312 Turning $01\ldots11$ into $10\ldots00$ means that we can move a bit ($01$->$10$) or we can squish multiple bits ($0111$->$1000$). 313 314 Let us show it is necessary. If $s \gt t$, it is impossible. And if there is no such matching, we are not able to put a position in $t$ as bits cannot move back, or there are not enough bits in $s$ to form $t$ (since the number of bits cannot increase). 315 316 Let is show it is sufficient. Since $s \lt t$ ($s=t$ is trivial), the strings have some common prefix and the most significant different bit has $0$ in $s$ and $1$ and $t$. Now, we can shift every bit in s into a position in t and squish the most significant bits. 317 318 To check if there is a matching, we find the least significant bit ($lsb$) of $t$ and $s$. if $lsb(t) \lt lsb(s)$ or if $s = 0$, then it is impossible. Else, we remove the $lsb$ from both $t$ and $s$ and repeat. If we're able to remove bits until $t=0$, then it is possible to go from $s$ to $t$. 319 320 **Code (C++)** 321 322 ``` 323 //雪花飄飄北風嘯嘯 324 //天地一片蒼茫 325 326 #include <bits/stdc++.h> 327 #include <ext/pb_ds/assoc_container.hpp> 328 #include <ext/pb_ds/tree_policy.hpp> 329 #include <ext/rope> 330 using namespace std; 331 using namespace __gnu_pbds; 332 using namespace __gnu_cxx; 333 #define ll long long 334 #define ii pair<ll,ll> 335 #define iii pair<ii,ll> 336 #define fi first 337 #define se second 338 #define endl '\n' 339 #define debug(x) cout << #x << " is " << x << endl 340 341 #define pub push_back 342 #define pob pop_back 343 #define puf push_front 344 #define pof pop_front 345 #define lb lower_bound 346 #define up upper_bound 347 348 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 349 #define all(x) (x).begin(),(x).end() 350 #define sz(x) (int)(x).size() 351 352 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 353 //change less to less_equal for non distinct pbds, but erase will bug 354 355 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 356 357 int main(){ 358 ios::sync_with_stdio(0); 359 cin.tie(0); 360 cout.tie(0); 361 cin.exceptions(ios::badbit | ios::failbit); 362 363 int TC; 364 cin>>TC; 365 while (TC--){ 366 int a,b; 367 cin>>a>>b; 368 369 vector<int> va,vb; 370 371 if (a>b){ 372 cout<<"NO"<<endl; 373 goto done; 374 } 375 376 rep(x,0,30){ 377 if (a&(1<<x)) va.pub(x); 378 if (b&(1<<x)) vb.pub(x); 379 } 380 381 if (sz(va)<sz(vb)){ 382 cout<<"NO"<<endl; 383 goto done; 384 } 385 386 rep(x,0,sz(vb)){ 387 if (va[x]>vb[x]){ 388 cout<<"NO"<<endl; 389 goto done; 390 } 391 } 392 393 cout<<"YES"<<endl; 394 395 done:; 396 } 397 } 398 ``` 399 400 **Code (C++) (gamegame)** 401 402 ``` 403 #include<bits/stdc++.h> 404 using namespace std; 405 typedef long long ll; 406 int main(){ 407 ios::sync_with_stdio(false);cin.tie(0); 408 int t;cin >> t; 409 while(t--){ 410 int x,y;cin >> x >> y; 411 int z=0; 412 bool ok=(x<=y); 413 for(int i=0; i<30 ;i++){ 414 if((x>>i)&1) z++; 415 if((y>>i)&1) z--; 416 if(z<0) ok=false; 417 } 418 if(ok) cout << "YES\n"; 419 else cout << "NO\n"; 420 } 421 } 422 ``` 423 424 **Code (Python)** 425 426 ``` 427 def lsb(x): 428 return x & (-x) 429 Q = int(input()) 430 for q in range(Q): 431 a,b = map(int,input().split(" ")) 432 if a > b: 433 print("NO") 434 else: 435 can = True 436 while b > 0: 437 if lsb(b) < lsb(a) or a == 0: 438 can = False 439 break 440 a -= lsb(a) 441 b -= lsb(b) 442 print("YES" if can else "NO") 443 ``` 444 445 ## [1491E - Fib-tree](/contest/1491/problem/E "Codeforces Global Round 13") 446 447 Setter: [Widowmaker](/profile/Widowmaker "Master Widowmaker") 448 Prepared by: [Widowmaker](/profile/Widowmaker "Master Widowmaker") and [syksykCCC](/profile/syksykCCC "Master syksykCCC") 449 450 **Hint** 451 452 The only pair $(j,k)$ that satisfies $F_i=F_j+F_k$ is $(i-1,i-2)$. 453 454 **Solution** 455 456 Firstly, we can discover that we can only cut a tree in the size of $f_{i}$ into one in size of $f_{i-1}$ and one in size of $f_{i-2}$. 457 458 **Proof** 459 460 We want to show that the only solution to $F_i=F_j+F_k$ is $(j,k)=(i-1,i-2)$ for $j \geq k$. 461 462 Clearly, $i \gt j$, otherwise, $F_i \lt F_j+F_k$. 463 464 Furthermore, $j \gt i-2$ as $F_i \gt 2 \cdot F_{i-2}$. 465 466 Therefore, we have shown the only solution is $(j,k)=(i-1,i-2)$. 467 468 However, we will have 2 ways to partition the tree sometimes. But it turns out we can cut any edge! 469 470 We will prove that if some edge cuts Fib-tree of $F_n$ vertices into trees with sizes $F_{n-1}$ and $F_{n-2}$, we can cut it, and the resulting trees are also Fib-trees. 471 472 **Proof** 473 474 By induction. For $n = 2$ it's obvious. 475 476 If only edge cuts Fib-tree into trees with sizes $F_{n-1}$ and $F_{n-2}$, we have to cut it. 477 478 If there are two such edges: suppose that cutting the first edge results in making two Fib-trees. Then in the tree of size $F_{n-1}$ the second edge divides it into trees of sizes $F_{n-2}$ and $F_{n-3}$, so we can cut it as well in the next step. But then we could as well cut the second edge first: we will have one Fib-tree of size $F_{n-2}$, and one tree of size $F_{n-1}$ which is cut into Fib-trees of sizes $F_{n-2}$ and $F_{n-3}$ by the first edge, so it's also a Fib-tree! 479 480 Because the growth of Fibonacci sequence is approximately $O(\phi^n)$, we only need to cut our tree $O(\log_\phi n)$ times: every time, if we find the splitting edge, we cut it, and recurse to the resulting trees, if at some point there was no splitting edge — tree isn't Fib-tree. 481 482 Finally, we got an $O(n\log_\phi n)$ solution. 483 484 **Code (C++)** 485 486 ``` 487 #include <bits/stdc++.h> 488 using namespace std; 489 const int N = 2e5 + 5; 490 int n, siz[N]; 491 vector<int> fib; 492 vector<pair<int, bool> > G[N]; 493 void NO() { cout << "NO\n"; exit(0); } 494 void GetSize(int u, int fa) 495 { 496 siz[u] = 1; 497 for(pair<int, bool> e : G[u]) 498 { 499 if(e.second) continue; 500 int v = e.first; 501 if(v == fa) continue; 502 GetSize(v, u); 503 siz[u] += siz[v]; 504 } 505 } 506 void CutEdge(int u, int fa, int k, int &pu, int &pv, int &kd) 507 { 508 for(pair<int, bool> e : G[u]) 509 { 510 if(pu) return; 511 if(e.second) continue; 512 int v = e.first; 513 if(v == fa) continue; 514 if(siz[v] == fib[k - 1] || siz[v] == fib[k - 2]) 515 { 516 pu = u; pv = v; 517 kd = (siz[v] == fib[k - 1]) ? k - 1 : k - 2; 518 break; 519 } 520 CutEdge(v, u, k, pu, pv, kd); 521 } 522 } 523 void Check(int u, int k) 524 { 525 // cout << "Check " << u << ' ' << k << endl; 526 if(k <= 1) return; 527 GetSize(u, 0); 528 int pu = 0, pv = 0, kd = 0; 529 CutEdge(u, 0, k, pu, pv, kd); 530 // cout << pu << ' ' << pv << ' ' << kd << endl; 531 if(!pu) NO(); 532 for(pair<int, bool> &e : G[pu]) 533 if(e.first == pv) e.second = true; 534 for(pair<int, bool> &e : G[pv]) 535 if(e.first == pu) e.second = true; 536 Check(pv, kd); 537 Check(pu, (kd == k - 1) ? k - 2 : k - 1); 538 } 539 int main() 540 { 541 ios::sync_with_stdio(false); 542 cin >> n; 543 fib.push_back(1); 544 fib.push_back(1); 545 for(int i = 1; ; i++) 546 { 547 if(fib[i] >= n) break; 548 int new_fib = fib[i] + fib[i - 1]; 549 fib.push_back(new_fib); 550 } 551 for(int i = 1; i < n; i++) 552 { 553 int u, v; 554 cin >> u >> v; 555 G[u].push_back(make_pair(v, false)); 556 G[v].push_back(make_pair(u, false)); 557 } 558 if(fib[fib.size() - 1] != n) NO(); 559 Check(1, fib.size() - 1); 560 cout << "YES\n"; 561 return 0; 562 } 563 ``` 564 565 ## [1491F - Magnets](/contest/1491/problem/F "Codeforces Global Round 13") 566 567 Setter: [3.141592653](/profile/3.141592653 "Grandmaster 3.141592653") and [star_xingchen_c](/profile/star_xingchen_c "Master star_xingchen_c") 568 Prepared by: [3.141592653](/profile/3.141592653 "Grandmaster 3.141592653") and [star_xingchen_c](/profile/star_xingchen_c "Master star_xingchen_c") 569 570 **Hint 1** 571 572 Try to construct a solution that works in $2n$ queries. 573 574 **Hint 2** 575 576 Try to find the second magnet which is not `-'. 577 578 **Hint 3** 579 580 The actual query limit is $n-1+\lceil\log_2n\rceil$. 581 582 **Solution** 583 584 It seems this problem needs some random technique, but here is a determinate solution: 585 586 We just try to find a not demagnetized magnet. 587 588 You can go through the following method to find one: 589 590 First put the first magnet in the left. 591 592 Then ask all the other magnets with the left pile. 593 594 If we got a non-zero answer, we find a valid magnet; else we just put this magnet in the left. 595 596 It can be proven later that we will always be able to find a valid magnet. 597 598 Then use this magnet to try on all other magnets. 599 600 This process form a solution requiring at most $2n-2$ queries. 601 602 However, when we look back at this solution we'll realize that there is a huge waste of information in the previous queries. 603 604 As all the previous answers are $0$, it's easy to prove that the magnet we found is the **second** one we have selected. 605 606 Since we know nothing about the right part, we can simply check the magnets in the right one by one. 607 608 However, you have known that there is only $1$ magnetic magnet in the left, so you can do a binary search to seek for the answer. 609 610 The maximum number of queries is $n-1+\lceil\log_2n\rceil$, which perfectly matches the limit. 611 612 **Code (C++)** 613 614 ``` 615 #include<bits/stdc++.h> 616 int n; 617 std::vector<int>ans,tmp,hlf; 618 int main() 619 { 620 int T; 621 scanf("%d",&T); 622 for(;T--;) 623 { 624 ans.clear(),tmp.clear(),hlf.clear(); 625 scanf("%d",&n); 626 register int i,ii; 627 int sec=0; 628 for(i=2;i<=n;i++) 629 { 630 printf("? 1 %d\n%d\n",i-1,i); 631 for(ii=1;ii<i;ii++)printf("%d ",ii); 632 puts(""),fflush(stdout); 633 int f; 634 scanf("%d",&f); 635 if(f){sec=i;break;} 636 }for(i=sec+1;i<=n;i++) 637 { 638 printf("? 1 1\n%d\n%d\n",sec,i); 639 fflush(stdout); 640 int f; 641 scanf("%d",&f); 642 if(!f)ans.push_back(i); 643 }for(i=1;i<sec;i++)tmp.push_back(i); 644 while(tmp.size()>1) 645 { 646 int md=tmp.size()>>1; 647 hlf.clear(); 648 for(i=1;i<=md;i++) 649 hlf.push_back(tmp.back()),tmp.pop_back(); 650 printf("? 1 %d\n%d\n",md,sec); 651 for(int t:hlf)printf("%d ",t); 652 puts(""),fflush(stdout); 653 int f; 654 scanf("%d",&f); 655 if(f)tmp=hlf; 656 } 657 for(i=1;i<sec;i++)if(tmp[0]!=i)ans.push_back(i); 658 printf("! %u",ans.size()); 659 for(int t:ans)printf(" %d",t); 660 puts(""),fflush(stdout); 661 } 662 } 663 ``` 664 665 ## [1491G - Switch and Flip](/contest/1491/problem/G "Codeforces Global Round 13") 666 667 Setter: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") and [oolimry](/profile/oolimry "Master oolimry") 668 Prepared by: [errorgorn](/profile/errorgorn "Grandmaster errorgorn") 669 670 **Hint 1** 671 672 Visualize this problem as graph with directed edges $(i,c_i)$. 673 674 **Hint 2** 675 676 Solve this problem where there is only $1$ big cycle. 677 678 **Hint 3** 679 680 What if a cycle has $2$ coins that are upside down? How can we force a cycle into such state? 681 682 **Solution** 683 684 We can visualize the problem as a graph with nodes of $2$ colors (face up — red and face down — blue). Initially, the graph has nodes with all red color and with a directed edge to $c_i$. 685 686 Firstly, any $2$ cycles with all red nodes can be converted into a single cycle with $2$ blues nodes with $1$ swap. 687 688  689 690 A cycle with $2$ blue nodes is very convenient here as swapping a blue node with a red node it is pointing to will decrease the cycle size and maintain that the cycle still has $2$ blue nodes. We can keep decreasing the cycle size until the cycle has only $2$ blue nodes and solve that in $1$ swap. Thus, solving $2$ cycles which have $X$ nodes in total uses only $X$ swaps. 691 692 Now, we simply pair the cycles and do this. 693 694 However, if there is an odd number of cycles, there are $2$ cases: 695 696 If the cycle does not cover the whole graph, we can solve the remaining cycle and a cycle of size $1$ together. 697 698 Otherwise, we can force $2$ blue nodes into the cycle with $2$ swaps (does not work for $n = 2$ so be careful). 699 700  701 702 Both cases need $X+1$ moves where $X$ is the size of the remaining cycle. 703 704 Thus, at most $X+1$ swaps is needed in this algorithm. 705 706 **Code (C++)** 707 708 ``` 709 //雪花飄飄北風嘯嘯 710 //天地一片蒼茫 711 712 #include <bits/stdc++.h> 713 #include <ext/pb_ds/assoc_container.hpp> 714 #include <ext/pb_ds/tree_policy.hpp> 715 #include <ext/rope> 716 using namespace std; 717 using namespace __gnu_pbds; 718 using namespace __gnu_cxx; 719 #define ll long long 720 #define ii pair<ll,ll> 721 #define iii pair<ii,ll> 722 #define fi first 723 #define se second 724 #define endl '\n' 725 #define debug(x) cout << #x << " is " << x << endl 726 727 #define pub push_back 728 #define pob pop_back 729 #define puf push_front 730 #define pof pop_front 731 #define lb lower_bound 732 #define up upper_bound 733 734 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 735 #define all(x) (x).begin(),(x).end() 736 #define sz(x) (int)(x).size() 737 738 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 739 //change less to less_equal for non distinct pbds, but erase will bug 740 741 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 742 743 int n; 744 int arr[200005]; 745 bool vis[200005]; 746 vector<ii> ans; 747 748 void cswap(int i,int j){ 749 swap(arr[i],arr[j]); 750 arr[i]=-arr[i],arr[j]=-arr[j]; 751 ans.pub(ii(i,j)); 752 } 753 754 void swap_cyc(int i,int j){ 755 cswap(i,j); 756 757 int curr=i; 758 while (arr[-arr[curr]]>0){ 759 cswap(curr,-arr[curr]); 760 } 761 762 curr=-arr[curr]; 763 while (arr[-arr[curr]]>0){ 764 cswap(curr,-arr[curr]); 765 } 766 767 cswap(curr,-arr[curr]); 768 } 769 770 int main(){ 771 ios::sync_with_stdio(0); 772 cin.tie(0); 773 cout.tie(0); 774 cin.exceptions(ios::badbit | ios::failbit); 775 776 cin>>n; 777 rep(x,1,n+1) cin>>arr[x]; 778 779 int p=-1; 780 781 rep(x,1,n+1) if (!vis[x]){ 782 if (arr[x]==x) continue; 783 784 int curr=x; 785 do{ 786 vis[curr]=true; 787 curr=arr[curr]; 788 } while (curr!=x); 789 790 if (p==-1) p=x; 791 else{ 792 swap_cyc(p,x); 793 p=-1; 794 } 795 } 796 797 if (p!=-1){ 798 bool can=false; 799 rep(x,1,n+1) if (arr[x]==x){ 800 swap_cyc(p,x); 801 can=true; 802 break; 803 } 804 805 if (!can){ 806 int t1=arr[p],t2=arr[arr[p]]; 807 cswap(p,t1); 808 swap_cyc(t1,t2); 809 } 810 } 811 812 cout<<sz(ans)<<endl; 813 for (auto &it:ans) cout<<it.fi<<" "<<it.se<<endl; 814 } 815 ``` 816 817 **Code (Python)** 818 819 ``` 820 from sys import stdin, stdout 821 822 n=int(stdin.readline()) 823 824 #make 1-indexed 825 arr=[0]+list(map(int,stdin.readline().split())) 826 827 vis=[0]*(n+1) 828 829 ans=[] 830 831 def cswap(i,j): 832 arr[i],arr[j]=-arr[j],-arr[i] 833 ans.append((i,j)) 834 835 def swap_cyc(i,j): 836 cswap(i,j) 837 838 curr=i 839 while (arr[-arr[curr]]>0): 840 cswap(curr,-arr[curr]) 841 842 curr=-arr[curr] 843 while (arr[-arr[curr]]>0): 844 cswap(curr,-arr[curr]) 845 846 cswap(curr,-arr[curr]) 847 848 p=-1 849 for i in range(1,n+1): 850 if (vis[i]==1): continue 851 if (arr[i]==i): continue 852 853 curr=i 854 while (True): 855 vis[curr]=1 856 curr=arr[curr] 857 if (curr==i): break 858 859 if (p==-1): 860 p=i 861 else: 862 swap_cyc(p,i) 863 p=-1 864 865 if (p!=-1): 866 can=False 867 for i in range(1,n+1): 868 if (arr[i]==i): 869 swap_cyc(p,i) 870 can=True 871 break 872 873 if (can==False): 874 t1,t2=arr[p],arr[arr[p]] 875 cswap(p,t1) 876 swap_cyc(t1,t2) 877 878 print(len(ans)) 879 [print(i[0],i[1]) for i in ans] 880 ``` 881 882 ## [1491H - Yuezheng Ling and Dynamic Tree](/contest/1491/problem/H "Codeforces Global Round 13") 883 884 Setter: [Ynoi](/profile/Ynoi "Master Ynoi") 885 Prepared by: [Widowmaker](/profile/Widowmaker "Master Widowmaker") and [Ynoi](/profile/Ynoi "Master Ynoi") 886 887 **Hint 1** 888 889 The complexity is $\mathcal O(n\sqrt{n})$. 890 891  892 893 **Solution** 894 895 Divide the nodes into $\sqrt{n}$ blocks. The $i$-th block will contain the nodes in $[(i-1) \sqrt{n}+1,i \sqrt{n}]$. 896 897 Let's define $f_x$ as an ancestor of $x$ such that $f_x$ is in the same block as $x$ and $a_{f_x}$ is not in the same block as $x$. 898 899 Notice that for a given block, if all $a_x$ is not in the same block as $x$, then $f_x=x$. 900 901 So, we do not have to re-compute all values of $f_x$ for a certain block if $\forall x, x-a_x \geq \sqrt n$ in this block. 902 903 When we update a range, we will update some ranges fully and update at most $2$ ranges partially. Let's show that only $O(n+q)$ re-computations will happen. 904 905 For a certain block, if it is completely contained in an update, the value of $x-a_x$ will increase by $1$, a single block will be re-computed by at most $O(\sqrt n)$ of such updates, which will contribute $O(\sqrt n \cdot \sqrt n)=O(n)$ re-computations. 906 907 For blocks that are partially updated by an update, such things will only happen at most $2q$ times, therefore we have a bound of $O(q)$ re-computations from such updates. 908 909 Maintaining $f_x$, querying can be easily done in $O(\sqrt n)$. 910 911 **Code (C++)** 912 913 ``` 914 #include <bits/stdc++.h> 915 #define N 100005 916 using namespace std; 917 918 template <typename T> 919 920 void read(T &a) 921 { 922 T x = 0,f = 1; 923 char ch = getchar(); 924 while (ch < '0' || ch > '9') 925 { 926 if (ch == '-') f = -1; 927 ch = getchar(); 928 } 929 while (ch >= '0' && ch <= '9') 930 { 931 x = (x << 1) + (x << 3) + (ch ^ 48); 932 ch = getchar(); 933 } 934 a = x * f; 935 } 936 937 template <typename T> 938 939 void write(T x) 940 { 941 if (x < 0) putchar('-'),x = -x; 942 if (x < 10) return (void) putchar(x + '0'); 943 write(x / 10); 944 putchar(x % 10 + '0'); 945 } 946 947 template <typename T> 948 949 void writeln(T x) 950 { 951 write(x); 952 putchar('\n'); 953 } 954 955 template <typename T> 956 957 void writes(T x) 958 { 959 write(x); 960 putchar(' '); 961 } 962 963 template <typename T,typename... Args> 964 965 void read(T &maxx,Args &... args) 966 { 967 read(maxx); 968 read(args...); 969 } 970 971 template <typename T,typename... Args> 972 973 void writeln(T maxx,Args ... args) 974 { 975 writes(maxx); 976 writes(args...); 977 putchar('\n'); 978 } 979 980 const int B = 300; 981 int n,q,a[N],num,bl[N],vis[N]; 982 std::vector<int> v; 983 984 struct Block 985 { 986 int f[B],lazy,flag,cnt,L,R; 987 void update() 988 { 989 flag = 1; 990 for (int i = L; i <= R; i++) 991 { 992 if (bl[i] != bl[a[i]]) f[i - L] = i; 993 else f[i - L] = f[a[i] - L],flag = 0; 994 } 995 } 996 void update(int l,int r,int x) 997 { 998 for (int i = l; i <= r; i++) 999 a[i] = i == 1 ? 0 : max(a[i] - x,1); 1000 update(); 1001 } 1002 void update(int x) 1003 { 1004 if (flag) lazy += x; 1005 else update(L,R,x); 1006 } 1007 }T[(N - 1) / B + 5]; 1008 1009 void update(int l,int r,int x) 1010 { 1011 if (bl[l] == bl[r]) 1012 { 1013 T[bl[l]].update(l,r,x); 1014 return ; 1015 } 1016 T[bl[l]].update(l,T[bl[l]].R,x); 1017 for (int i = bl[l] + 1; i < bl[r]; i++) 1018 T[i].update(x); 1019 T[bl[r]].update(T[bl[r]].L,r,x); 1020 // cout << l << ' ' << r << ' ' << x << endl; 1021 // cout << '0' << ' '; 1022 // for (int i = 2; i <= n; i++) 1023 // cout << max(a[i] - T[bl[i]].lazy,1) << ' '; 1024 // cout << endl; 1025 } 1026 1027 void clear() 1028 { 1029 for (int i = 0; i < v.size(); i++) 1030 vis[v[i]] = 0; 1031 v.clear(); 1032 } 1033 1034 int query(int x,int y) 1035 { 1036 // cout << '0' << ' '; 1037 // for (int i = 2; i <= n; i++) 1038 // cout << max(a[i] - T[bl[i]].lazy,1) << ' '; 1039 // cout << endl; 1040 while (T[bl[x]].f[x - T[bl[x]].L] != T[bl[y]].f[y - T[bl[y]].L]) 1041 { 1042 if (bl[x] < bl[y]) swap(x,y); 1043 // cout << x << ' ' << T[bl[x]].f[x - T[bl[x]].L] << endl; 1044 x = (T[bl[x]].f[x - T[bl[x]].L] == 1) ? 0 : max(a[T[bl[x]].f[x - T[bl[x]].L]] - T[bl[x]].lazy,1); 1045 } 1046 int qaq = (T[bl[x]].f[x - T[bl[x]].L] == 1) ? 0 : max(a[T[bl[x]].f[x - T[bl[x]].L]] - T[bl[x]].lazy,1); 1047 while (x != qaq) 1048 { 1049 assert(x != qaq); 1050 vis[x] = 1; 1051 v.push_back(x); 1052 x = (x == 1) ? 0 : max(a[x] - T[bl[x]].lazy,1); 1053 } 1054 while (y != qaq) 1055 { 1056 if (vis[y]) return clear(),y; 1057 y = (y == 1) ? 0 : max(a[y] - T[bl[y]].lazy,1); 1058 } 1059 } 1060 1061 signed main() 1062 { 1063 read(n,q); 1064 for (int i = 2; i <= n; i++) read(a[i]); 1065 num = (n - 1) / B + 1; 1066 for (int i = 1; i <= num; i++) 1067 { 1068 T[i].L = (i - 1) * B + 1; 1069 T[i].R = min(i * B,n); 1070 T[i].cnt = i * B - (i - 1) * B; 1071 T[i].flag = T[i].lazy = 0; 1072 for (int j = T[i].L; j <= T[i].R; j++) 1073 bl[j] = i; 1074 } 1075 for (int i = 1; i <= num; i++) 1076 T[i].update(); 1077 while (q--) 1078 { 1079 int opt; 1080 read(opt); 1081 if (opt == 1) 1082 { 1083 int l,r,x; 1084 read(l,r,x); 1085 update(l,r,x); 1086 } 1087 if (opt == 2) 1088 { 1089 int u,v; 1090 read(u,v); 1091 writeln(query(u,v)); 1092 } 1093 } 1094 // cerr << (double) clock() / CLOCKS_PER_SEC << endl; 1095 return 0; 1096 } 1097 ``` 1098 1099 ## [1491I - Ruler Of The Zoo](/contest/1491/problem/I "Codeforces Global Round 13") 1100 1101 Setter: [oolimry](/profile/oolimry "Master oolimry") 1102 Prepared by: [oolimry](/profile/oolimry "Master oolimry") 1103 1104 As the solution to this problem is very long, the full editorial is split into $4$ parts. If you want to challenge yourself, you can try reading one part at a time and see if you get any inspiration. You can also try to read the specific hints for each part. 1105 1106 **Part 1 Hint 1** 1107 1108 Convert the queue into a circle. 1109 1110 **Part 1** 1111 1112 Firstly, let's convert the queue into a circle. In our new problem, $n$ animals stand in a circle. The king fights the animal directly clockwise to it. If the king wins, he and the other person swap places, otherwise nothing happens. The animal that is king will always move 1 space clockwise regardless of what happens. 1113 1114  1115 1116 For example, in this scenario, 0 beats 1, so he stays as king. But he then loses to 2. 1117 1118 **Part 2 Hint 1** 1119 1120 Call animals whose A is smaller than the B of the animal before them RED color and the rest of the animals NONRED color. 1121 1122 **Part 2 Hint 2** 1123 1124 Work out the inequalities. 1125 1126 **Part 2 Hint 3** 1127 1128 How do the colors of animals change? 1129 1130 **Part 2** 1131 1132 Let's give each animal a color. An animal $i$ is RED if $B_{i-1}$ > $A_i$. In other words, and animal is red if and only if the previous animal will beat it as king. The animals that are not red are called NONRED for now. 1133 1134 We can assume no two animals are consecutively RED* (*will elaborate more in part 4). Suppose we have 3 animals $XYZ$ in that order, and $Y$ is red while $X$ and $Z$ are non-red. Suppose $X$ becomes king and wins $Y$ but not $Z$. As such, the final arrangement is $YXZ$. The claim here is that $X$ and $Z$ cannot become RED. 1135 1136 For $X$, $X$ beats $Y$, We have $B_X \gt A_Y$, but since $A_X \gt B_X$ and $A_Y \gt B_Y$, we get that $B_Y \lt A_X$. As such, $X$ cannot be RED. 1137 1138 For $Z$, we have $C_X \lt A_Z$ (since X lost to Z) and $B_X \lt C_X$, we hence have $B_X \lt A_Z$. As such, $Z$ cannot be RED 1139 1140 Finally for $Y$, it is possible that it turns from RED to NONRED. 1141 1142 From these we can conclude that **RED cannot be created, but can be destroyed**. 1143 1144 **Part 3 Hint 1** 1145 1146 REDs can only be destroyed at most $O(n)$ times. 1147 1148 **Part 3 Hint 2** 1149 1150 Simulate a lot "uneventful" moves at once. 1151 1152 **Part 3 Hint 3** 1153 1154 Consider NONRED positions to be fixed, and the REDs rotate anti-clockwise about them. 1155 1156 **Part 3 Hint 4** 1157 1158 After $n-1$ moves, what do you observe? 1159 1160 **Part 3 Hint 5** 1161 1162 Do many sets of $n-1$ moves at once until a RED is destroyed or when the game ends. 1163 1164 **Part 3 Hint 6** 1165 1166 How to find when a RED is destroyed or when the game ends event occurs quickly? 1167 1168 **Part 3** 1169 1170 As such, we have the following conclusions: 1171 1172 * REDS are never created only destroyed 1173 * The order of NONREDS will not change unless a RED inserts itself within the sequence 1174 * REDS will never battle REDS (because of * assumption) 1175 1176 Since the number of times REDS can be destroyed is limited, we should exploit that. We define an event as either when a RED is destroyed or when the game ends. Since events can occur at most $O(n)$ times, we just need to find some way to quickly simulate the moves until the next event. 1177 1178 Let's visualize the moves like this: instead of the RED and NONRED swapping positions, the NONREDs are fixed in position, and the REDs move around anticlockwise. 1179 1180  1181 1182 After $n-1$ moves, every RED moves one space anticlockwise around the belt of NONREDs Then in that case, we just need to check how many sets of $n-1$ moves is needed until the first event occurs. 1183 1184 For convenience, let's split NONRED into BLUE and GREEN. If a NONRED beats a red in front of it, and it loses to next animal, then it is BLUE. If it wins one more time (and hence the entire game) it is GREEN. 1185 1186 Let's look at the conditions for the events: 1187 1188 1. A RED is destroyed. This occurs when $B_{nr} \lt A_{r}$ where $nr$ is any BLUE or GREEN 1189 2. The game ends. This occurs when $B_{g} \gt A_{r}$ where $g$ is any GREEN 1190 1191 To find the first how many times the reds need to move anticlockwise, we could maintain a monotonic vector across the belt of NONREDs, and then for each RED, binary search the earliest position where an event occurs. 1192 1193 Finally, when we find the number of sets of $n-1$ we need to move backwards, we move everything manually, check if the game ends. Then we recompute the color of all animals, and repeat. If no event occurs, then it will repeat infinitely. 1194 1195 The step of finding the number of steps before first event occurs takes $O(nlogn)$ in total. Since REDs can disappear at most $O(n)$ times, then the total time complexity is $O(n^2logn)$. 1196 1197 It's worth noting that the constant factor for this algorithm is small as the number of REDs is $0.5n$ and binary search is a very fast log. Hence, it passes quite comfortably (author's solution is under 400ms) even though $n \leq 6000$. 1198 1199 **Part 4** 1200 1201 In terms of implementation, we can run the first $2n$ by brute force just to handle some bad corner cases. In particular, it is mostly to handle the assumption "We can assume no two animals are consecutively RED". 1202 1203 If two animals are consecutively RED, then working out the inequalities will show that the one right before the two REDs should be able to win, and hence the game should end within $2n$ moves. 1204 1205 **Code (C++)** 1206 1207 ``` 1208 #include <bits/stdc++.h> 1209 using namespace std; 1210 const int RED = 0, BLUE = 1, GREEN = 2; 1211 const long long inf = 1e16; 1212 typedef pair<long long, long long> ii; 1213 typedef pair<long long, ii> iii; 1214 1215 long long n; 1216 struct animal{ int a, b, c, id, pos, colour, redHere; }; 1217 vector<animal> belt; 1218 vector<animal> arr; 1219 1220 vector<iii> s; ///strictly increasing stack 1221 vector<ii> reds; 1222 void insert(long long b, long long beltPos, long long pos){ 1223 while(!s.empty() && s.back().first >= b) s.pop_back(); 1224 s.push_back(iii(b,ii(beltPos, pos))); 1225 } 1226 1227 long long totalMoves = 0; 1228 1229 void brute(){ 1230 deque<animal> q; 1231 animal w = arr[0]; 1232 1233 for(int i = 1;i < n;i++){ 1234 q.push_back(arr[i]); 1235 } 1236 1237 long long count = 1; 1238 for(int x = 1;;x++){ 1239 if(x > 2*n){ 1240 return; 1241 } 1242 1243 if(count == 3){ 1244 cout << w.id << " " << x << "\n"; // << "\n" << (int)((clock() - start)); 1245 exit(0); 1246 } 1247 1248 if(count == 1){ 1249 if(w.b > q.front().a){ 1250 animal y = q.front(); 1251 q.push_back(y); 1252 q.pop_front(); 1253 count++; 1254 } 1255 else{ 1256 q.push_back(w); 1257 w = q.front(); 1258 q.pop_front(); 1259 count = 1; 1260 } 1261 } 1262 else{ 1263 if(w.c > q.front().a){ 1264 animal y = q.front(); 1265 q.push_back(y); 1266 q.pop_front(); 1267 count++; 1268 } 1269 else{ 1270 q.push_back(w); 1271 w = q.front(); 1272 q.pop_front(); 1273 count = 1; 1274 } 1275 } 1276 } 1277 } 1278 1279 int main(){ 1280 ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); 1281 1282 cin >> n; 1283 for(int i = 0;i < n;i++){ 1284 int a, b, c; cin >> a >> b >> c; 1285 assert(a > b and b < c); 1286 arr.push_back({a,b,c,i,-1,1,-1}); 1287 } 1288 1289 if(arr[0].a > arr[1].a) swap(arr[0],arr[1]); ///settle first game 1290 arr.push_back(arr[0]); arr.erase(arr.begin()); 1291 1292 brute(); 1293 1294 ///deciding which are RED 1295 for(int i = 1;i < n;i++){ 1296 if(arr[i-1].b > arr[i].a){ 1297 arr[i].colour = RED; 1298 } 1299 } 1300 1301 ///for non-RED, decide if it's BLUE or GREEN 1302 for(int i = 0;i < n;i++){ 1303 arr[i].pos = i; 1304 1305 if(arr[i].colour == RED) continue; 1306 int nxt = i+1; if(nxt == n) nxt = 0; 1307 if(arr[nxt].colour == RED) nxt++; if(nxt == n) nxt = 0; 1308 1309 if(arr[i].c > arr[nxt].a) arr[i].colour = GREEN; 1310 else arr[i].colour = BLUE; 1311 } 1312 1313 ///get ready the belt 1314 arr.push_back(arr[0]); 1315 for(int i = 0;i < n;i++){ 1316 if(arr[i].colour != RED){ 1317 if(arr[i+1].colour == RED){ 1318 arr[i].redHere = arr[i+1].pos; 1319 } 1320 belt.push_back(arr[i]); 1321 } 1322 } 1323 1324 while(true){ 1325 s.clear(); reds.clear(); 1326 1327 ///Account for cyclic nature, so every element is inserted once, then later inserted again 1328 for(int i = 0;i < (int) belt.size();i++){ 1329 animal A = belt[i]; 1330 if(A.colour == BLUE) insert(A.b, A.pos, i); 1331 else insert(-inf, A.pos, i); ///GREEN trigger events regardless of the value of a 1332 } 1333 1334 long long minMoves = inf; 1335 for(int i = 0;i < (int) belt.size();i++){ 1336 animal A = belt[i]; 1337 if(A.colour == BLUE) insert(A.b, A.pos, i); 1338 else insert(-inf, A.pos, i); ///GREEN trigger events regardless of the value of a 1339 1340 ///find the RED at that position, if any 1341 int red = A.redHere; if(red == -1) continue; 1342 reds.push_back(ii(red, i)); 1343 1344 ///find the earliest event that triggers this RED (rightmost non-Red with nonRED.a < RED.b or rightmost GREEN) 1345 auto early = lower_bound(s.begin(), s.end(), iii(arr[red].a, ii(-1,-1))); 1346 if(early == s.begin()) continue; ///no event in this case 1347 early--; 1348 1349 ///Number of rotations before event (rotation = N-1 turns) 1350 long long distance = i - (early->second).second; 1351 if(distance < 0) distance += (belt.size()); 1352 minMoves = min(distance, minMoves); ///find the minimum number of rotations 1353 } 1354 1355 ///No event can occur, answer last infiinite 1356 if(minMoves == inf){ 1357 cout << "-1 -1"; 1358 return 0; 1359 } 1360 else if(minMoves != 0){ ///Move the reds CCW along the belt 1361 totalMoves += minMoves * (n-1); 1362 for(ii R : reds) belt[R.second].redHere = -1; 1363 for(ii R : reds){ 1364 int pos = R.second; 1365 pos -= minMoves; if(pos < 0) pos += belt.size(); 1366 belt[pos].redHere = R.first; 1367 } 1368 } 1369 1370 ii ans = ii(inf, inf); 1371 1372 ///Updating the belt 1373 for(int i = 0;i < (int) belt.size();i++){ 1374 if(belt[i].redHere == -1) continue; 1375 animal R = arr[belt[i].redHere]; 1376 if(belt[i].b < R.a){ ///BLUE type event occured 1377 belt[i].redHere = -1; 1378 belt.insert(belt.begin()+(i+1), R); ///inserting in middle of vector 1379 1380 ///updating the colours of the surrounding non-REDs 1381 if(belt[i].c > R.a) belt[i].colour = GREEN; 1382 else belt[i].colour = BLUE; 1383 1384 int nxt = i+2; if(nxt == (int) belt.size()) nxt = 0; 1385 if(belt[i+1].c > belt[nxt].a) belt[i+1].colour = GREEN; 1386 else belt[i+1].colour = BLUE; 1387 } 1388 else if(belt[i].colour == GREEN){ ///GREEN type event occured, game ends 1389 ans = min(ans, ii(totalMoves + R.pos + 2, belt[i].id)); 1390 } 1391 } 1392 1393 if(ans.first != inf){ 1394 cout << ans.second << " " << ans.first; 1395 return 0; 1396 } 1397 } 1398 } 1399 ``` 1400 1401 **Code (C++) (errorgorn)** 1402 1403 ``` 1404 //雪花飄飄北風嘯嘯 1405 //天地一片蒼茫 1406 1407 #include <bits/stdc++.h> 1408 #include <ext/pb_ds/assoc_container.hpp> 1409 #include <ext/pb_ds/tree_policy.hpp> 1410 #include <ext/rope> 1411 using namespace std; 1412 using namespace __gnu_pbds; 1413 using namespace __gnu_cxx; 1414 #define ll long long 1415 #define ii pair<ll,ll> 1416 #define iii pair<ii,ll> 1417 #define fi first 1418 #define se second 1419 #define endl '\n' 1420 #define debug(x) cout << #x << " is " << x << endl 1421 1422 #define pub push_back 1423 #define pob pop_back 1424 #define puf push_front 1425 #define pof pop_front 1426 #define lb lower_bound 1427 #define up upper_bound 1428 1429 #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 1430 #define all(x) (x).begin(),(x).end() 1431 #define sz(x) (int)(x).size() 1432 1433 #define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> 1434 //change less to less_equal for non distinct pbds, but erase will bug 1435 1436 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 1437 1438 struct dat{ 1439 int a,b,c; 1440 int idx; 1441 }; 1442 1443 int n; 1444 dat head; 1445 deque<dat> dq; 1446 1447 dat state[6005]; 1448 dat trans_belt[6005]; 1449 bool green[6005]; 1450 1451 int curr; 1452 ll moves=1; 1453 1454 void brute(){ 1455 rep(x,0,1000000){ 1456 if ((curr==0?head.a:(curr==1?head.b:head.c))>dq.front().a){ 1457 dq.pub(dq.front()); 1458 dq.pof(); 1459 curr++; 1460 if (curr==3){ 1461 cout<<head.idx<<" "<<moves<<endl; 1462 exit(0); 1463 } 1464 } 1465 else{ 1466 dq.pub(head); 1467 head=dq.front(); 1468 dq.pof(); 1469 curr=1; 1470 } 1471 1472 moves++; 1473 1474 if (x>n && curr==1) break; 1475 } 1476 } 1477 1478 int main(){ 1479 ios::sync_with_stdio(0); 1480 cin.tie(0); 1481 cout.tie(0); 1482 cin.exceptions(ios::badbit | ios::failbit); 1483 1484 cin>>n; 1485 1486 rep(x,0,n){ 1487 int a,b,c; 1488 cin>>a>>b>>c; 1489 1490 if (!x) head={a,b,c,x}; 1491 else dq.pub({a,b,c,x}); 1492 } 1493 1494 curr=0; 1495 brute(); 1496 1497 //convert to state 1498 state[0]=head; 1499 rep(x,1,n) state[x]=dq[x-1]; 1500 1501 while (true){ 1502 //cout<<"move: "<<moves-1<<endl; 1503 //rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl; 1504 1505 vector<ii> stk; 1506 1507 //find the first instance where state[z].b<state[x].a 1508 //maintain min stack of state[z].b 1509 1510 //now, we focus on the belt itself 1511 //there is a case where the red does not convert to a anything but the game ends 1512 //we need to handle that case carefully! 1513 //i think lets just insert it into stack with value -1 1514 //then if it appears its easily handled 1515 1516 memset(green,false,sizeof(green)); 1517 1518 int cnt=0; 1519 1520 int pidx=-1; 1521 rep(x,0,n){ 1522 if (x && state[x-1].b>state[x].a){ //red 1523 1524 } 1525 else{ //not red 1526 if (pidx!=-1 && state[pidx].c>state[x].a){ 1527 green[pidx]=true; 1528 } 1529 1530 pidx=x; 1531 } 1532 } 1533 if (state[pidx].c>state[0].a) green[0]=true; 1534 1535 rep(x,0,n){ 1536 if (x && state[x-1].b>state[x].a){ //red 1537 1538 } 1539 else{ //not red 1540 int temp=green[x]?-1:state[x].b; 1541 1542 while (!stk.empty() && stk.back().fi>temp) stk.pob(); 1543 stk.pub(ii(temp,cnt)); 1544 cnt++; 1545 } 1546 } 1547 1548 int best=1e9; //shortest distance until red becomes not red 1549 int cnt2=cnt; 1550 1551 //cout<<"non-reds: "<<cnt<<endl; 1552 1553 rep(x,0,n){ 1554 if (x && state[x-1].b>state[x].a){ //red 1555 if (stk.front().fi>state[x].a) continue; //it wont become red here 1556 1557 int lo=0,hi=sz(stk),mi; 1558 while (hi-lo>1){ 1559 mi=hi+lo>>1; 1560 if (stk[mi].fi<state[x].a) lo=mi; 1561 else hi=mi; 1562 } 1563 1564 //cout<<"debug: "<<x<<endl; 1565 //for (auto &it:stk) cout<<it.fi<<"_"<<it.se<<" "; cout<<endl; 1566 //cout<<state[x].a<<endl; 1567 1568 //cout<<"found: "<<pos[stk[hi]]<<endl; 1569 int dist=cnt2-stk[lo].se; 1570 //cout<<dist<<endl; 1571 if (dist<best){ 1572 best=dist; 1573 } 1574 1575 //cout<<endl; 1576 1577 } 1578 else{ //not red 1579 int temp=green[x]?-1:state[x].b; 1580 1581 while (!stk.empty() && stk.back().fi>temp) stk.pob(); 1582 stk.pub(ii(temp,cnt2)); 1583 cnt2++; 1584 } 1585 } 1586 1587 //cout<<"number in belt: "<<cnt<<endl; 1588 //cout<<"d: "<<best<<" "<<idx<<endl; 1589 1590 if (best==1e9){ 1591 cout<<"-1 -1"<<endl; 1592 return 0; 1593 } 1594 1595 //we simulate best-1 cycles for the reds 1596 1597 best--; 1598 1599 //cout<<"hmm: "<<endl; 1600 //cout<<best<<" "<<cnt<<endl; 1601 if (best>=0){ 1602 moves+=best*(n-1); 1603 1604 //cout<<endl; 1605 cnt2=0; 1606 rep(x,0,n){ 1607 if (x && state[x-1].b>state[x].a){ //red 1608 1609 } 1610 else{ //not red 1611 trans_belt[cnt2]=state[x]; 1612 cnt2++; 1613 } 1614 } 1615 1616 //rep(x,0,cnt2) cout<<trans_belt[x].idx<<" "; cout<<endl; 1617 1618 rep(x,n,0){ 1619 if (x && state[x-1].b>state[x].a){ //red 1620 1621 } 1622 else{ //not red 1623 cnt2--; 1624 //cout<<x<<" "<<(cnt2-best+cnt)%cnt<<endl; 1625 state[x]=trans_belt[(cnt2-best+cnt)%cnt]; 1626 } 1627 } 1628 } 1629 1630 //cout<<cnt<<endl; 1631 //cout<<"move: "<<moves-1<<endl; 1632 //rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl; 1633 1634 head=state[0]; 1635 dq.clear(); 1636 rep(x,1,n) dq.pub(state[x]); 1637 1638 curr=1; 1639 brute(); 1640 1641 //convert to state 1642 state[0]=head; 1643 rep(x,1,n) state[x]=dq[x-1]; 1644 1645 //cout<<"move: "<<moves-1<<endl; 1646 //rep(x,0,n) cout<<state[x].idx<<" "; cout<<endl; 1647 //cout<<endl; 1648 1649 //break; 1650 } 1651 } 1652 ```