2183.md (60067B)
1 Source: https://codeforces.com/blog/entry/149944 2 3 We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! 4 5 **Rate The Contest!** 6 7 * Great contest 8 * Good contest 9 * Average contest 10 * Bad contest 11 12 ## [2183A — Binary Array Game](https://codeforces.com/contest/2183/problem/A) 13 14 Idea & Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui") 15 16 **Rate The Problem!** 17 18 * Good Problem 19 * Okay Problem 20 * Bad Problem 21 * Didn't Solve 22 23 **Hint 1** 24 25 If the sequence $a$ consists entirely of $1$ s, what will Alice do? 26 27 **Hint 2** 28 29 Consider discussing the values of $a_1$ and $a_n$. 30 31 **Solution** 32 33 First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequence. 34 35 Note that the last operation must involve at least one of $a_1$ or $a_n$. We discuss based on the values of $a_1$ and $a_n$: 36 37 If $a_1 = 1$, then Alice can directly operate on the interval $[2,n]$ to win, because $a_{2 \sim n}$ must contain at least one $0$. 38 39 If $a_n = 1$, then Alice can directly operate on the interval $[1,n-1]$ to win, because $a_{1 \sim n-1}$ must contain at least one $0$. 40 41 If $a_1 = 0$ and $a_n = 0$, then operating on the entire sequence would certainly cause Alice to lose. This implies that Alice cannot operate on both $a_1$ and $a_n$ simultaneously. Therefore, after Alice's operation, there will still be at least one $0$ in the sequence $a$. Bob can then operate on the entire sequence to win. Hence, in this case, Bob wins. 42 43 Time complexity: $O(\sum n)$. 44 45 **Implementation** 46 47 ``` 48 #include<bits/stdc++.h> 49 using namespace std; 50 int _t_,n,a[100010]; 51 void solve() 52 { 53 cin>>n; 54 for(int i=1;i<=n;i++) 55 cin>>a[i]; 56 if(a[1]+a[n]==0) 57 cout<<"NO\n"; 58 else 59 cout<<"YES\n"; 60 } 61 int main() 62 { 63 ios::sync_with_stdio(0); 64 cin.tie(0),cout.tie(0); 65 cin>>_t_; 66 while(_t_--) 67 solve(); 68 return 0; 69 } 70 ``` 71 72 ## [2183B — Yet Another MEX Problem](https://codeforces.com/contest/2183/problem/B) 73 74 Idea & Preparation: [wangmarui](/profile/wangmarui "Grandmaster wangmarui") 75 76 **Rate The Problem!** 77 78 * Good Problem 79 * Okay Problem 80 * Bad Problem 81 * Didn't Solve 82 83 **Hint 1** 84 85 Considering that in the end only $k - 1$ numbers will remain, which numbers in an interval of length $k$ are invalid? 86 87 **Hint 2** 88 89 Consider the Pigeonhole Principle. 90 91 **Solution** 92 93 Since only $k - 1$ numbers will remain in the end, it is relatively easy to notice that for any interval of length $k$, numbers within this interval that are greater than or equal to $k-1$ or have duplicate values are invalid. One of these two types of numbers can be removed. Since there are only $k - 1$ numbers from $0$ to $k-2$, in any interval of length $k$, there must be at least one number that can be deleted. Therefore, the answer is $\min(\text{mex}(a), k-1)$. 94 95 Time complexity: $O(\sum n)$. 96 97 **Implementation** 98 99 ``` 100 #include<bits/stdc++.h> 101 using namespace std; 102 #define re register 103 #define ll long long 104 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++) 105 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--) 106 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 107 #define endl '\n' 108 ll _t_; 109 ll n,m; 110 ll maxn; 111 ll a[1000010]; 112 ll b[1000010]; 113 void _clear(){} 114 void solve() 115 { 116 _clear(); 117 cin>>n>>m; 118 forl(i,1,n) 119 cin>>a[i],a[i]=min(a[i],n+1); 120 forl(i,0,n+5) 121 b[i]=0; 122 ll mex=0; 123 forl(i,1,n) 124 b[a[i]]++; 125 while(b[mex]) 126 mex++; 127 cout<<min(mex,m-1)<<endl; 128 } 129 int main() 130 { 131 IOS; 132 _t_=1; 133 cin>>_t_; 134 while(_t_--) 135 solve(); 136 return 0; 137 } 138 ``` 139 140 ## [2183C — War Strategy](https://codeforces.com/contest/2183/problem/C) 141 142 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error") 143 144 **Rate The Problem!** 145 146 * Good Problem 147 * Okay Problem 148 * Bad Problem 149 * Didn't Solve 150 151 **Hint 1** 152 153 Consider a greedy algorithm. 154 155 **Hint 2** 156 157 What shape must the finally occupied bases take? 158 159 **Hint 3** 160 161 If the capital is the first city (i.e., $k=1$), how to solve it? 162 163 **Claim 1** 164 165 The finally occupied bases must form an interval containing $k$. 166 167 **Proof** 168 169 If the finally occupied bases do not form an interval containing $k$, then there must exist some $x, y$ such that $1 \le x \lt y \lt k$ or $k \lt y \lt x \le n$, with $x$ occupied and $y$ unoccupied. Consider a soldier at $y$ starting from $k$ and moving to $x$; it must pass through base $x$ along the way. Consider making this soldier stop exactly at $x$. Then soldier $y$ ends up at $x$. After a finite number of such adjustments, we will reach a state where no further adjustment is possible, which implies the finally occupied bases must be an interval containing $k$. 170 171 **Claim 2** 172 173 Suppose this interval contains $a$ positions to the left of $k$ and $b$ positions to the right of $k$ (excluding $k$ itself) ($0 \le a \le k-1$, $0 \le b \le n-k$). It is possible to occupy this interval if and only if $a + b + \max(a, b) - 1 \le m$. 174 175 **Proof** 176 177 Sufficiency: 178 179 We can imagine a simple strategy. Initially, we do nothing until the capital contains $a$ soldiers. Then we move $a$ soldiers from $k$ to $k-1$, then move $a-1$ soldiers from $k-1$ to $k-2$, and so on. Thus $k-1, k-2, \ldots, k-a$ are all filled with soldiers. Then we wait (if necessary) until the capital contains $b$ soldiers and move them in the same way to $k+1, \ldots, k+b$. It can be observed that this strategy requires exactly $a + b + \max(a, b) - 1$ days. 180 181 Necessity: 182 183 We prove that for any strategy, the required number of days $m$ is at least $a + b + \max(a, b) - 1$. 184 185 First, we need at least $a+b$ days to obtain the extra $a+b$ soldiers. Second, we cannot move new soldiers to new bases every moment. In fact, we can prove that there are at least $\max(a, b) - 1$ idle days. The proof is as follows. 186 187 Assume without loss of generality that $a \ge b$. 188 189 Define the potential function $h(S)$ of a state $S$ as the number of soldiers minus the number of occupied bases. 190 191 Suppose the first move to the left is moving $t$ soldiers to the leftmost consecutive $t$ positions $k-a, \ldots, k-a+t-1$. 192 193 (If the move is not to the leftmost positions but to some intermediate positions, we can show through adjustment that such a move is suboptimal. Therefore, an optimal solution will not contain such moves.) 194 195 Let $S_0$ be the state before the move, $S_1$ be the state when moving $t$ soldiers to $k-a+t$, $S_2$ be the state after completing the move of all $t$ soldiers, and $S_3$ be the final state. 196 197 We have $h(S_2) = h(S_1)$, $h(S_3) \ge h(S_2)$. 198 199 $h(S_1) - h(S_0) \ge a - t$ (during the intermediate $a-t$ steps, the potential increases each time). 200 201 $h(S_0) \ge t - 1$ (at least $t$ movable soldiers are needed). 202 203 Summing up, we get $h(S_3) \ge a - 1$. Therefore, the number of days needed is at least $2a + b - 1$. 204 205 In summary, at least $a + b + \max(a, b) - 1$ days are required. 206 207 **Solution** 208 209 We consider a greedy approach. First, if $k-1 \lt n-k$, we replace $k$ with $n+1-k$. 210 211 We define two variables $a$ and $b$, representing how many cells have been extended to the left and right, respectively. Initially, $a = 0$, $b = 0$. Then we repeatedly try to increase $a$ and $b$ by $1$ in turns. We first try to increase $b$ by $1$ (if $b \lt n-k$ and $a + (b+1) + \max(a, b+1) - 1 \le m$), then set $b$ to $b+1$. Next, we try to increase $a$ by $1$ (if $a \lt k-1$ and $(a+1) + b + \max(a+1, b) - 1 \le m$). If we cannot increase $a$, we break the loop. Finally, $a + b + 1$ (don't forget the home base) is the answer. The time complexity is $O(n)$. 212 213 **Implementation** 214 215 ``` 216 #include<bits/stdc++.h> 217 using namespace std; 218 int n,k,m; 219 signed main(){ 220 int T; 221 cin>>T; 222 while(T--){ 223 cin>>n>>m>>k; 224 if(k-1<n-k)k=n+1-k; 225 int a=0,b=0; 226 while(1){ 227 if(b<n-k&&a+(b+1)+max(a,b+1)-1<=m)++b; 228 if(a<k-1&&(a+1)+b+max(a+1,b)-1<=m)++a; 229 else break; 230 } 231 cout<<a+b+1<<endl; 232 } 233 } 234 ``` 235 236 **Bonus** 237 238 Solve the problem in $O(1)$ or $O(\log n)$ time per test case. 239 240 ## [2183D1 — Tree Coloring (Easy Version)](https://codeforces.com/contest/2183/problem/D1) 241 242 Idea & Preparation: [jiazhichen844](/profile/jiazhichen844 "Grandmaster jiazhichen844") 243 244 **Rate The Problem!** 245 246 * Good Problem 247 * Okay Problem 248 * Bad Problem 249 * Didn't Solve 250 251 **Hint 1** 252 253 Consider which points cannot be colored in the same operation. 254 255 **Hint 2** 256 257 Find a lower bound for the number of operations. 258 259 **Solution** 260 261 Suppose the number of points at depth $i$ is $t_i$. First, points at the same depth cannot be colored simultaneously, so the lower bound for the answer is $\max t_i$. 262 263 However, note that if points in layer $x$ share a common parent, they and their parent also cannot be colored simultaneously. Thus, the answer must also be compared with $\max(t_x + 1)$. 264 265 We claim this is the answer. Proof follows from the constructive proof in D2. 266 267 ## [2183D2 — Tree Coloring (Hard Version)](https://codeforces.com/contest/2183/problem/D2) 268 269 Idea & Preparation: [jiazhichen844](/profile/jiazhichen844 "Grandmaster jiazhichen844") 270 271 **Rate The Problem!** 272 273 * Good Problem 274 * Okay Problem 275 * Bad Problem 276 * Didn't Solve 277 278 **Hint 3** 279 280 When can the minimum number of operations reach $\max t_i$? How much more than $\max t_i$ can it be at most? 281 282 **Solution 1** 283 284 We claim the maximum number of operations is $\max t_i + 1$. Consider the following constructive proof. 285 286 Let $S_i$ denote the set of points for the $i$ th operation. 287 288 Without loss of generality, let $T=\max t_i$. Find the largest $x$ such that $t_x=T$. Clearly, points with $d_i=x$ cannot be operated on simultaneously; we can place them into $S_1, S_2, \cdots, S_T$ respectively. 289 290 Then we only need to consider placing points of depth $\neq x$ into $S$. First, consider points of depth $ \gt x$. Suppose we have already placed all points of depth $k-1$. Now, when placing points of depth $k$, it is clear that each $S_i$ can contain at most one point of depth $k-1$. 291 292 Now, $t_{k-1}$ sets contain points of depth $k-1$, which impose constraints on the depth $k$ points to be placed; The remaining $T-t_{k-1}$ sets contain no points of depth $k-1$ and can freely add any point of depth $k$ (see the diagram below, where the upper red dots represent sets containing points of depth $k-1$, and the blue dots represent sets without such points). 293 294 295  296 297 298 For restricted sets (where children cannot be placed), we can retain only one child and place the others into unrestricted sets. Since the number of points in the lower layer is strictly less than $T$, at least one unrestricted set will remain. At this point, we can place each retained child into the set to its right. 299 300 Next, we construct the point of depth $ \lt x$. Suppose we have already constructed the point of depth $k+1$. Now we need to place the point of depth $k$ into a set. Clearly, there are $t_{k+1}$ sets with restrictions. Assume the current number of sets is $a = T$ or $T + 1$. The number of unrestricted sets is $c = a - t_{k+1}$. We proceed with some case analysis: 301 302 1. $a=T$ and $c=0$: All points at depth $k+1$ share a common parent. 303 304 This parent cannot be placed into any set. We set $a$ to $T+1$, place the parent into this new set, and assign the remaining points arbitrarily. 305 306 1. Points at depth $k$ have at least two non-leaf neighbors. 307 308 We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily. 309 310 1. A node at depth $k$ has exactly one non-leaf child, and at least one set lacks any node at depth $k+1$. 311 312 Place this father into the set lacking a node at depth $k+1$, then place the remaining nodes arbitrarily. 313 314 The above process constructs a solution with either $T$ or $T+1$ sets. It yields $T+1$ sets precisely when there are $T$ points at the same depth with the same parent, making this process clearly optimal. These sets can be maintained in $O(n)$ or $O(n\log n)$ time. 315 316 Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $O(n\log n)$. 317 318 **Solution 2** 319 320 This solution is from [nldr](/profile/nldr "International Master nldr"). 321 322 Consider the construction scheme. 323 324 We assign each node $u$ a color $c_u \in {1, \dots, k}$ such that: 325 326 If $dep_u = dep_v$ and $u \neq v$, then $c_u \neq c_v$. 327 328 If $u$ is the parent node of $v$, then $c_u \neq c_v$. 329 330 Assign colors layer by layer based on depth. For each layer of $m$ nodes, convert it into a matching problem. 331 332 Select $m$ distinct colors from ${1, \dots, k}$ to assign to these $m$ nodes, ensuring each node does not receive the color of its parent node. 333 334 Consider removing all nodes from the $d+1$th layer. 335 336 Sort them by their parent node's color. This groups child nodes constrained by the same color together. 337 338 Let the sorted nodes be $u_0, u_1, \dots, u_{m-1}$. 339 340 Let their parent node colors be $f_0, f_1, \dots, f_{m-1}$. 341 342 Define: $c_{u_i} = ((i + \Delta) \pmod k) + 1$. 343 344 Here we treat colors as a cycle $0 \dots k-1$ and attempt to assign the sorted nodes $m$ consecutive colors. 345 346 We need to find a $\Delta$ such that for all $i$, $(i + \Delta) \pmod k \neq f_i$. 347 348 That is, $\Delta \not\equiv (f_i - i) \pmod k$. 349 350 We compute all invalid $\Delta$ values (i.e., $(f_i - i) \pmod k$), yielding $m$ constraints in total. 351 352 Since there are $k$ possible values for $\Delta$ and typically $m \lt k$ or constraints overlap, by the Pigeonhole Principle, a valid $\Delta$ must exist under the lower bound definition of $k$. 353 354 In practice, because we've sorted by $f_i$, the constraints form a regular pattern—we only need $\Delta$ to avoid specific values. 355 356 We can enumerate $\Delta$ values from smallest to largest and find the first valid $\Delta$. 357 358 The complexity bottleneck lies in the sorting operation, which is $O(n \log n)$. 359 360 **Implementation (Solution 1)** 361 362 ``` 363 #include<bits/stdc++.h> 364 #define int long long 365 using namespace std; 366 vector<int> e[300005],v[300005],g[300005]; 367 int n,d[300005],t[300005],id[300005],son[300005],snum[300005],fa[300005]; 368 bool flag[300005]; 369 void dfs(int pos,int fa) 370 { 371 ::fa[pos]=fa; 372 d[pos]=d[fa]+1; 373 t[d[pos]]++; 374 g[d[pos]].push_back(pos); 375 for(int x:e[pos]) 376 { 377 if(x==fa) 378 continue; 379 snum[pos]++; 380 dfs(x,pos); 381 } 382 } 383 void test() 384 { 385 cin>>n; 386 for(int i=1;i<=n;i++) 387 e[i].clear(),g[i].clear(),v[i].clear(),d[i]=t[i]=id[i]=snum[i]=0; 388 for(int i=1;i<n;i++) 389 { 390 int u,v; 391 cin>>u>>v; 392 e[u].push_back(v); 393 e[v].push_back(u); 394 } 395 dfs(1,0); 396 int mx=0,mt=0; 397 for(int i=1;i<=n;i++) 398 if(t[i]>=mx) 399 mx=t[i],mt=i; 400 // for(int i=1;i<=n;i++) 401 // cerr<<i<<" "<<fa[i]<<" "<<d[i]<<"\n"; 402 int ans=mx; 403 for(int i=1;i<=mx;i++) 404 id[g[mt][i-1]]=i,v[i].push_back(g[mt][i-1]); 405 for(int i=mt+1;i<=n;i++) 406 { 407 vector<int> vfa; 408 for(int j:g[i-1]) 409 { 410 son[j]=0; 411 if(snum[j]) 412 flag[id[j]]=1; 413 } 414 int pos=1; 415 for(int j:g[i]) 416 { 417 if(!son[fa[j]]) 418 son[fa[j]]=j,vfa.push_back(fa[j]); 419 else 420 { 421 while(flag[pos]) 422 pos++; 423 assert(pos<=mx); 424 id[j]=pos,v[pos].push_back(j),pos++; 425 } 426 } 427 while(flag[pos]) 428 pos++; 429 assert(pos<=mx); 430 int lst=pos; 431 for(int x:vfa) 432 { 433 id[son[x]]=lst; 434 v[lst].push_back(son[x]); 435 lst=id[x]; 436 } 437 for(int j:g[i-1]) 438 flag[id[j]]=0; 439 } 440 for(int i=mt-1;i>=1;i--) 441 { 442 vector<int> vfa; 443 for(int j:g[i]) 444 son[j]=0; 445 for(int j:g[i+1]) 446 { 447 flag[id[j]]=1; 448 if(!son[fa[j]]) 449 son[fa[j]]=j,vfa.push_back(fa[j]); 450 } 451 assert(!vfa.empty()); 452 if(vfa.size()==1) 453 { 454 if(ans==t[i+1]) 455 ans++,id[vfa[0]]=ans,v[ans].push_back(vfa[0]); 456 else 457 { 458 int pos=1; 459 while(flag[pos]) 460 pos++; 461 assert(pos<=ans); 462 id[vfa[0]]=pos,v[pos].push_back(vfa[0]); 463 } 464 } 465 else 466 { 467 for(int i=0;i<vfa.size();i++) 468 id[vfa[i]]=id[son[vfa[(i+1)%vfa.size()]]],v[id[vfa[i]]].push_back(vfa[i]); 469 } 470 for(int j:g[i+1]) 471 flag[id[j]]=0; 472 for(int x:vfa) 473 flag[id[x]]=1; 474 int pos=1; 475 for(int x:g[i]) 476 if(!son[x]) 477 { 478 while(flag[pos]) 479 pos++; 480 assert(pos<=ans); 481 id[x]=pos,v[pos].push_back(x); 482 pos++; 483 } 484 for(int x:vfa) 485 flag[id[x]]=0; 486 } 487 cout<<ans<<"\n"; 488 for(int i=1;i<=ans;i++) 489 { 490 cout<<v[i].size()<<" "; 491 for(int x:v[i]) 492 cout<<x<<" "; 493 cout<<"\n"; 494 } 495 } 496 signed main() 497 { 498 ios::sync_with_stdio(0); 499 cin.tie(0); 500 cout.tie(0); 501 int t; 502 cin>>t; 503 for(int i=1;i<=t;i++) 504 test(); 505 } 506 ``` 507 508 ## [2183E — LCM is Legendary Counting Master](https://codeforces.com/contest/2183/problem/E) 509 510 Idea & Preparation: [Gold14526](/profile/Gold14526 "Grandmaster Gold14526") 511 512 **Rate The Problem!** 513 514 * Good Problem 515 * Okay Problem 516 * Bad Problem 517 * Didn't Solve 518 519 **Hint 1** 520 521 Consider the term $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$. What properties can you derive if $a_i \lt a_{i+1}$? 522 523 **Hint 2** 524 525 Recall that $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})} = \frac{\gcd(a_i,a_{i+1})}{a_i a_{i+1}}$. Notice that when $a_i \lt a_{i+1}$, the inequality $\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$ always holds. 526 527 **Hint 3** 528 529 You might have bounded the sum of the first $n-1$ terms. Try comparing the term $\frac{a_n-a_1}{a_1 a_n}$ (from the telescoping sum) with the last term $\frac{a_1}{a_1 a_n}$. 530 531 **Hint 4** 532 533 If $y \gt x$ and $\gcd(x,y)=y-x$, what does this imply about the relationship between $x$ and $y$? How many such pairs $(x,y)$ exist for $1\le x \lt y \le m$? 534 535 **Solution** 536 537 Note that 538 539 $ \begin{aligned} &\quad \frac{1}{\operatorname{lcm}(a_1,a_2)}+\frac{1}{\operatorname{lcm}(a_2,a_3)}+\cdots+\frac{1}{\operatorname{lcm}(a_{n-1},a_n)}+\frac{1}{\operatorname{lcm}(a_n,a_1)} \\ &= \frac{\gcd(a_1,a_2)}{a_1a_2}+\frac{\gcd(a_2,a_3)}{a_2a_3}+\cdots+\frac{\gcd(a_{n-1},a_n)}{a_{n-1}a_n}+\frac{\gcd(a_1,a_n)}{a_1a_n} \\ &\le \frac{a_2-a_1}{a_1a_2}+\frac{a_3-a_2}{a_2a_3}+\cdots+\frac{a_n-a_{n-1}}{a_{n-1}a_n}+\frac{\color{red}{a_1}}{a_1a_n} \\ &= \left(\frac{1}{a_1}-\frac{1}{a_2}\right)+\left(\frac{1}{a_2}-\frac{1}{a_3}\right)+\cdots+\left(\frac{1}{a_{n-1}}-\frac{1}{a_n}\right)+\frac{1}{a_n} \\ &= \frac{1}{a_1} \\ &\le 1 \end{aligned} $ 540 541 The equality holds if and only if $\gcd(a_i,a_{i+1})=a_{i+1}-a_i$ for all $1\le i \lt n$, and $a_1=1$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions. 542 543 The condition $\gcd(x,y)=y-x$ implies that $y-x$ is a divisor of $x$. In other words, there exists a divisor $d$ of $x$ such that $y=x+d$. Therefore, the total number of such valid pairs $(x,y)$ is only $\mathcal O(m \ln m)$. Consequently, we can easily obtain the answer using dynamic programming with a time complexity of $O(nm\ln m)$. 544 545 **Implementation** 546 547 ``` 548 #include<bits/stdc++.h> 549 #define cint const int 550 #define uint unsigned int 551 #define cuint const unsigned int 552 #define ll long long 553 #define cll const long long 554 #define ull unsigned long long 555 #define cull const unsigned long long 556 using namespace std; 557 namespace FastIO 558 { 559 const int BUF_SIZE=1<<20; 560 char in_buf[BUF_SIZE],out_buf[BUF_SIZE]; 561 char* in_ptr=in_buf+BUF_SIZE; 562 char* out_ptr=out_buf; 563 char get_char() 564 { 565 if(in_ptr==in_buf+BUF_SIZE) 566 { 567 in_ptr=in_buf; 568 fread(in_buf,1,BUF_SIZE,stdin); 569 } 570 return *in_ptr++; 571 } 572 void put_char(char c) 573 { 574 if(out_ptr==out_buf+BUF_SIZE) 575 { 576 fwrite(out_buf,1,BUF_SIZE,stdout); 577 out_ptr=out_buf; 578 } 579 *out_ptr++=c; 580 } 581 struct Flusher 582 { 583 ~Flusher() 584 { 585 if(out_ptr!=out_buf) 586 { 587 fwrite(out_buf,1,out_ptr-out_buf,stdout); 588 } 589 } 590 } flusher; 591 } 592 #define getchar FastIO::get_char 593 #define putchar FastIO::put_char 594 inline int read() 595 { 596 int x=0; 597 bool zf=1; 598 char ch=getchar(); 599 while(ch<'0'||ch>'9') 600 { 601 if(ch=='-') 602 { 603 zf=0; 604 } 605 ch=getchar(); 606 } 607 while(ch>='0'&&ch<='9') 608 { 609 x=(x<<1)+(x<<3)+(ch^48); 610 ch=getchar(); 611 } 612 return zf?x:-x; 613 } 614 void print(cint x) 615 { 616 if(x==0) 617 { 618 putchar('0'); 619 return; 620 } 621 char buf[12]; 622 int len=0,y=x; 623 if(y<0) 624 { 625 putchar('-'); 626 y=-y; 627 } 628 while(y) 629 { 630 buf[len++]=(y%10)+'0'; 631 y/=10; 632 } 633 while(len--) 634 { 635 putchar(buf[len]); 636 } 637 } 638 inline void princh(cint x,const char ch) 639 { 640 print(x); 641 putchar(ch); 642 } 643 cint N=3000,M=3000; 644 cint mod=998244353; 645 int n,m; 646 int a[N+1]; 647 int dp[N+1][M+1]; 648 vector<int>d[M+1]; 649 int ans; 650 void solve() 651 { 652 n=read(); 653 m=read(); 654 for(int i=1;i<=n;++i) 655 { 656 a[i]=read(); 657 } 658 if(a[1]>1) 659 { 660 princh(0,'\n'); 661 return; 662 } 663 dp[1][1]=1; 664 for(int i=2;i<=n;++i) 665 { 666 for(int j=1;j<=m;++j) 667 { 668 dp[i][j]=0; 669 for(int x:d[j]) 670 { 671 (dp[i][j]+=dp[i-1][j-x])>=mod?(dp[i][j]-=mod):0; 672 } 673 } 674 if(a[i]) 675 { 676 for(int j=1;j<=m;++j)if(j!=a[i])dp[i][j]=0; 677 } 678 } 679 ans=0; 680 for(int j=1;j<=m;++j) 681 { 682 (ans+=dp[n][j])>=mod?(ans-=mod):0; 683 } 684 princh(ans,'\n'); 685 } 686 int main() 687 { 688 // freopen(".in","r",stdin); 689 // freopen(".out","w",stdout); 690 for(int i=1;i<=M;++i) 691 { 692 for(int j=i;j<=M;j+=i) 693 { 694 d[j].push_back(i); 695 } 696 } 697 int T=read(); 698 while(T--)solve(); 699 return 0; 700 } 701 ``` 702 703 ## [2183F — Jumping Man](https://codeforces.com/contest/2183/problem/F) 704 705 Idea & Preparation: [Neil_Qian](/profile/Neil_Qian "Candidate Master Neil_Qian") 706 707 **Rate The Problem!** 708 709 * Good Problem 710 * Okay Problem 711 * Bad Problem 712 * Didn't Solve 713 714 **Hint 1** 715 716 Calculating the sum of squares of counts is difficult. 717 718 **Hint 2** 719 720 Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. 721 722 **Hint 3** 723 724 Try dynamic programming. 725 726 **Hint 4** 727 728 The DP transition is continuous over the DFS sequence. 729 730 **Solution** 731 732 Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. 733 734 Let $f_{i,j}$ represent the number of ways to choose two strings located at nodes $i$ and $j$, respectively, within their subtrees. Clearly, $f_{i,j}$ has a non-zero value only if $c_i = c_j$, where $c$ denotes the string sequence. 735 736 Then, $f_{p,q}$ contributes to $f_{i,j}$ if and only if $p$ is in the subtree of $i$ and $q$ is in the subtree of $j$. By performing a depth-first search (DFS) on the tree and marking timestamps, the $(x, y)$ pairs of contributing $f_{p,q}$ must form a rectangle (as in a DFS sequence, each subtree is a range). Sorting by reverse DFS order and computing $2$ — dimensional suffix sums suffices. 737 738 The time complexity is $O(n^2)$. 739 740 **Implementation** 741 742 ``` 743 #include <bits/stdc++.h> 744 745 using namespace std; 746 747 typedef long long ll; 748 749 const int MAXN = 5e3 + 10; 750 const int mod = 998244353; 751 752 inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); } 753 inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; } 754 inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; } 755 756 int T, n, ans[MAXN], sum[MAXN][MAXN]; char s[MAXN]; 757 758 vector<int> g[MAXN]; int in[MAXN], out[MAXN], rev[MAXN], id; 759 760 void init(int u, int f = 0) { 761 in[u] = ++id, rev[id] = u; 762 for (int v : g[u]) if (v != f) init(v, u); 763 out[u] = id; 764 } 765 766 inline 767 int query(int al, int ar, int bl, int br) { 768 return sub(add(sum[al][bl], sum[ar + 1][br + 1]), add(sum[al][br + 1], sum[ar + 1][bl])); 769 } 770 771 int main() { 772 for (scanf("%d", &T); T--; ) { 773 scanf("%d%s", &n, s + 1), id = 0; 774 for (int i = 1, u, v; i < n; i++) { 775 scanf("%d%d", &u, &v); 776 g[u].emplace_back(v), g[v].emplace_back(u); 777 } 778 init(1); 779 for (int i = n; i; i--) { 780 for (int j = n; j; j--) { 781 if (s[rev[i]] == s[rev[j]]) { 782 sum[i][j] = add(query(in[rev[i]] + 1, out[rev[i]], in[rev[j]] + 1, out[rev[j]]), 1); 783 } 784 cadd(sum[i][j], sub(add(sum[i + 1][j], sum[i][j + 1]), sum[i + 1][j + 1])); 785 } 786 } 787 for (int i = 1; i <= n; i++) { 788 printf("%d ", query(in[i], out[i], in[i], out[i])); 789 } 790 puts(""); 791 for (int i = 1; i <= n; i++) g[i].clear(); 792 for (int i = 1; i <= n; i++) { 793 for (int j = 1; j <= n; j++) sum[i][j] = 0; 794 } 795 } 796 } 797 ``` 798 799 ## [2183G — Snake Instructions](https://codeforces.com/contest/2183/problem/G) 800 801 Idea & Preparation: [xvchongyv](/profile/xvchongyv "Expert xvchongyv") & [wangmarui](/profile/wangmarui "Grandmaster wangmarui") 802 803 **Rate The Problem!** 804 805 * Good Problem 806 * Okay Problem 807 * Bad Problem 808 * Didn't Solve 809 810 **Hint 1** 811 812 Consider under what circumstances you need to return $-1$. 813 814 **Answer** 815 816 When there are three consecutive snakes with speeds $0, x, 0$, we cannot determine whether $x$ is $1$ or $2$, so we need to return $-1$ in this case. In all other situations, it's easy to have a scheme that uniquely determines all snakes' speeds. 817 818 **Hint 2** 819 820 Consider what information you can get by querying the string `L`. 821 822 **Hint 3** 823 824 The case analysis process for this problem is not complicated. 825 826 **Hint 4** 827 828 Consider querying three fixed strings to determine all snakes' speeds. 829 830 **Solution** 831 832 Consider querying the three strings: `L`, `LR`, and `R`. 833 834 It can be observed that the sizes of the sets returned from querying `L` and `LR` are the same. The specific proof states that after querying `LR`, the positions of the surviving snakes are exactly their initial positions. Since the relative order of the snakes remains unchanged, performing operation `R` after operation `L` will definitely not cause any two snakes to collide. Therefore, the sizes of the returned sets are the same. 835 836 By establishing a one-to-one correspondence with the initial coordinates, we can easily deduce the speeds of all snakes that survive after performing operation `L`. 837 838 At this point, we only lack the speeds of the snakes that died after performing operation `L`. A simple case analysis reveals the following scenarios (the first number on the right represents the speed of the snake that died after operation `L`, and `_` indicates that there is no snake at that initial position): 839 840 * `01`. 841 * `02`. 842 * `0_2`. 843 * `12`. 844 845 We can directly solve the problem by classifying these cases, but the implementation might be somewhat cumbersome. Therefore, let's consider a more concise approach to the case analysis. 846 847 First, try to determine some snakes with speed $2$. For the position and speed of such a snake, the following cases allow direct determination: 848 849 * The previous snake is at a distance of $1$ and has been determined to have speed $1$. 850 * The previous snake is at a distance of $1$ and has not been determined. Let's explain why this snake's speed is certain in this case: 851 * If the previous snake's speed is $0$, it will definitely not be killed in a collision, so this case is impossible. 852 * If the previous snake's speed is at least $1$, then this snake must have a speed of at least $2$ to catch up and collide with the previous snake. Therefore, this snake's speed is at least $2$. 853 * The previous snake is at a distance of $2$ and has been determined to have speed $0$. 854 855 The case analysis above naturally eliminates the `0_2` and `12` scenarios. 856 857 Now, only the `01` and `02` cases remain. It can be observed that only the patterns `010` and `020` are indistinguishable. Therefore, we can initially ignore this situation: first find one valid solution, and then check if this solution contains such an indistinguishable pattern. 858 859 Otherwise, since the snake immediately after this one must have a speed of at least $1$ (under the condition of a unique solution), the position this snake would reach if it moved ignoring obstacles is exactly the position of the first snake whose position is $\ge$ this snake's position after performing the `R` query. If this snake does not come into contact with any other snake while moving right, its position can also be directly determined. Therefore, we can directly deduce the speeds of all snakes using this method. 860 861 Time complexity: $O(\sum n)$ or $O(\sum n \log n)$. 862 863 **Implementation** 864 865 ``` 866 /* 867 OI 2025 RP++!!! 868 869 author: wmrqwq[alsu] 870 871 time: 2025/7/12 872 873 contest: 874 875 Tips: 876 877 RE, MLE? 878 greedy, dp? 879 natural time? 880 map, umap? 881 giveup rating, get score. 882 brute force, right solution? 883 %mod? std/run/maker/checker? 884 add bruteforce? 885 clear? 886 double, long double? 887 O(n)? O(n^2)! 888 make data! 889 890 last but not least. 891 892 bruteforce -> SegTree? 893 Think more. 894 */ 895 //#pragma GCC optimize("Ofast") 896 //#pragma GCC optimize("unroll-loops") 897 //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") 898 #include<bits/stdc++.h> 899 using namespace std; 900 //#define map unordered_map 901 #define re register 902 #define ll long long 903 #define cll const ll 904 #define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++) 905 #define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--) 906 #define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c)) 907 #define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c)) 908 #define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++) 909 #define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--) 910 #define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c)) 911 #define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c)) 912 #define pii pair<ll,ll> 913 #define mid ((l+r)>>1) 914 #define lowbit(x) (x&-x) 915 #define pb push_back 916 #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 917 // #define endl '\n' 918 #define QwQ return 0; 919 #define db long double 920 #define ull unsigned long long 921 #define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y)) 922 #define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2) 923 #define x first 924 #define y second 925 #define aty cout<<"Yes\n"; 926 #define atn cout<<"No\n"; 927 #define cfy cout<<"YES\n"; 928 #define cfn cout<<"NO\n"; 929 #define xxy cout<<"yes\n"; 930 #define xxn cout<<"no\n"; 931 #define printcf(x) x?cout<<"YES\n":cout<<"NO\n"; 932 #define printat(x) x?cout<<"Yes\n":cout<<"No\n"; 933 #define printxx(x) x?cout<<"yes\n":cout<<"no\n"; 934 #define maxqueue priority_queue<ll> 935 #define minqueue priority_queue<ll,vector<ll>,greater<ll>> 936 #define bug1 cout<<"bug1,AWaDa?\n"; 937 #define bug2 cout<<"bug2,AWaDa!\n"; 938 #define bug3 cout<<"bug3,AKTang?\n"; 939 #define bug4 cout<<"bug4,AKTang!\n"; 940 #define IM (ll)1e9 941 #define LM (ll)1e18 942 #define MIM (ll)-1e9 943 #define MLM (ll)-1e18 944 #define sort stable_sort 945 ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;} 946 ll pw(ll x,ll y,ll mod){if(mod==1)return 0;if(y==0)return 1;if(x==0)return 0;ll an=1,tmp=x;while(y){if(y&1)an=(an*tmp)%mod;tmp=(tmp*tmp)%mod;y>>=1;}return an;} 947 ll pw(ll x){return 1ll<<x;} 948 template<typename T1,typename T2>bool Max(T1&x,T2 y){if(y>x)return x=y,1;return 0;}template<typename T1,typename T2>bool Min(T1&x,T2 y){if(y<x)return x=y,1;return 0;}ll Ss=chrono::steady_clock::now().time_since_epoch().count();mt19937_64 Apple(Ss);ll rand_lr(ll l,ll r){return Apple()%(r-l+1)+l;} 949 // cll mod=1e9+7,N=300010;ll fac[N],inv[N];void init(){fac[0]=1;forl(i,1,N-5)fac[i]=i*fac[i-1],fac[i]%=mod;inv[N-5]=pw(fac[N-5],mod-2,mod);forr(i,N-5,1)inv[i-1]=inv[i]*i%mod;}ll C(ll n,ll m){if(n<m || m<0)return 0;return (fac[n]%mod)*(inv[n-m]*inv[m]%mod)%mod;} 950 // void add(ll&x,ll y){x=((x+y)%mod+mod)%mod;}void del(ll&x,ll y){x=(x%mod-y%mod+mod)%mod;} 951 ll _t_; 952 struct BIT{ 953 ll maxn; 954 ll tree[1000010]; 955 void clear(ll l){ 956 forl(i,0,l) 957 tree[i]=0; 958 } 959 void add(ll x,ll y){ 960 for(;x<=maxn;x+=lowbit(x)) 961 tree[x]+=y; 962 } 963 ll query(ll x){ 964 ll S=0; 965 for(;x;x-=lowbit(x)) 966 S+=tree[x]; 967 return S; 968 } 969 ll query(ll l,ll r){ 970 return query(r)-query(l-1); 971 } 972 }; 973 // ll lg[1000010]; 974 void Init(){ 975 // forl(i,2,1e6+5) 976 // lg[i]=lg[i>>1]+1; 977 } 978 //sunny 979 ll n; 980 ll a[100010]; 981 ll ans[100010]; 982 vector<ll>vl,vr,vlr; 983 //tulpa 984 void ask(string s,vector<ll>&v) 985 { 986 cout<<"? "<<s<<endl; 987 v.pb(rd()); 988 forl(i,1,v[0]) 989 v.pb(rd()); 990 } 991 /* 992 012 993 994 01 995 02 996 997 120 998 */ 999 void _clear(){} 1000 void solve() 1001 { 1002 _clear(); 1003 vl.clear(),vr.clear(),vlr.clear(); 1004 cin>>n; 1005 forl(i,1,n) 1006 cin>>a[i], 1007 ans[i]=-1; 1008 ask("L",vl),ask("R",vr),ask("LR",vlr); 1009 ll sz=vlr[0],L=1; 1010 forl(i,1,n) 1011 { 1012 while(L<=sz && vlr[L]<a[i]) 1013 L++; 1014 if(L<=sz && vlr[L]==a[i]) 1015 ans[i]=vlr[L]-vl[L]; 1016 } 1017 forl(i,2,n) 1018 if(ans[i]==-1 && ((a[i]-a[i-1]==1 && abs(ans[i-1])==1) || (a[i]-a[i-1]==2 && ans[i-1]==0))) 1019 { 1020 // if(ans[i-1]==-1) 1021 // ans[i-1]=1; 1022 ans[i]=2; 1023 } 1024 forl(i,1,n) 1025 if(ans[i]==-1) 1026 ans[i]=*lower_bound(vr.begin()+2,vr.end(),a[i])-a[i]; 1027 forl(i,1,n-2) 1028 if(a[i]+1==a[i+1] && a[i+1]+1==a[i+2] && ans[i]+ans[i+2]==0 && ans[i+1]) 1029 { 1030 cout<<"! "<<-1<<endl; 1031 return ; 1032 } 1033 cout<<"! "; 1034 forl(i,1,n) 1035 cout<<ans[i]<<' '; 1036 cout<<endl; 1037 } 1038 int main() 1039 { 1040 Init(); 1041 // freopen("tst.txt","r",stdin); 1042 // freopen("sans.txt","w",stdout); 1043 IOS; 1044 _t_=1; 1045 cin>>_t_; 1046 while(_t_--) 1047 solve(); 1048 QwQ; 1049 } 1050 ``` 1051 1052 ## [2183H — Minimise Cost](https://codeforces.com/contest/2183/problem/H) 1053 1054 Idea & Preparation: [Hoks_](/profile/Hoks_ "Grandmaster Hoks_") Special Thanks: [Sorasaki_Hina](/profile/Sorasaki_Hina "Master Sorasaki_Hina") 1055 1056 **Rate The Problem!** 1057 1058 * Good Problem 1059 * Okay Problem 1060 * Bad Problem 1061 * Didn't Solve 1062 1063 **Hint 1** 1064 1065 Subsequences are too hard; can we find some properties? How should we approach the case where $k\le n\le500$? 1066 1067 **Hint 2** 1068 1069 The approach for $k\le n\le500$ is too naive; how can we optimize it? What if $k\le n\le5000$? 1070 1071 **Hint 3** 1072 1073 What if we are guaranteed that the count of positive numbers $m \le 5000$? 1074 1075 **Hint 4** 1076 1077 The requirement of **exactly** $k$ segments, combined with the previous optimizations, suggests what technique? Consider the data constraints. 1078 1079 **Solution** 1080 1081 Sort $a$ in non-decreasing order. The cost of a group depends only on the multiset of its values, so the original positions are irrelevant. 1082 1083 **Lemma 1 (canonical form).** There exists an optimal partition whose groups are contiguous blocks in the sorted array. If their lengths are $l_1,l_2,\dots,l_k$ in order of increasing values, then $l_1\ge l_2\ge\cdots\ge l_k$. 1084 1085 **Proof of Lemma 1** 1086 1087 Fix the block sizes. Every element is multiplied by the size of its block, so the total cost is a dot product between the values and a multiset of multipliers in which every block size $\ell$ occurs exactly $\ell$ times. By the rearrangement inequality, pairing values in non-decreasing order with multipliers in non-increasing order does not increase the cost. Regrouping equal multipliers into blocks of the corresponding sizes gives contiguous blocks with non-increasing lengths. 1088 1089 Henceforth, partitions are partitions of the sorted array into contiguous blocks. Let $S_0=0$, $S_i=a_1+\cdots+a_i$, and 1090 1091 $C(j,i)=(i-j)(S_i-S_j)$ 1092 1093 be the cost of the block $a_{j+1}\dots a_i$. If $f_{t,i}$ is the minimum cost of partitioning the first $i$ elements into exactly $t$ blocks, then 1094 1095 $f_{t,i}=\min_{0\le j \lt i}\bigl(f_{t-1,j}+C(j,i)\bigr),$ 1096 1097 which gives an $O(n^2k)$ algorithm if evaluated directly. 1098 1099 For $0\le a\le b\le c\le d\le n$, expansion gives 1100 1101 $\bigl(C(a,d)+C(b,c)\bigr)-\bigl(C(a,c)+C(b,d)\bigr)=(d-c)(S_b-S_a)+(b-a)(S_d-S_c). \tag{1}$ 1102 1103 If all elements are non-negative, the right-hand side is non-negative, so 1104 1105 $C(a,c)+C(b,d)\le C(a,d)+C(b,c). \tag{2}$ 1106 1107 This quadrangle inequality (QI) implies decision monotonicity in each DP layer, and therefore an $O(nk)$ algorithm for non-negative arrays. For arbitrary signs, (2) may fail. 1108 1109 Let 1110 1111 $z=\#\{i:a_i\le 0\},\qquad m=n-z=\#\{i:a_i \gt 0\}.$ 1112 1113 Thus $0$ is grouped with the non-positive elements. Let $\mathcal P_0$ be the partition whose first block contains the smallest $n-k+1$ elements and whose other blocks are singletons; its cost is 1114 1115 $\operatorname{base}=(n-k+1)S_{n-k+1}+\bigl(S_n-S_{n-k+1}\bigr). \tag{3}$ 1116 1117 **Lemma 2 (boundary shift).** In a canonical partition with at least two blocks, let the first two block lengths be $p\ge q$. If $q\ge2$ and the first element $x$ of the second block satisfies $x\le0$, moving $x$ into the first block does not increase the cost. 1118 1119 **Proof of Lemma 2** 1120 1121 Let $A$ be the sum of the first block and $U$ the sum of the second block after removing $x$. The move changes the cost by 1122 1123 $\bigl((p+1)(A+x)-pA\bigr)+\bigl((q-1)U-q(x+U)\bigr)=A-U+(p+1-q)x.$ 1124 1125 All elements of the first block are at most $x$, so $A\le px$; all elements counted in $U$ are at least $x$, so $U\ge(q-1)x$. Hence $A-U\le(p-q+1)x\le0$, using $p\ge q$ and $x\le0$. Also $(p+1-q)x\le0$. 1126 1127 After a shift, reapply Lemma 1 to the later blocks. The first block has grown and remains a longest block, so its set of elements is unchanged by this reordering. If $k=1$, then $\mathcal P_0$ is the unique partition; below let $k\ge2$. 1128 1129 **Case 1: $k \gt m$.** Then $\mathcal P_0$ is optimal. Indeed, in a canonical partition, if the second block is a singleton then all later blocks are singletons. Otherwise its first element must be non-positive: if it were positive, all remaining elements would be positive, at most $m$ elements in $k-1\ge m$ blocks, forcing all those blocks to be singletons. Lemma 2 therefore moves the first cut one step right without increasing the cost. Repeating ends at $\mathcal P_0$. In particular, all positive elements are singletons. 1130 1131 **Case 2: $k\le m$.** There is an optimal partition whose first block contains all non-positive elements. To see this, let the first cut be $b \lt z$ in a canonical optimal partition. The second block starts with a non-positive element. It cannot be a singleton: otherwise all later blocks would be singletons and $b=n-k+1\ge n-m+1=z+1$, a contradiction. Lemma 2 hence increases $b$ by one without increasing the cost. Repeating gives $b\ge z$. Later blocks are then positive, although the first block may also contain positive elements. 1132 1133 This structural form with monotone DP on the positive suffix gives $O(nk)$. For the full constraints, use Aliens' trick. Its inner DP requires QI also for transitions from cut $0$, and deleting cuts inside the non-positive prefix is not enough: for $a=(-100,1,1,1)$ and $(a,b,c,d)=(0,2,3,4)$, the right-hand side of (1) is negative. We extend the forced prefix further. 1134 1135 Start with $T=z$. While $t=T+1\le n$ satisfies 1136 1137 $tS_t-(t-1)S_{t-1} \lt a_t, \tag{4}$ 1138 1139 increase $T$ to $t$. The left side is the marginal cost of appending $a_t$ to the first $t-1$ elements as one block. 1140 1141 **Claim.** For $k\le m$, there is an optimal partition whose first cut is at least $T$, unless it is $\mathcal P_0$. 1142 1143 **Proof of the claim** 1144 1145 Take a canonical optimal partition whose first block contains all non-positive elements and whose first cut is $b \lt T$. Put $t=b+1$. Then $a_t \gt 0$ and (4) holds. If the second block has length $L\ge2$ and its remaining sum after removing $a_t$ is $U \gt 0$, moving $a_t$ into the first block changes the cost by 1146 1147 $\bigl(tS_t-(t-1)S_{t-1}\bigr)-La_t-U \lt 0,$ 1148 1149 because the bracket is less than $a_t$ by (4). Reapply Lemma 1 to the later blocks and repeat. If at some stage the second block is a singleton in canonical form, all later blocks are singletons, so the partition is $\mathcal P_0$. 1150 1151 Thus, apart from $\mathcal P_0$, only cuts in 1152 1153 $\mathcal J=\{0\}\cup\{j:T\le j \lt n\} \tag{5}$ 1154 1155 are needed. If $T \gt n-k+1$, no partition with first cut in $\mathcal J$ has $k$ blocks, so the answer is $\operatorname{base}$. If $T\le n-k+1$, then $\mathcal P_0$ itself uses only cuts from $\mathcal J$. 1156 1157 **Lemma 3.** Inequality (2) holds for all $a,b\in\mathcal J$ with $a\le b\le c\le d$. 1158 1159 **Proof of Lemma 3** 1160 1161 If $a\ge T$, all elements after $a$ are positive, so both differences in (1) are non-negative. Let $a=0$ and $b\ge T$. Then (1) becomes 1162 1163 $(d-c)S_b+b(S_d-S_c). \tag{6}$ 1164 1165 Since $c\ge b\ge T\ge z$, we have $S_d-S_c\ge(d-c)a_{b+1}$. It remains to prove $S_b+b a_{b+1}\ge0$ for $T\le b \lt n$. 1166 1167 If $T \lt n$, failure of (4) at $t=T+1$ gives $(T+1)S_{T+1}-TS_T\ge a_{T+1}$, equivalently $S_T+T a_{T+1}\ge0$. For $b \gt T$, both $S_b\ge S_T$ and $b a_{b+1}\ge T a_{T+1}$, since the added elements are positive and $a_{T+1} \gt 0$. Hence $S_b+b a_{b+1}\ge0$ for all $b\ge T$, and (6) is at least $(d-c)(S_b+b a_{b+1})\ge0$. 1168 1169 Let $G(t)$ be the minimum cost of a partition into exactly $t$ blocks using cuts from $\mathcal J$, where $1\le t\le n-T+1$. 1170 1171 **Lemma 4.** $G$ is convex: $G(t-1)+G(t+1)\ge2G(t)$ for $2\le t\le n-T$. 1172 1173 **Proof of Lemma 4** 1174 1175 Let optimal partitions with $t-1$ and $t+1$ blocks have cut sequences $0=x_0 \lt \cdots \lt x_{t-1}=n$ and $0=y_0 \lt \cdots \lt y_{t+1}=n$. Choose the smallest $j\in[1,t-1]$ with $y_{j+1}\le x_j$; it exists since $y_t \lt n=x_{t-1}$, and minimality gives $x_{j-1} \lt y_j \lt y_{j+1}\le x_j$. 1176 1177 Exchange the suffixes after this crossing: use the first partition up to $x_{j-1}$, the block $(x_{j-1},y_{j+1}]$, and the second partition after $y_{j+1}$; symmetrically, use the second partition up to $y_j$, the block $(y_j,x_j]$, and the first partition after $x_j$. Both resulting partitions have $t$ blocks and cuts in $\mathcal J$. They differ from the original pair only in the crossing blocks, where Lemma 3 gives 1178 1179 $C(x_{j-1},y_{j+1})+C(y_j,x_j)\le C(x_{j-1},x_j)+C(y_j,y_{j+1}).$ 1180 1181 Hence the sum of their costs is at most $G(t-1)+G(t+1)$, while each cost is at least $G(t)$. 1182 1183 Now apply Aliens' trick. For an integer reward $\mu$ per block, let $\operatorname{check}(\mu)$ be the minimum of $\text{cost}-\mu\cdot(\text{number of blocks})$ over partitions with cuts in $\mathcal J$, and let $\operatorname{cnt}(\mu)$ be the corresponding number of blocks, with ties broken toward fewer blocks. Adding the same constant $-\mu$ to every block preserves (2). By Lemma 4, $\operatorname{cnt}(\mu)$ is non-decreasing in $\mu$. For the largest $\mu$ with $\operatorname{cnt}(\mu)\le k$, the standard recovery gives $G(k)=\operatorname{check}(\mu)+\mu k$. The answer is $\min(\operatorname{base},G(k))$. 1184 1185 To compute $\operatorname{check}(\mu)$, let $dp[i]$ be the optimal pair (penalised value, block count) for the first $i$ elements; in the implementation, `ck(mu)` evaluates this DP and returns whether the resulting block count is at most $k$. Then $dp[0]=(0,0)$ and, for $i\ge\max(T,1)$, 1186 1187 $dp[i]=\min_{j\in\mathcal J,\ j \lt i}\bigl(dp[j]+C(j,i)-\mu\bigr),$ 1188 1189 with the block count increased by $1$ in each transition. In the code, `a` is overwritten by the prefix sums $S$, `p` is $\max(T,1)$, the precomputed `ans` is $\operatorname{base}$, and `calc(i,j,mu)` evaluates the transition above. 1190 1191 By Lemma 3, the optimal $j$ is monotone in $i$. The queue `q` stores candidate cuts in increasing order, and `lim[idx]` is the first right endpoint at which `q[idx + 1]` is at least as good as `q[idx]`. Removing front candidates with `lim[l] <= i` therefore leaves an optimal cut for $dp[i]$. To insert $i$, `find(i,q[r],mu)` binary-searches the first endpoint where $i$ beats the tail candidate `q[r]`; if this point is at most `lim[r - 1]`, then `q[r]` never becomes optimal and is discarded. Each cut enters and leaves the queue once, so one check takes $O(n\log n)$ time. 1192 1193 The binary search over $\mu$ needs $O(\log V)$ checks, where $V=O(n^2\max_i|a_i|)$. The total complexity is $O(n\log n\log V)$ time and $O(n)$ memory per test case after sorting. All costs are stored in `__int128`. 1194 1195 **Implementation** 1196 1197 ``` 1198 #include <bits/stdc++.h> 1199 using namespace std; 1200 1201 #define S cerr << "SYT AK IOI" << endl; 1202 #define M cerr << "MKF AK IOI" << endl; 1203 1204 using ll = long long; 1205 using pii = pair<int, int>; 1206 using uint = unsigned int; 1207 using ull = unsigned long long; 1208 mt19937 rnd(0 ^ (*new int)); 1209 // #define int long long //use it if possible 1210 #define pb(x) push_back(x) 1211 #define F(i, a, b) for (int i = (a), i##end = (b); i <= (i##end); ++i) 1212 #define UF(i, a, b) for (int i = (a), i##end = (b); i >= (i##end); --i) 1213 #define gc() getchar() 1214 #define pc putchar 1215 #define popcount(x) __builtin_popcount(x) 1216 1217 inline void init(); 1218 inline void IO(); 1219 __int128 n,k,p; 1220 __int128 a[1000100],lim[1000100],q[1000100]; 1221 array<__int128,2>dp[1000100]; 1222 ll rd() 1223 { 1224 ll x; 1225 cin>>x; 1226 return x; 1227 } 1228 inline array<__int128,2> calc(__int128 i,__int128 j,__int128 x){ 1229 return (array<__int128,2>){dp[j][0]+(i-j)*(a[i]-a[j])-x,dp[j][1]+1}; 1230 } 1231 inline bool c2(__int128 x,__int128 i,__int128 j,__int128 m){ 1232 return calc(x,j,m)>=calc(x,i,m); 1233 } 1234 inline __int128 find(__int128 i,__int128 j,__int128 m){ 1235 int l=i,r=n,mid,res=n+1; 1236 while(l<=r) c2(mid=l+r>>1,i,j,m)?res=mid,r=mid-1:l=mid+1; 1237 return res; 1238 } 1239 inline __int128 ck(__int128 mid){ 1240 for(__int128 i=p,l=1,r=1;i<=n;i++){ 1241 for(;l<r&&lim[l]<=i;l++);dp[i]=calc(i,q[l],mid); 1242 for(;l<r&&lim[r-1]>=find(i,q[r],mid);r--); 1243 lim[r]=find(i,q[r],mid);q[++r]=i; 1244 } 1245 return dp[n][1]<=k; 1246 } 1247 void print(__int128 x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');} 1248 inline void mian() 1249 { 1250 // cin>>n>>k; 1251 n=rd(),k=rd(); 1252 F(i,1,n)a[i]=rd(); 1253 sort(a+1,a+1+n); 1254 F(i,2,n)a[i]+=a[i-1]; 1255 if(k==1){print(n*a[n]);putchar('\n');return;} 1256 __int128 ans=(n-k+1)*a[n-k+1]+a[n]-a[n-k+1];p=1; 1257 while(p<=n and a[p]-a[p-1]<=0)p++; 1258 while(p<=n and p*a[p]-a[p]+a[p-1]<(p-1)*a[p-1])p++; 1259 --p,p=max(p,(__int128)1); 1260 if(n-p<k-1){print(ans);putchar('\n');return;} 1261 __int128 l=-n*n*(__int128)(1e9),r=-l,mid,res=l; 1262 while(l<=r) ck(mid=l+r>>1)?res=mid,l=mid+1:r=mid-1; 1263 ck(res); 1264 ans=min(ans,(__int128)k*res+dp[n][0]); 1265 print(ans);putchar('\n'); 1266 } 1267 signed main() 1268 { 1269 IO(); 1270 cin.tie(nullptr)->sync_with_stdio(false); 1271 int T = 1; 1272 #define multitest 1 1273 #ifdef multitest 1274 T=rd(); 1275 #endif 1276 init(); 1277 1278 while (T--) 1279 mian(); 1280 return 0; 1281 } 1282 1283 inline void init() 1284 { 1285 } 1286 1287 #define NAME(x) #x 1288 #define INNAME(x) NAME(x) 1289 // #define FILEIO sub3_15 1290 inline void IO() 1291 { 1292 #ifdef FILEIO 1293 freopen(INNAME(FILEIO) ".in", "r", stdin), freopen(INNAME(FILEIO) ".out", "w", stdout); 1294 #endif 1295 } 1296 ``` 1297 1298 ## [2183I1 — Pairs Flipping (Easy Version)](https://codeforces.com/contest/2183/problem/I1) 1299 1300 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error") Special Thanks: [N_z__](/profile/N_z__ "International Grandmaster N_z__") 1301 1302 **Rate the problem** 1303 1304 * Good Problem 1305 * Okay Problem 1306 * Bad Problem 1307 * Didn't Solve 1308 1309 **Hint 1** 1310 1311 What if $s=1111\ldots$? 1312 1313 **Hint 2** 1314 1315 Try dividing the sequence into two equal halves, eliminating both halves by assigning odd and even lengths respectively. 1316 1317 **Hint 3** 1318 1319 Try processing recursively to reduce $n$ to a smaller scale. 1320 1321 **Hint 4** 1322 1323 Try further optimizing one of the two halves. 1324 1325 **Solution** 1326 1327 If $n$ is even, we only consider $s_1s_2\ldots s_{n-1}$. Now assume that $n$ is odd. Let $m=\frac{n-1}2$. 1328 1329 Consider dividing the $n$ numbers into the first $m$ and the last $m+1$ parts. The first $m$ are eliminated using odd lengths in $[1,m-1]$, and the last $m+1$ are eliminated using even lengths in $[1,m]$. (Assume that $m$ is even; it is similar when $m$ is odd.) 1330 1331 Let $solvePartially(l,r,p)$ denote the process of considering that there are 1s only in the interval $[l,r]$ and at some position $p$ outside $[l,r]$, and only using lengths in $[1,r-l]$ to eliminate. If $s_l=s_r=0$ or $s_l=s_r=1$, we operate on $l,r$ and recurse to $solvePartially(l+1,r-1,p)$; otherwise, assume that $s_l=1,s_r=0$ and $r \lt p$. If $p-(r-l)\in [l+1,r-1]$, we operate on $p-(r-l),p$ and then recurse to $solvePartially(l+1,r-1,l)$. Otherwise, the $1$ at $p$ is difficult to eliminate. Note that this situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times, so we have obtained a solution with $c\le 2\left\lfloor\log_3\frac{n}2\right\rfloor+2$, roughly $24$ in the constraints of the problem, which is not acceptable. 1332 1333 Proof that the above situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times: 1334 1335 * Note that the occurrence of an impossible elimination necessarily comes with $p-(r-l)\ge r$. Let $q+p=l+r$; then we must have $3(r-l)\le p-q$. Since $1\le r-l\le \frac{n}2$, it can happen at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times. In other words, each time an elimination is impossible, the interval length must reduce to $1/3$ of its original length. 1336 1337 In the above approach, the left and right sides are almost independent. Since operations on the left side are allowed to extend to the right side, we try to eliminate the left side completely. Let $solveCompletely(l,r,p)$ denote that the interval $[l,r]$ except for some position $p$ on the left side has been completely eliminated, and that we still need to eliminate position $p$ together with parts outside $[l,r]$. If $s_l=s_r=1$ or $s_l=s_r=0$, we eliminate $l,r$ and recurse to $solveCompletely(l-1,r+1,p)$; otherwise, assume that $s_l=1,s_r=0$, we eliminate $p,p+r-l$ and then recurse to $solveCompletely(l-1,r+1,l)$. In this way, for the left half, we can reduce it to a single remaining position $p$. Finally, we have optimised to $c\le \left\lfloor\log_3 \frac n2\right\rfloor+2$, which is below $14$ under the constraints of this problem. The code is easy to implement. 1338 1339 **Code** 1340 1341 ``` 1342 #include <bits/stdc++.h> 1343 using namespace std; 1344 signed main() { 1345 ios_base::sync_with_stdio(false); 1346 cin.tie(0); 1347 int t; 1348 cin >> t; 1349 while(t--) { 1350 int n; 1351 cin >> n; 1352 string a; 1353 cin >> a; 1354 vector<int> ops(n/2+5); 1355 auto operate = [&](int i)->void{ 1356 if(ops[i]==0) return; 1357 else { 1358 a[ops[i]-1]^=1; 1359 a[ops[i]-1+i]^=1; 1360 } 1361 }; 1362 auto solveCompletely = [&](auto self, int l, int r, int x)->void{ 1363 if(l>r) return; 1364 if(a[l]==a[r]) { 1365 if(a[l]=='1') ops[r-l]=l+1, operate(r-l); 1366 self(self, l+1, r-1, x); 1367 return; 1368 } 1369 if(x!=-1 && x<l) { 1370 if(x+r-l>=l) { 1371 ops[r-l]=x+1, operate(r-l); 1372 } 1373 } else if(x!=-1 && x>r) { 1374 if(x-r+l<=r) { 1375 ops[r-l]=x-r+l+1, operate(r-l); 1376 } 1377 } 1378 if(a[l]=='1') { 1379 self(self, l+1, r-1, l); 1380 } else { 1381 self(self, l+1, r-1, r); 1382 } 1383 }; 1384 auto solvePartially = [&](auto self, int l, int r)->int{ 1385 if(l>r) return -1; 1386 if(l==r) if(a[l]=='1') return l; else return -1; 1387 int x = self(self, l+1, r-1); 1388 if(a[l]==a[r]) { 1389 if(a[l]=='1') ops[r-l]=l+1, operate(r-l); 1390 return x; 1391 } else { 1392 if(x!=-1) { 1393 ops[r-l]=x+1, operate(r-l); 1394 } 1395 if(a[l]=='1') return l; 1396 else return r; 1397 } 1398 }; 1399 solvePartially(solvePartially, 0, (n-1)/2-1); 1400 if(n%2) solveCompletely(solveCompletely, (n-1)/2, n-1, -1); 1401 else solveCompletely(solveCompletely, (n-1)/2, n-2, -1); 1402 for(int i=1; i<=n/2; i++) cout << ops[i] << " "; 1403 cout << endl; 1404 } 1405 return 0; 1406 } 1407 ``` 1408 1409 ## [2183I2 — Pairs Flipping (Hard Version)](https://codeforces.com/contest/2183/problem/I2) 1410 1411 Idea & Preparation: [Network_Error](/profile/Network_Error "Grandmaster Network_Error") 1412 1413 **Rate the problem** 1414 1415 * Good Problem 1416 * Okay Problem 1417 * Bad Problem 1418 * Didn't Solve 1419 1420 **Solution** 1421 1422 In the I1 approach, we can observe that the main cost arises from isolated $1$'s outside the interval that occasionally cannot be eliminated. We consider optimizing this situation. 1423 1424 The following diagram illustrates a scenario where such an elimination fails: 1425 1426 ``` 1427 1111111111111|1??????0|1111111111110 1428 p l r q 1429 ``` 1430 1431 Here, $p$ is the previous $1$ we could not eliminate (without loss of generality, assume $p \lt l$), the current interval being processed is $[l,r]$, and $l-p \ge r-l$ (making it impossible to eliminate directly using the previous method). $q$ is the symmetric point of $p$. 1432 1433 At this point, the operation lengths we can use are $q-p-2, q-p-4, q-p-6, \ldots, r-l$. Note that $q-p$ is excluded because we have already used it earlier. 1434 1435 Let the lengths of the three segments be $A$, $B$, and $C$, where $A=C$. This scenario is denoted as $F(A,B,C)$. 1436 1437 Next, we will study in detail how to eliminate for $F(A,B,C)$. 1438 1439 If $A \lt B-1$, we have essentially solved it in I1. 1440 1441 For example, in a simple case where $r-l = l-p$ and $s_l=1, s_r=0$, we can apply an operation of length $r-l$ on $p$ and $l$, thereby eliminating both $p$ and $l$ simultaneously. 1442 1443 For other cases, we can show that there is always a method to eliminate until only one $1$ remains, and this remaining $1$ can only be at one of the positions $l, l-1, l-2, r, r+1, r+2$. This part can be resolved through case analysis. 1444 1445 Specifically, we only need to consider three cases: $A=B$, $A=B+1$, or $A=B-1$. If the case falls outside these three, such as $A',B',C'$, we always shift the interval inward and transform it into $A'-1, B'+2, C'-1$. 1446 1447 We take $F(B-1,B,B-1)$ as an example to discuss the specific method. 1448 1449 We further discuss based on $s_l$ and $s_r$. For convenience, we label the positions starting from $p$ as $0, \ldots, q-p$, and use a sequence to represent the positions operated on in order of decreasing length. Let the maximum available length be $L = q-p-2$. For example, the sequence $0,3,1$ means we first use an operation of length $L$ on $p$ and $p+L$, then use an operation of length $L-2$ on $p+3$ and $p+3+(L-2)$, and finally use an operation of length $L-4$ on $p+1$ and $p+1+(L-4)$. 1450 1451 1. $s_l = s_r = 0$. We operate in order: $[0,1,2,\ldots,B-4], 2B-5, B-3$. Finally, a $1$ remains at index $B-2$. 1452 2. $s_l = 1, s_r = 0$. We operate in order: $0, [(3,2),(5,4),(7,6),\ldots,(B-3,B-4)], B-1, 1$. Finally, a $1$ remains at index $B-2$. 1453 3. $s_l = 0, s_r = 1$. We operate in order: $[0,1,2,\ldots,B-3], 2B-3$. Finally, a $1$ remains at index $B-2$. 1454 4. $s_l = s_r = 1$. We operate in order: $[1,2,3,\ldots,B-2], 0$. Finally, a $1$ remains at index $2B-2$. 1455 1456 Similarly, elimination methods for $F(B,B,B)$ and $F(B+1,B,B+1)$ can be obtained. 1457 1458 Thus, between every two adjacent $1$'s that cannot be eliminated, we can always save one elimination, leaving a $1$ within a distance of at most $2$ from $l$ or $r$. Let the interval length be $s$. Whenever a $1$ cannot be eliminated, $s$ becomes at least $\frac19 s + \frac{2}{3}$. Therefore, the number of remaining $1$'s is approximately $\log_9\frac{n}{2}+O(1)$. Note that when the interval length is small, it may consume many $1$'s. A constant optimization is that when the recursion interval length does not exceed $18$, we can use an $O(n^2 2^n)$ dynamic programming approach to easily find the optimal solution, and the optimal solution can always leave no more than $1$ remaining $1$. Additionally, there are other optimizations, such as running the algorithm forward and backward on the sequence and taking the better result. All of these can pass. 1459 1460 It can be proven that when $n \le 2 \times 10^6$, the total number of $1$'s does not exceed $7$. 1461 1462 **Code** 1463 1464 ``` 1465 #include<bits/stdc++.h> 1466 using namespace std; 1467 1468 const int N=2e6,DB=20; 1469 int n,a[N+1]; 1470 int ans[N+1]; 1471 int mid; 1472 inline void op(int x,int y) 1473 { 1474 if(x>y)swap(x,y); 1475 ans[y-x]=x; 1476 a[x]^=1; 1477 a[y]^=1; 1478 } 1479 inline void del(int x,int y) 1480 { 1481 if(x>y)swap(x,y); 1482 if(!ans[y-x])return; 1483 ans[y-x]=0; 1484 a[x]^=1; 1485 a[y]^=1; 1486 } 1487 #define ppc __builtin_popcount 1488 namespace DP{ 1489 int n; 1490 bool f[DB+1][1<<DB+1]; 1491 int g[DB+1][1<<DB+1]; 1492 void dp() 1493 { 1494 n=DB; 1495 f[n][0]=1; 1496 for(int S=1;S<(1<<n);S<<=1)f[n][S]=1; 1497 for(int len=n;len>=2;len-=2) 1498 { 1499 for(int S=0;S<(1<<n);S++) 1500 { 1501 if(!f[len][S])continue; 1502 f[len-2][S]=1; 1503 g[len-2][S]=-1; 1504 for(int i=0;i+len-1<n;i++) 1505 { 1506 f[len-2][S^(1<<i)^(1<<(i+len-1))]=1; 1507 g[len-2][S^(1<<i)^(1<<(i+len-1))]=i; 1508 } 1509 } 1510 } 1511 } 1512 vector<int>ask(int S) 1513 { 1514 int len=0; 1515 vector<int>ans(n+2); 1516 while(len<n) 1517 { 1518 int pos=g[len][S]; 1519 ans[len+1]=pos; 1520 if(pos!=-1) 1521 { 1522 S^=1<<pos; 1523 S^=1<<(pos+len+1); 1524 } 1525 len+=2; 1526 } 1527 return ans; 1528 } 1529 } 1530 int solvec(int l,int r,int p) 1531 { 1532 if(!l)return p; 1533 if(a[l]==a[r]) 1534 { 1535 if(a[l])op(l,r); 1536 return solvec(l-1,r+1,p); 1537 } 1538 if(p)op(p,p+r-l); 1539 if(a[l])return solvec(l-1,r+1,l); 1540 else return solvec(l-1,r+1,r); 1541 } 1542 void solvep(int l,int r,int p,bool flag) 1543 { 1544 if(l>=r)return; 1545 if(!p) 1546 { 1547 if(a[l]==a[r]) 1548 { 1549 if(a[l])op(l,r); 1550 solvep(l+1,r-1,0,0); 1551 return; 1552 } 1553 if(a[l])solvep(l+1,r-1,l,0); 1554 else solvep(l+1,r-1,r,0); 1555 return; 1556 } 1557 if(r-l+1==DB) 1558 { 1559 int S=0; 1560 for(int i=l;i<=r;++i)S|=a[i]<<(i-l); 1561 vector<int>res=DP::ask(S); 1562 for(int len=r-l;len>=1;len-=2) 1563 { 1564 if(res[len]!=-1)op(res[len]+l,res[len]+len+l); 1565 } 1566 return; 1567 } 1568 int x=l+r-p,y=p; 1569 if(x>y)swap(x,y); 1570 int A=l-x,B=r-l+1; 1571 int len=y-x-2; 1572 auto f=[&](int a){int b=a+len;len-=2,a=a+x,b=b+x;if(p>l)a=l+r-a,b=l+r-b;op(a,b);}; 1573 if(!flag&&r-l+1>=10&&abs(A-B)==1) 1574 { 1575 for(int i=x+1;i<l;++i)del(i,l+r-i); 1576 int type=a[l]|(a[r]<<1); 1577 if(p>r)type=a[r]|(a[l]<<1); 1578 if(A==B-1) 1579 { 1580 switch(type) 1581 { 1582 case 0:for(int i=0;i<=B-4;i++)f(i);f(2*B-5);f(B-3);break; 1583 case 1:f(0);for(int i=3;i<=B-3;i+=2)f(i),f(i-1);f(B-1);f(1);break; 1584 case 2:for(int i=0;i<=B-3;i++)f(i);f(2*B-3);break; 1585 case 3:for(int i=1;i<=B-2;i++)f(i);f(0);break; 1586 } 1587 } 1588 else if(A==B) 1589 { 1590 switch(type) 1591 { 1592 case 0:for(int i=0;i<=B-2;i++)f(i);f(2*B-1);break; 1593 case 1: 1594 if(B%3==2){f(1);f(0);for(int i=3;i<=B-5;i+=3)f(i+1),f(i+2),f(i);f(B-1);f(B);f(2);} 1595 else if(B%3==0){f(1);f(0);for(int i=3;i<=B-6;i+=3)f(i+1),f(i+2),f(i);f(B-3);f(B);f(B-1);f(2);} 1596 else{f(1);f(0);for(int i=3;i<=B-7;i+=3)f(i+1),f(i+2),f(i);f(B-3);f(B-4);f(B);f(B-1);f(2);} 1597 break; 1598 case 2:f(1);f(0);for(int i=3;i<=B-3;i+=2)f(i),f(i-1);f(B-1);f(2*B-2);break; 1599 case 3:f(0);for(int i=3;i<=B-1;i+=2)f(i),f(i-1);f(1);break; 1600 } 1601 } 1602 else if(A==B+1) 1603 { 1604 switch(type) 1605 { 1606 case 0:for(int i=1;i<=B;i++)f(i);f(0);break; 1607 case 1:for(int i=1;i<B;i++)f(i);f(0);f(B);break; 1608 case 2:for(int i=1;i<=B-1;i+=2)f(i),f(i-1);f(2*B);break; 1609 case 3: 1610 if(B%3==2){f(0);f(1);for(int i=3;i<=B-2;i+=3)f(i+2),f(i),f(i+1);f(2);} 1611 else if(B%3==0){f(1);f(0);for(int i=3;i<=B-3;i+=3)f(i+1),f(i+2),f(i);f(B);f(2);} 1612 else{f(1);f(0);for(int i=4;i<=B-3;i+=3)f(i),f(i+1),f(i-1);f(B);f(B-1);f(2);} 1613 break; 1614 } 1615 } 1616 for(int i=x;i<=l;++i)if(a[i]){solvep(l+1,r-1,i,1);return;} 1617 for(int i=r;i<=y;++i)if(a[i]){solvep(l+1,r-1,i,1);return;} 1618 solvep(l+1,r-1,0,1); 1619 return; 1620 } 1621 if(a[l]&&a[r]) 1622 { 1623 op(l,r); 1624 solvep(l+1,r-1,p,flag); 1625 return; 1626 } 1627 len=r-l; 1628 auto down=[&](){ 1629 if(a[l])solvep(l+1,r-1,l,0); 1630 else if(a[r])solvep(l+1,r-1,r,0); 1631 else solvep(l+1,r-1,0,0); 1632 }; 1633 if(p+len>l&&p+len<r) 1634 { 1635 op(p,p+len); 1636 down(); 1637 return; 1638 } 1639 if(p-len>l&&p-len<r) 1640 { 1641 op(p,p-len); 1642 down(); 1643 return; 1644 } 1645 down(); 1646 } 1647 int rn; 1648 void solve() 1649 { 1650 cin>>n; 1651 rn=(n>>1); 1652 for(int i=1;i<=n;++i) 1653 { 1654 char ch; 1655 cin>>ch; 1656 a[i]=ch-'0'; 1657 } 1658 for(int i=1;i<=n;++i)ans[i]=0; 1659 if(!(n&1)) 1660 { 1661 op(n-(n>>1),n); 1662 --n; 1663 } 1664 mid=(n+1>>1); 1665 if(!(mid&1))--mid; 1666 int p=solvec((mid>>1),(mid>>1)+2,(a[(mid>>1)+1]?(mid>>1)+1:0)); 1667 solvep(mid+1,n,0,0); 1668 for(int i=1;i<=rn;++i)cout<<ans[i]<<' '; 1669 cout<<'\n'; 1670 } 1671 int main() 1672 { 1673 DP::dp(); 1674 int T; 1675 cin>>T; 1676 while(T--)solve(); 1677 return 0; 1678 } 1679 ```