codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ![img](/predownloaded/4e/48/4e48dae183c20890f5e654f88d8ba50e2880929b.png)
    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 ![ ](/predownloaded/04/30/0430080547e6a92a3d96ba3011af85a4e1ed2c10.png)
    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 ![ ](/predownloaded/74/ab/74abe92a094dabd5a1f42cf537ac9457b97e7c95.png)
    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 ![ ](/predownloaded/ff/89/ff8966699d3f169f29b1e05c06b36e1c3ab67a91.png)
    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 ![ ](/predownloaded/26/a1/26a1652b93536d168f4a5cb26498d8b80899a03c.png)
   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 ![ ](/predownloaded/a4/62/a462b15840891649c8e53971192a71e04ea7dbc4.png)
   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 ```