We'd like to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated!↵
↵
<spoiler summary="Rate The Contest!">↵
- [likes: 1, option1] Great contest↵
- [likes: 1, option2] Good contest↵
- [likes: 1, option3] Average contest↵
- [likes: 1, option4] Bad contest↵
</spoiler>↵
↵
## [2183A — Binary Array Game](https://mirror.codeforces.com/contest/2183/problem/A)↵
↵
Idea & Preparation: [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 2, option1] Good Problem ↵
- [likes: 2, option2] Okay Problem ↵
- [likes: 2, option3] Bad Problem ↵
- [likes: 2, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
If the sequence $a$ consists entirely of $1$ s, what will Alice do?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider discussing the values of $a_1$ and $a_n$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequence.↵
↵
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$:↵
↵
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$.↵
↵
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$.↵
↵
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.↵
↵
Time complexity: $O(\sum n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
int _t_,n,a[100010];↵
void solve()↵
{↵
cin>>n;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
if(a[1]+a[n]==0)↵
cout<<"NO\n";↵
else↵
cout<<"YES\n";↵
}↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0),cout.tie(0);↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183B — Yet Another MEX Problem](https://mirror.codeforces.com/contest/2183/problem/B)↵
↵
Idea & Preparation: [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 3, option1] Good Problem ↵
- [likes: 3, option2] Okay Problem ↵
- [likes: 3, option3] Bad Problem ↵
- [likes: 3, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Considering that in the end only $k - 1$ numbers will remain, which numbers in an interval of length $k$ are invalid?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider the Pigeonhole Principle.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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)$.↵
↵
Time complexity: $O(\sum n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define re register↵
#define ll long long↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
ll _t_;↵
ll n,m;↵
ll maxn;↵
ll a[1000010];↵
ll b[1000010];↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
cin>>n>>m;↵
forl(i,1,n)↵
cin>>a[i],a[i]=min(a[i],n+1);↵
forl(i,0,n+5)↵
b[i]=0;↵
ll mex=0;↵
forl(i,1,n)↵
b[a[i]]++;↵
while(b[mex])↵
mex++;↵
cout<<min(mex,m-1)<<endl; ↵
}↵
int main()↵
{↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183C — War Strategy](https://mirror.codeforces.com/contest/2183/problem/C)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 4, option1] Good Problem ↵
- [likes: 4, option2] Okay Problem ↵
- [likes: 4, option3] Bad Problem ↵
- [likes: 4, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider a greedy algorithm.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What shape must the finally occupied bases take?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If the capital is the first city (i.e., $k=1$), how to solve it?↵
</spoiler>↵
↵
<spoiler summary="Claim 1">↵
The finally occupied bases must form an interval containing $k$.↵
</spoiler>↵
↵
<spoiler summary="Proof">↵
If the finally occupied bases do not form an interval containing $k$, then there must exist some $x, y$ such that $1 \le x < y < k$ or $k < y < 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$.↵
</spoiler>↵
↵
<spoiler summary="Claim 2">↵
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$.↵
</spoiler>↵
↵
<spoiler summary="Proof">↵
↵
Sufficiency:↵
↵
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.↵
↵
Necessity:↵
↵
We prove that for any strategy, the required number of days $m$ is at least $a + b + \max\{a, b\} - 1$.↵
↵
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.↵
↵
Assume without loss of generality that $a \ge b$.↵
↵
Define the potential function $h(S)$ of a state $S$ as the number of soldiers minus the number of occupied bases.↵
↵
Suppose the first move to the left is moving $t$ soldiers to the leftmost consecutive $t$ positions $k-a, \ldots, k-a+t-1$.↵
↵
(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.)↵
↵
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.↵
↵
We have $h(S_2) = h(S_1)$, $h(S_3) \ge h(S_2)$.↵
↵
$h(S_1) - h(S_0) \ge a - t$ (during the intermediate $a-t$ steps, the potential increases each time).↵
↵
$h(S_0) \ge t - 1$ (at least $t$ movable soldiers are needed).↵
↵
Summing up, we get $h(S_3) \ge a - 1$. Therefore, the number of days needed is at least $2a + b - 1$.↵
↵
In summary, at least $a + b + \max\{a, b\} - 1$ days are required.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We consider a greedy approach. First, if $k-1 < n-k$, we replace $k$ with $n+1-k$.↵
↵
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 < 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 < 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 capital) is the answer. The time complexity is $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
/*↵
OI 2025 RP++!!!↵
↵
author: wmrqwq[alsu]↵
↵
time: 2025/7/12↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) (x&-x)↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
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;}↵
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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
ll lg[1000010];↵
void Init(){↵
forl(i,2,1e6+5)↵
lg[i]=lg[i>>1]+1;↵
}↵
//sunny↵
ll n,m,k;↵
//tulpa↵
void _clear(){}↵
void solve()↵
{↵
ll ans=0;↵
_clear();↵
cin>>n>>m>>k;↵
forl(i,0,k-1)↵
{↵
ll lst=m-i*2+1;↵
if(lst<0)↵
continue;↵
ll S=1+i;↵
ll now=(m-i+1)/2;↵
Min(now,lst);↵
Min(now,n-k);↵
S+=now;↵
Max(ans,S);↵
}↵
cout<<ans<<endl;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
Solve the problem in $O(1)$ time per test case.↵
</spoiler>\{a, b+1\} - 1 \le m$), then set $b$ to $b+1$. Next, we try to increase $a$ by $1$ (if $a < 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)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,k,m;↵
signed main(){↵
int T;↵
cin>>T;↵
while(T--){↵
cin>>n>>m>>k;↵
if(k-1<n-k)k=n+1-k;↵
int a=0,b=0;↵
while(1){↵
if(b<n-k&&a+(b+1)+max(a,b+1)-1<=m)++b;↵
if(a<k-1&&(a+1)+b+max(a+1,b)-1<=m)++a;↵
else break;↵
}↵
cout<<a+b+1<<endl;↵
}↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
Solve the problem in $O(1)$ or $O(\log n)$ time per test case.↵
</spoiler>↵
↵
↵
## [2183D1 — Tree Coloring (Easy Version)](https://mirror.codeforces.com/contest/2183/problem/D1)↵
↵
Idea & Preparation: [user:jiazhichen844,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 5, option1] Good Problem ↵
- [likes: 5, option2] Okay Problem ↵
- [likes: 5, option3] Bad Problem ↵
- [likes: 5, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider which points cannot be colored in the same operation.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Find a lower bound for the number of operations.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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$.↵
↵
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)$.↵
↵
We claim this is the answer. Proof follows from the constructive proof in D2.↵
</spoiler>↵
↵
## [2183D2 — Tree Coloring (Hard Version)](https://mirror.codeforces.com/contest/2183/problem/D2)↵
↵
Idea & Preparation: [user:jiazhichen844,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 6, option1] Good Problem ↵
- [likes: 6, option2] Okay Problem ↵
- [likes: 6, option3] Bad Problem ↵
- [likes: 6, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
When can the minimum number of operations reach $\max t_i$? How much more than $\max t_i$ can it be at most?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We claim the maximum number of operations is $\max t_i + 1$. Consider the following constructive proof.↵
↵
Let $S_i$ denote the set of points for the $i$ th operation.↵
↵
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.↵
↵
Then we only need to consider placing points of depth $\neq x$ into $S$. First, consider points of depth $>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$.↵
↵
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).↵
↵
<center>↵
<br/>↵
<img src="https://i.ibb.co/gLZWfH1F/D.png" alt="D" border="0"/>↵
<br/>↵
</center>↵
↵
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.↵
↵
Next, we construct the point of depth $<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:↵
↵
1. $a=T$ and $c=0$: All points at depth $k+1$ share a common parent.↵
↵
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.↵
↵
2. Points at depth $k$ have at least two non-leaf neighbors.↵
↵
We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily.↵
↵
3. A node at depth $k$ has exactly one non-leaf child, and at least one set lacks any node at depth $k+1$.↵
↵
Place this father into the set lacking a node at depth $k+1$, then place the remaining nodes arbitrarily.↵
↵
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.↵
↵
Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
vector<int> e[300005],v[300005],g[300005];↵
int n,d[300005],t[300005],id[300005],son[300005],snum[300005],fa[300005];↵
bool flag[300005];↵
void dfs(int pos,int fa)↵
{↵
::fa[pos]=fa;↵
d[pos]=d[fa]+1;↵
t[d[pos]]++;↵
g[d[pos]].push_back(pos);↵
for(int x:e[pos])↵
{↵
if(x==fa)↵
continue;↵
snum[pos]++;↵
dfs(x,pos);↵
}↵
}↵
void test()↵
{↵
cin>>n;↵
for(int i=1;i<=n;i++)↵
e[i].clear(),g[i].clear(),v[i].clear(),d[i]=t[i]=id[i]=snum[i]=0;↵
for(int i=1;i<n;i++)↵
{↵
int u,v;↵
cin>>u>>v;↵
e[u].push_back(v);↵
e[v].push_back(u);↵
}↵
dfs(1,0);↵
int mx=0,mt=0;↵
for(int i=1;i<=n;i++)↵
if(t[i]>=mx)↵
mx=t[i],mt=i;↵
// for(int i=1;i<=n;i++)↵
// cerr<<i<<" "<<fa[i]<<" "<<d[i]<<"\n";↵
int ans=mx;↵
for(int i=1;i<=mx;i++)↵
id[g[mt][i-1]]=i,v[i].push_back(g[mt][i-1]);↵
for(int i=mt+1;i<=n;i++)↵
{↵
vector<int> vfa;↵
for(int j:g[i-1])↵
{↵
son[j]=0;↵
if(snum[j])↵
flag[id[j]]=1;↵
}↵
int pos=1;↵
for(int j:g[i])↵
{↵
if(!son[fa[j]])↵
son[fa[j]]=j,vfa.push_back(fa[j]);↵
else↵
{↵
while(flag[pos])↵
pos++;↵
assert(pos<=mx);↵
id[j]=pos,v[pos].push_back(j),pos++;↵
}↵
}↵
while(flag[pos])↵
pos++;↵
assert(pos<=mx);↵
int lst=pos;↵
for(int x:vfa)↵
{↵
id[son[x]]=lst;↵
v[lst].push_back(son[x]);↵
lst=id[x];↵
}↵
for(int j:g[i-1])↵
flag[id[j]]=0;↵
}↵
for(int i=mt-1;i>=1;i--)↵
{↵
vector<int> vfa;↵
for(int j:g[i])↵
son[j]=0;↵
for(int j:g[i+1])↵
{↵
flag[id[j]]=1;↵
if(!son[fa[j]])↵
son[fa[j]]=j,vfa.push_back(fa[j]);↵
}↵
assert(!vfa.empty());↵
if(vfa.size()==1)↵
{↵
if(ans==t[i+1])↵
ans++,id[vfa[0]]=ans,v[ans].push_back(vfa[0]);↵
else↵
{↵
int pos=1;↵
while(flag[pos])↵
pos++;↵
assert(pos<=ans);↵
id[vfa[0]]=pos,v[pos].push_back(vfa[0]);↵
}↵
}↵
else↵
{↵
for(int i=0;i<vfa.size();i++)↵
id[vfa[i]]=id[son[vfa[(i+1)%vfa.size()]]],v[id[vfa[i]]].push_back(vfa[i]);↵
}↵
for(int j:g[i+1])↵
flag[id[j]]=0;↵
for(int x:vfa)↵
flag[id[x]]=1;↵
int pos=1;↵
for(int x:g[i])↵
if(!son[x])↵
{↵
while(flag[pos])↵
pos++;↵
assert(pos<=ans);↵
id[x]=pos,v[pos].push_back(x);↵
pos++;↵
}↵
for(int x:vfa)↵
flag[id[x]]=0;↵
}↵
cout<<ans<<"\n";↵
for(int i=1;i<=ans;i++)↵
{↵
cout<<v[i].size()<<" ";↵
for(int x:v[i])↵
cout<<x<<" ";↵
cout<<"\n";↵
}↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
for(int i=1;i<=t;i++)↵
test();↵
}↵
```↵
</spoiler>↵
↵
## [2183E — LCM is Legendary Counting Master](https://mirror.codeforces.com/contest/2183/problem/E)↵
↵
Idea & Preparation: [user:Gold14526,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 7, option1] Good Problem ↵
- [likes: 7, option2] Okay Problem ↵
- [likes: 7, option3] Bad Problem ↵
- [likes: 7, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider the term $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$. What properties can you derive if $a_i < a_{i+1}$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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 < a_{i+1}$, the inequality $\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$ always holds.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If $y > 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 < y \le m$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Note that↵
$$↵
\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}↵
$$↵
The equality holds if and only if $\gcd(a_i,a_{i+1})=a_{i+1}-a_i$ for all $1\le i<n$, and $a_1=1$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions.↵
↵
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)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=3000,M=3000;↵
cint mod=998244353;↵
int n,m;↵
int a[N+1];↵
int dp[N+1][M+1];↵
vector<int>d[M+1];↵
int ans;↵
void solve()↵
{↵
n=read();↵
m=read();↵
for(int i=1;i<=n;++i)↵
{↵
a[i]=read();↵
}↵
if(a[1]>1)↵
{↵
princh(0,'\n');↵
return;↵
}↵
dp[1][1]=1;↵
for(int i=2;i<=n;++i)↵
{↵
for(int j=1;j<=m;++j)↵
{↵
dp[i][j]=0;↵
for(int x:d[j])↵
{↵
(dp[i][j]+=dp[i-1][j-x])>=mod?(dp[i][j]-=mod):0;↵
}↵
}↵
if(a[i])↵
{↵
for(int j=1;j<=m;++j)if(j!=a[i])dp[i][j]=0;↵
}↵
}↵
ans=0;↵
for(int j=1;j<=m;++j)↵
{↵
(ans+=dp[n][j])>=mod?(ans-=mod):0;↵
}↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
for(int i=1;i<=M;++i)↵
{↵
for(int j=i;j<=M;j+=i)↵
{↵
d[j].push_back(i);↵
}↵
}↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
## [2183F — Jumping Man](https://mirror.codeforces.com/contest/2183/problem/F)↵
↵
Idea & Preparation: [user:Neil_Qian,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 8, option1] Good Problem ↵
- [likes: 8, option2] Okay Problem ↵
- [likes: 8, option3] Bad Problem ↵
- [likes: 8, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Calculating the sum of squares of counts is difficult.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try dynamic programming. ↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
The DP transition is continuous over the DFS sequence.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. ↵
↵
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. ↵
↵
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. ↵
↵
The time complexity is $O(n^2)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
const int MAXN = 5e3 + 10;↵
const int mod = 998244353;↵
↵
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }↵
inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }↵
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }↵
↵
int T, n, ans[MAXN], sum[MAXN][MAXN]; char s[MAXN];↵
↵
vector<int> g[MAXN]; int in[MAXN], out[MAXN], rev[MAXN], id;↵
↵
void init(int u, int f = 0) {↵
in[u] = ++id, rev[id] = u;↵
for (int v : g[u]) if (v != f) init(v, u);↵
out[u] = id;↵
}↵
↵
inline ↵
int query(int al, int ar, int bl, int br) {↵
return sub(add(sum[al][bl], sum[ar + 1][br + 1]), add(sum[al][br + 1], sum[ar + 1][bl]));↵
}↵
↵
int main() {↵
for (scanf("%d", &T); T--; ) {↵
scanf("%d%s", &n, s + 1), id = 0;↵
for (int i = 1, u, v; i < n; i++) {↵
scanf("%d%d", &u, &v);↵
g[u].emplace_back(v), g[v].emplace_back(u);↵
}↵
init(1);↵
for (int i = n; i; i--) {↵
for (int j = n; j; j--) {↵
if (s[rev[i]] == s[rev[j]]) {↵
sum[i][j] = add(query(in[rev[i]] + 1, out[rev[i]], in[rev[j]] + 1, out[rev[j]]), 1);↵
}↵
cadd(sum[i][j], sub(add(sum[i + 1][j], sum[i][j + 1]), sum[i + 1][j + 1]));↵
}↵
}↵
for (int i = 1; i <= n; i++) {↵
printf("%d ", query(in[i], out[i], in[i], out[i]));↵
}↵
puts("");↵
for (int i = 1; i <= n; i++) g[i].clear();↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= n; j++) sum[i][j] = 0;↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
## [2183G — Snake Instructions](https://mirror.codeforces.com/contest/2183/problem/G)↵
↵
Idea & Preparation: [user:xvchongyv,2025-12-23] & [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 9, option1] Good Problem ↵
- [likes: 9, option2] Okay Problem ↵
- [likes: 9, option3] Bad Problem ↵
- [likes: 9, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider under what circumstances you need to return $-1$.↵
↵
<spoiler summary="Answer">↵
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.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what information you can get by querying the string `L`.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The case analysis process for this problem is not complicated.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider querying three fixed strings to determine all snakes' speeds.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Consider querying the three strings: `L`, `LR`, and `R`.↵
↵
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.↵
↵
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`.↵
↵
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):↵
↵
- `01`.↵
- `02`.↵
- `0_2`.↵
- `12`.↵
↵
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.↵
↵
First, try to determine some snakes with speed $2$. For the position and speed of such a snake, the following cases allow direct determination:↵
↵
- The previous snake is at a distance of $1$ and has been determined to have speed $1$.↵
- 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:↵
- If the previous snake's speed is $0$, it will definitely not be killed in a collision, so this case is impossible.↵
- 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$.↵
- The previous snake is at a distance of $2$ and has been determined to have speed $0$.↵
↵
The case analysis above naturally eliminates the `0_2` and `12` scenarios.↵
↵
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.↵
↵
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.↵
↵
Time complexity: $O(\sum n)$ or $O(\sum n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
/*↵
OI 2025 RP++!!!↵
↵
author: wmrqwq[alsu]↵
↵
time: 2025/7/12↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) (x&-x)↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
// #define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
// 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;}↵
// 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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
// ll lg[1000010];↵
void Init(){↵
// forl(i,2,1e6+5)↵
// lg[i]=lg[i>>1]+1;↵
}↵
//sunny↵
ll n;↵
ll a[100010];↵
ll ans[100010];↵
vector<ll>vl,vr,vlr;↵
//tulpa↵
void ask(string s,vector<ll>&v)↵
{↵
cout<<"? "<<s<<endl;↵
v.pb(rd());↵
forl(i,1,v[0])↵
v.pb(rd());↵
}↵
/*↵
012↵
↵
01↵
02↵
↵
120↵
*/↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
vl.clear(),vr.clear(),vlr.clear();↵
cin>>n;↵
forl(i,1,n)↵
cin>>a[i],↵
ans[i]=-1;↵
ask("L",vl),ask("R",vr),ask("LR",vlr);↵
ll sz=vlr[0],L=1;↵
forl(i,1,n)↵
{↵
while(L<=sz && vlr[L]<a[i])↵
L++;↵
if(L<=sz && vlr[L]==a[i])↵
ans[i]=vlr[L]-vl[L];↵
}↵
forl(i,2,n)↵
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)))↵
{↵
// if(ans[i-1]==-1)↵
// ans[i-1]=1;↵
ans[i]=2;↵
}↵
forl(i,1,n)↵
if(ans[i]==-1)↵
ans[i]=*lower_bound(vr.begin()+2,vr.end(),a[i])-a[i];↵
forl(i,1,n-2)↵
if(a[i]+1==a[i+1] && a[i+1]+1==a[i+2] && ans[i]+ans[i+2]==0 && ans[i+1])↵
{↵
cout<<"! "<<-1<<endl;↵
return ;↵
}↵
cout<<"! ";↵
forl(i,1,n)↵
cout<<ans[i]<<' ';↵
cout<<endl;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
```↵
</spoiler>↵
↵
## [2183H — Minimise Cost](https://mirror.codeforces.com/contest/2183/problem/H)↵
↵
Idea & Preparation: [user:Hoks_,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 10, option1] Good Problem ↵
- [likes: 10, option2] Okay Problem ↵
- [likes: 10, option3] Bad Problem ↵
- [likes: 10, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Subsequences are too hard; can we find some properties? How should we approach the case where $n=k=500$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The approach for $n=k=500$ is too naive; how can we optimize it? What if $n=k=5000$?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What if we are guaranteed that the count of positive numbers $m \le 5000$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
The requirement of **exactly** $k$ segments, combined with the previous optimizations, suggests what technique? Consider the data constraints.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We can observe the following two conclusions:↵
↵
1. After sorting all elements, the subsequence we partition must correspond to a **substring** (contiguous segment) of the new sequence.↵
2. If the lengths of the partitioned segments are $l_1, l_2, \dots, l_k$, then it must hold that $l_i \ge l_{i+1}$ for $i \in [1, k)$.↵
↵
<spoiler summary="Proof of Length Monotonicity">↵
Define the range of a sequence $b$ as $[\min b_i, \max b_i]$.Take two subsequences $s_i, s_j$ such that their value ranges intersect. Let their lengths be $l_i, l_j$.Without loss of generality, assume $l_i > l_j$.Consider the set of all elements in $s_i$ and $s_j$. If we take the smallest $l_i$ elements to form a new $s_i$ and the remaining to form $s_j$, the cost decreases.↵
↵
Why? Consider an element $a_x$. It is multiplied by either $l_i$ or $l_j$. We only care about elements that switch coefficients. With the split point at the $l_i$-th number, the number of elements switching from coefficient $l_j$ to $l_i$ equals the number of elements switching from $l_i$ to $l_j$. Since the array is sorted, the former elements are strictly smaller than the latter. Given $l_i > l_j$, switching the larger coefficient to smaller numbers reduces the total sum.By repeatedly adjusting, we arrive at the conclusion.↵
</spoiler>↵
↵
Based on this, we can design a brute-force DP. Let $f_{i,j}$ be the minimum weight sum for partitioning the first $i$ numbers into exactly $j$ segments.$$f_{i,j}=\min\limits_{k=1}^{i-1} (f_{k,j-1}+(s_i-s_k)\cdot(i-k))$$ This runs in $O(n^2k)$ .↵
↵
We can optimize this DP. Let $w(l,r) = (r-l+1)\cdot(s_r-s_{l-1})$. If all numbers are non-negative, the cost function satisfies the Quadrangle Inequality (QI). Using Knuth Optimization, we can reduce the complexity to $O(nk)$.↵
↵
Now consider the case with negative numbers.We observe:↵
↵
1. For positive numbers, more segments are better (smaller coefficients).↵
2. For negative numbers, fewer segments are better (larger coefficients).↵
↵
Since $l_1$ is the largest coefficient, we prioritize assigning the negative numbers to the first segment. Let $m$ be the count of non-negative numbers.If $k \le m$, the optimal strategy is to assign a prefix (containing all negative numbers and some positive numbers) to the first segment, and partition the remaining suffix of positive numbers into $k-1$ segments.↵
↵
<spoiler summary="Proof: The segment containing negative numbers is exactly one">↵
We prove that splitting negative numbers into 2 segments is not optimal.Consider a configuration: $a_1, \dots, a_x$ (negative), $a_{x+1}, \dots, a_n$ (positive).Suppose we have a partition $[a_1, a_l]$ and $[a_{l+1}, a_r]$ where $l < x < r$. We can shift the split to $[a_1, a_x]$ and $[a_{x+1}, a_r]$.Let $l_1=l, l_2=x-l, l_3=r-x$. Let $S_1, S_2, S_3$ be the sum of absolute values in the respective ranges.The change in cost is a reduction of $S_1 l_2 + S_3 l_2 - S_2(l_1 - l_3)$.Since $S_3 l_2 + S_2 l_3 \ge 0$, we only need $S_1 l_2 \ge S_2 l_1$, or $S_1/l_1 \ge S_2/l_2$.This means the average absolute value of the earlier segment is larger. Since the array is sorted (and values are negative), the absolute values are indeed decreasing, so this holds.↵
</spoiler>↵
↵
If $k > m$, we assign each positive number to its own segment, and partition the negative numbers into the remaining segments.↵
↵
Finally, consider $n, k \le 2 \times 10^5$.The constraints and the "exactly $k$ segments" requirement suggest **Alien's Trick**. The cost function $w(l,r)$ for positive numbers satisfies QI, implying convexity.We binary search a penalty $\lambda$. The transitions become $dp[i] = \min (dp[j] + w(j+1, i) + \lambda)$.To handle negative numbers efficiently, we use the property that negative numbers (indices $x \le n-m$) cannot be optimal transition points (except for the base case $0$). By excluding these indices from the decision set, the cost function satisfies the Quadrangle Inequality for all valid transitions.↵
↵
<spoiler summary="Proof of QI with Restricted Transitions">↵
The Quadrangle Inequality condition simplifies to:$$(d-c)\cdot(s_b-s_a)+(b-a)\cdot(s_d-s_c)\ge0$$ If all $a_i \ge 0$ , $s$ is non-decreasing, and it holds.If we exclude negative indices, the only special case is transition from $0$ (where $s_a=0$). In this case, $(d-c)s_b + b(s_d-s_c) \ge 0$ holds because $s$ is increasing for the suffix and lengths are positive.Thus, the restricted DP has decision monotonicity.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define S cerr << "SYT AK IOI" << endl;↵
#define M cerr << "MKF AK IOI" << endl;↵
↵
using ll = long long;↵
using pii = pair<int, int>;↵
using uint = unsigned int;↵
using ull = unsigned long long;↵
mt19937 rnd(0 ^ (*new int));↵
// #define int long long //use it if possible↵
#define pb(x) push_back(x)↵
#define F(i, a, b) for (int i = (a), i##end = (b); i <= (i##end); ++i)↵
#define UF(i, a, b) for (int i = (a), i##end = (b); i >= (i##end); --i)↵
#define gc() getchar()↵
#define pc putchar↵
#define popcount(x) __builtin_popcount(x)↵
↵
inline void init();↵
inline void IO();↵
__int128 n,k,p;↵
__int128 a[1000100],lim[1000100],q[1000100];↵
array<__int128,2>dp[1000100];↵
ll rd()↵
{↵
ll x;↵
cin>>x;↵
return x;↵
}↵
inline array<__int128,2> calc(__int128 i,__int128 j,__int128 x){↵
return (array<__int128,2>){dp[j][0]+(i-j)*(a[i]-a[j])-x,dp[j][1]+1};↵
}↵
inline bool c2(__int128 x,__int128 i,__int128 j,__int128 m){↵
return calc(x,j,m)>=calc(x,i,m);↵
}↵
inline __int128 find(__int128 i,__int128 j,__int128 m){↵
int l=i,r=n,mid,res=n+1;↵
while(l<=r) c2(mid=l+r>>1,i,j,m)?res=mid,r=mid-1:l=mid+1;↵
return res;↵
}↵
inline __int128 ck(__int128 mid){↵
for(__int128 i=p,l=1,r=1;i<=n;i++){↵
for(;l<r&&lim[l]<=i;l++);dp[i]=calc(i,q[l],mid);↵
for(;l<r&&lim[r-1]>=find(i,q[r],mid);r--);↵
lim[r]=find(i,q[r],mid);q[++r]=i;↵
}↵
return dp[n][1]<=k;↵
}↵
void print(__int128 x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}↵
inline void mian()↵
{↵
// cin>>n>>k;↵
n=rd(),k=rd();↵
F(i,1,n)a[i]=rd();↵
sort(a+1,a+1+n);↵
F(i,2,n)a[i]+=a[i-1];↵
if(k==1){print(n*a[n]);putchar('\n');return;}↵
__int128 ans=(n-k+1)*a[n-k+1]+a[n]-a[n-k+1];p=1;↵
while(p<=n and a[p]-a[p-1]<=0)p++;↵
while(p<=n and p*a[p]-a[p]+a[p-1]<(p-1)*a[p-1])p++;↵
--p,p=max(p,(__int128)1);↵
if(n-p<k-1){print(ans);putchar('\n');return;}↵
__int128 l=-n*n*(__int128)(1e9),r=-l,mid,res=l;↵
while(l<=r) ck(mid=l+r>>1)?res=mid,l=mid+1:r=mid-1;↵
ck(res);↵
ans=min(ans,(__int128)k*res+dp[n][0]);↵
print(ans);putchar('\n');↵
}↵
signed main()↵
{↵
IO();↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T = 1;↵
#define multitest 1↵
#ifdef multitest↵
T=rd();↵
#endif↵
init();↵
↵
while (T--)↵
mian();↵
return 0;↵
}↵
↵
inline void init()↵
{↵
}↵
↵
#define NAME(x) #x↵
#define INNAME(x) NAME(x)↵
// #define FILEIO sub3_15↵
inline void IO()↵
{↵
#ifdef FILEIO↵
freopen(INNAME(FILEIO) ".in", "r", stdin), freopen(INNAME(FILEIO) ".out", "w", stdout);↵
#endif↵
}↵
↵
```↵
</spoiler>↵
↵
## [2183I1 — Pairs Flipping (Easy Version)](https://mirror.codeforces.com/contest/2183/problem/I1)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23] Special Thanks: [user:N_z_,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 11, option1] Good Problem ↵
- [likes: 11, option2] Okay Problem ↵
- [likes: 11, option3] Bad Problem ↵
- [likes: 11, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Try dividing the sequence into two equal halves.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let us assume $n$ is an odd number. We shall attempt to divide it into the first $\frac{n-1}2$ elements and the subsequent $\frac{n+1}2$ elements, eliminating both halves by assigning odd and even lengths respectively.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try processing recursively to reduce $n$ to a smaller scale.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Try further optimizing one of the two halves.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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$.↵
↵
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.)↵
↵
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<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.↵
↵
Proof that the above situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times：↵
↵
- 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 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.↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
template<typename T1, typename T2>↵
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {↵
os << "(" << p.first << ", " << p.second << ")";↵
return os;↵
}↵
// your original is_iterable (unchanged)↵
template <typename T, typename = void>↵
struct is_iterable : std::false_type {};↵
↵
template <typename T>↵
struct is_iterable<T, std::void_t<↵
decltype(std::begin(std::declval<T>())),↵
decltype(std::end(std::declval<T>()))↵
>> : std::true_type {};↵
↵
// detect std::basic_string<...>↵
template <typename T>↵
struct is_string : std::false_type {};↵
↵
template <typename CharT, typename Traits, typename Alloc>↵
struct is_string<std::basic_string<CharT, Traits, Alloc>> : std::true_type {};↵
↵
// optionally also detect string_view (C++17)↵
template <typename CharT, typename Traits>↵
struct is_string<std::basic_string_view<CharT, Traits>> : std::true_type {};↵
↵
// now enable the generic container printer only when T is iterable AND not a string↵
template <typename T>↵
typename std::enable_if<↵
is_iterable<T>::value && !is_string<T>::value,↵
std::ostream&↵
>::type↵
operator<<(std::ostream& os, const T& container) {↵
os << "{ ";↵
for (auto it = std::begin(container); it != std::end(container); ++it) {↵
os << *it;↵
if (std::next(it) != std::end(container)) os << ", ";↵
}↵
os << " }";↵
return os;↵
}↵
↵
// Queue-like adapters (stack, queue, priority_queue)↵
template <typename T>↵
ostream& operator<<(ostream& os, queue<T> q) {↵
os << "{ ";↵
while (!q.empty()) { os << q.front(); q.pop(); if (!q.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
template <typename T>↵
ostream& operator<<(ostream& os, stack<T> st) {↵
os << "{ ";↵
while (!st.empty()) { os << st.top(); st.pop(); if (!st.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
template <typename T>↵
ostream& operator<<(ostream& os, priority_queue<T> pq) {↵
os << "{ ";↵
while (!pq.empty()) { os << pq.top(); pq.pop(); if (!pq.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
// using namespace std;↵
using ll = long long;↵
#define add push_back ↵
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)↵
#define F0R(i,a) FOR(i,0,a)↵
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)↵
#define R0F(i,a) ROF(i,0,a)↵
#define f first↵
#define s second↵
#define trav(a,x) for (auto& a: x)↵
#define int long long↵
#define vt vector↵
#define endl "\n"↵
#define enld "\n"↵
#define double long double↵
const ll mod = 998244353;↵
const ll inf = 1e18;↵
template<typename T> using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; //defines min_pq↵
↵
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());↵
int rand_num(int l, int r) {↵
return rnd()%(r-l+1)+l;↵
}↵
signed main() {↵
ios_base::sync_with_stdio(false); ↵
cin.tie(0);↵
// freopen("input.txt" , "r" , stdin);↵
// freopen("output.txt" , "w", stdoutsigned main() {↵
ios_base::sync_with_stdio(false); ↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--) {↵
int n;↵
cin >> n;↵
string a;↵
cin >> a;↵
// int n = a.size();↵
vtvector<int> ops(n/2+5);↵
auto operate = [&](int i)->void{↵
if(ops[i]==0) return;↵
else {↵
if(a[ops[i]-1]=='1') a[ops[i]-1]='0'; else a[ops[i]-1]='1';↵
if(a[ops[i]-1+i]=='1') a[ops[i]-1+i]='0'; else^=1;↵
a[ops[i]-1+i]='1'^=1;↵
}↵
↵
}; ↵
autofsolveCompletely = [&](auto self, int l, int r, int x)->void{↵
if(l>r) return;↵
if(a[l]==a[r]) {↵
if(a[l]=='1') ops[r-l]=l+1, operate(r-l);↵
self(self, l+1, r-1, x);↵
return;↵
}↵
if(x!=-1 && x<l) {↵
if(x+r-l>=l) {↵
ops[r-l]=x+1, operate(r-l);↵
}↵
} else if(x!=-1 && x>r) {↵
if(x-r+l<=r) {↵
ops[r-l]=x-r+l+1, operate(r-l);↵
}↵
}↵
if(a[l]=='1') {↵
self(self, l+1, r-1, l);↵
} else {↵
self(self, l+1, r-1, r);↵
}↵
};↵
autogsolvePartially = [&](auto self, int l, int r)->int{↵
if(l>r) return -1;↵
if(l==r) if(a[l]=='1') return l; else return -1;↵
int x = self(self, l+1, r-1);↵
// cout << l << " " << r << " " << x << endl;↵
if(a[l]==a[r]) {↵
if(a[l]=='1') ops[r-l]=l+1, operate(r-l);↵
return x;↵
} else {↵
if(x!=-1) {↵
ops[r-l]=x+1, operate(r-l);↵
}↵
if(a[l]=='1') return l;↵
else return r;↵
}↵
};↵
/*↵
5↵
1-2 3-5↵
7↵
1-3 4-7↵
*/↵
g(gsolvePartially(solvePartially, 0, (n-1)/2-1);↵
if(n%2)f(fsolveCompletely(solveCompletely, (n-1)/2, n-1, -1);↵
elsef(f, (n-1)/2, n-2, -1);↵
// cout << ops << endl;↵
FOR(i, 1, n/2+1) cout << ops[i] << " ";↵
cout << endl;↵
// cout << a << endl;↵
↵
}↵
return 0;↵
}↵
/*↵
1100111 01010100↵
1100111 ↵
0: ?↵
2: ?↵
↵
01010100↵
7 14↵
8 13↵
↵
1111111011↵
1111 11101↵
1 4↵
2 3↵
5 9↵
6 8↵
*/solveCompletely(solveCompletely, (n-1)/2, n-2, -1);↵
for(int i=1; i<=n/2; i++) cout << ops[i] << " ";↵
cout << endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183I2 — Pairs Flipping (Hard Version)](https://mirror.codeforces.com/contest/2183/problem/I2)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 12, option1] Good Problem ↵
- [likes: 12, option2] Okay Problem ↵
- [likes: 12, option3] Bad Problem ↵
- [likes: 12, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
In the approach of I1, we can see that the main cost comes from the fact that isolated $1$'s outside the interval sometimes cannot be eliminated. We consider optimizing this situation.↵
↵
The following diagram illustrates a scenario where one such elimination fails.↵
↵
```↵
1111111111111|1??????0|1111111111110↵
p l r q↵
```↵
↵
Here, $p$ is the previous $1$ we could not eliminate (assume without loss of generality that $p<l$), $[l, r]$ is the current interval being processed, and $l-p \ge r-l$ (making it impossible to eliminate directly using the previous method). $q$ is the symmetric point of $p$.↵
↵
The operation lengths we can use at this point are $q-p-3, q-p-5, q-p-7, \ldots, r-l$. Note that $q-p-1$ is excluded because we have already used it earlier.↵
↵
Let the lengths of the three segments be $A$, $B$, and $C$, where $A = C$. This scenario is denoted as $F(A, B)$.↵
↵
Next, we will study in detail how to perform elimination for $F(A, B)$.↵
↵
If $A < B-1$, we have essentially solved it in I1.↵
↵
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.↵
↵
For other cases, we can demonstrate that it is always possible to find a method to eliminate until only one $1$ remains. 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.↵
↵
Thus, between every two adjacent $1$'s that cannot be eliminated, we can always save one elimination, leaving a $1$ near $l$ or $r$. Let the interval length be $s$. Whenever a $1$ cannot be eliminated, $s$ becomes at least $\frac19 s + \frac{2}{3}$. The number of remaining $1$'s is approximately $\log_9\frac{n}{2}$. When the interval length does not exceed 18, we can use an $O(n^2 2^n)$ dynamic programming approach to find the optimal solution. The optimal solution can always leave no more than $1$ remaining $1$. It can be proven that when $n \le 2 \times 10^6$, the total number of $1$'s does not exceed $7$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
bool Mbg;↵
using namespace std;↵
#define vec vector↵
#define pb push_back↵
#define eb emplace_back↵
#define siz(vec) (int)((vec).size())↵
#define all(vec) (vec).begin(),(vec).end()↵
template<class T>↵
void operator +=(vec<T> &lhs,const T &rhs){lhs.push_back(rhs);}↵
#define pii pair<int,int>↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define exc(expr) if(expr)continue;↵
#define stop(expr) if(expr)break;↵
#define ret(expr) if(expr)return;↵
#define deb(var) cout<<#var<<'='<<(var)<<"; "↵
#define debl(var) cout<<#var<<'='<<(var)<<";\n"↵
#define ins insert↵
#define era erase↵
#define lb lower_bound↵
#define ub upper_bound↵
#define int long long↵
#define inf (long long)(1.1e18)↵
template<class T>↵
bool Min(T &x,const T &y){return x>y?x=y,1:0;}↵
template<class T>↵
bool Max(T &x,const T &y){return x<y?x=y,1:0;}↵
const int mod=998244353;↵
void Add(int &x,const int &y){x=x+y<mod?x+y:x+y-mod;}↵
void Dec(int &x,const int &y){x=x>=y?x-y:x-y+mod;}↵
int fpm(int x,int y){↵
int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)ans=1ll*x*ans%mod;return ans;↵
}↵
mt19937 eng(time(0));↵
↵
int n;↵
char s[2000010],S[2000010];↵
bool used[2000010];↵
int ans[2000010];↵
void Oper(int x,int y){↵
if(x>y)swap(x,y);↵
assert(1<=x&&x<y&&y<=n);↵
assert(!used[y-x]);↵
used[y-x]=1;↵
ans[y-x]=x;↵
s[x]^=1,s[y]^=1;↵
}↵
bool Delete(int x,int y){↵
assert(1<=x&&x<y&&y<=n);↵
if(!used[y-x])return 1;↵
if(ans[y-x]!=x)return 0;↵
used[y-x]=0;↵
ans[y-x]=0;↵
s[x]^=1,s[y]^=1;↵
return 1;↵
}↵
void solve(int l,int r,int p,bool fl){↵
if(l>r)return;↵
assert(~(r-l+1)&1);↵
if(!p){↵
if(s[l]=='1'&&s[r]=='1')Oper(l,r);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
// 鍋囧畾p!=0↵
↵
// 1. 妫€鏌ヤ笁鍊嶉暱搴?↵
↵
int x=l+r-p,y=p;↵
if(x>y)swap(x,y);↵
int A=l-x,B=r-l+1,C=y-r;↵
assert(A==C);↵
↵
int len=A+B+C-3;↵
auto Init=[&](){↵
for(int i=x+1;i<l;i++)assert(Delete(i,l+r-i));↵
};↵
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;↵
Oper(a,b);↵
};↵
↵
auto get1=[&](){↵
int tot=0,pos=0;↵
for(int i=x;i<=l;i++){↵
if(s[i]=='1'){↵
++tot,pos=i;↵
}↵
}↵
for(int i=r;i<=y;i++){↵
if(s[i]=='1'){↵
++tot,pos=i;↵
}↵
}↵
assert(tot<=1);↵
return pos;↵
};↵
if(!fl&&r-l+1>=10){ // 杩涘叆鍒嗘敮↵
int mask=(s[l]-'0')|((s[r]-'0')<<1);↵
if(p>r)mask=(s[r]-'0')|((s[l]-'0')<<1);↵
if(A==B-1){↵
Init();↵
if(mask==0){↵
for(int i=0;i<=B-4;i++)f(i);↵
f(2*B-5);↵
f(B-3);↵
}else if(mask==1){↵
f(0);↵
for(int i=3;i<=B-3;i+=2)f(i),f(i-1);↵
f(B-1);↵
f(1);↵
}else if(mask==2){↵
for(int i=0;i<=B-3;i++)f(i);↵
f(2*B-3);↵
}else if(mask==3){↵
for(int i=1;i<=B-2;i++)f(i);↵
f(0);↵
}↵
return solve(l+1,r-1,get1(),1);↵
}↵
else if(A==B){↵
// B B B↵
Init();↵
if(mask==0){↵
for(int i=0;i<=B-2;i++)f(i);↵
f(2*B-1);↵
}else if(mask==1){↵
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);↵
}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);↵
}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);↵
}↵
}else if(mask==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);↵
}else if(mask==3){↵
f(0);↵
for(int i=3;i<=B-1;i+=2)f(i),f(i-1);↵
f(1);↵
}↵
return solve(l+1,r-1,get1(),1);↵
}else if(A==B+1){↵
Init();↵
if(mask==0){↵
for(int i=1;i<=B;i++)f(i);↵
f(0);↵
}else if(mask==1){↵
for(int i=1;i<B;i++)f(i);↵
f(0);↵
f(B);↵
}else if(mask==2){↵
for(int i=1;i<=B-1;i+=2){↵
f(i),f(i-1);↵
}↵
f(2*B);↵
}else if(mask==3){↵
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);↵
}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);↵
}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);↵
}↵
}↵
return solve(l+1,r-1,get1(),1);↵
}↵
}↵
↵
if(s[l]=='1'&&s[r]=='1'){↵
Oper(l,r);↵
return solve(l+1,r-1,p,fl);↵
}else if(s[l]!=s[r]||s[l]=='0'&&s[r]=='0'){↵
int len=r-l;↵
if(p+len>l&&p+len<r){↵
Oper(p,p+len);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
if(p-len>l&&p-len<r){↵
Oper(p,p-len);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
}↵
vec<int> construct(int n){↵
int N=n;↵
fill(used+1,used+n+1,0);↵
fill(ans+1,ans+n+1,0);↵
for(int i=1;i<=n;i++)s[i]=S[i];↵
if(~n&1){↵
Oper(n-n/2,n);↵
--n;↵
}↵
int m=(n+1)/2;↵
if(~m&1)--m;↵
{↵
int r=0;↵
if(s[(m+1)/2]=='1')r=(m+1)/2;↵
for(int i=m/2;i;i--){↵
int j=m+1-i;↵
int mask=(s[i]-'0')<<1|(s[j]-'0');↵
if(mask==3){↵
Oper(i,j);↵
}else if(mask==1){↵
if(r)Oper(r,r+j-i);↵
r=j;↵
}else if(mask==2){↵
if(r)Oper(r,r+j-i);↵
r=i;↵
}↵
}↵
}↵
assert((n-m-1)&1);↵
// debl(m);↵
// debl(n); ↵
solve(m+1,n,0,0);↵
return vec<int>(ans+1,ans+N/2+1);↵
}↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;i++)cin>>S[i];↵
↵
auto A=construct(n);↵
int c1=count(s+1,s+n+1,'1');↵
↵
reverse(S+1,S+n+1);↵
auto B=construct(n);↵
int c2=count(s+1,s+n+1,'1');↵
↵
if(c1>c2){↵
A=B;↵
for(int i=0;i<n/2;i++){↵
if(A[i])A[i]=n+1-(A[i]+i+1);↵
}↵
}↵
#ifdef ONLINE_JUDGE↵
for(auto x:A)cout<<x<<' ';↵
cout<<'\n';↵
#endif↵
}↵
bool Med;↵
signed main(){↵
// freopen("d.out","r",stdin); ↵
ios::sync_with_stdio(0),↵
cin.tie(0),cout.tie(0);↵
int T=1;cin>>T;while(T--)work();↵
#ifndef ONLINE_JUDGE↵
cout<<"ok\n";↵
#endif↵
// cerr<<"Time: "<<clock()<<" ms;\n";↵
// cerr<<"Memory: "<<abs(&Med-&Mbg)/1024.0/1024.0<<" MiB.\n";↵
}↵
/*↵
- CONTINUE, NON-STOPPING, FOR THE FAITH↵
- START TYPING IF YOU DON'T KNOW WHAT TO DO↵
- STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING↵
*/ ↵
```↵
</spoiler>↵
↵
↵
<spoiler summary="Rate The Contest!">↵
- [likes: 1, option1] Great contest↵
- [likes: 1, option2] Good contest↵
- [likes: 1, option3] Average contest↵
- [likes: 1, option4] Bad contest↵
</spoiler>↵
↵
## [2183A — Binary Array Game](https://mirror.codeforces.com/contest/2183/problem/A)↵
↵
Idea & Preparation: [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 2, option1] Good Problem ↵
- [likes: 2, option2] Okay Problem ↵
- [likes: 2, option3] Bad Problem ↵
- [likes: 2, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
If the sequence $a$ consists entirely of $1$ s, what will Alice do?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider discussing the values of $a_1$ and $a_n$.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
First, if the entire sequence consists of $1$ s, Alice wins immediately by operating on the whole sequence.↵
↵
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$:↵
↵
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$.↵
↵
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$.↵
↵
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.↵
↵
Time complexity: $O(\sum n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
int _t_,n,a[100010];↵
void solve()↵
{↵
cin>>n;↵
for(int i=1;i<=n;i++)↵
cin>>a[i];↵
if(a[1]+a[n]==0)↵
cout<<"NO\n";↵
else↵
cout<<"YES\n";↵
}↵
int main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0),cout.tie(0);↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183B — Yet Another MEX Problem](https://mirror.codeforces.com/contest/2183/problem/B)↵
↵
Idea & Preparation: [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 3, option1] Good Problem ↵
- [likes: 3, option2] Okay Problem ↵
- [likes: 3, option3] Bad Problem ↵
- [likes: 3, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Considering that in the end only $k - 1$ numbers will remain, which numbers in an interval of length $k$ are invalid?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider the Pigeonhole Principle.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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)$.↵
↵
Time complexity: $O(\sum n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
#define re register↵
#define ll long long↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
ll _t_;↵
ll n,m;↵
ll maxn;↵
ll a[1000010];↵
ll b[1000010];↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
cin>>n>>m;↵
forl(i,1,n)↵
cin>>a[i],a[i]=min(a[i],n+1);↵
forl(i,0,n+5)↵
b[i]=0;↵
ll mex=0;↵
forl(i,1,n)↵
b[a[i]]++;↵
while(b[mex])↵
mex++;↵
cout<<min(mex,m-1)<<endl; ↵
}↵
int main()↵
{↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183C — War Strategy](https://mirror.codeforces.com/contest/2183/problem/C)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 4, option1] Good Problem ↵
- [likes: 4, option2] Okay Problem ↵
- [likes: 4, option3] Bad Problem ↵
- [likes: 4, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider a greedy algorithm.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
What shape must the finally occupied bases take?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
If the capital is the first city (i.e., $k=1$), how to solve it?↵
</spoiler>↵
↵
<spoiler summary="Claim 1">↵
The finally occupied bases must form an interval containing $k$.↵
</spoiler>↵
↵
<spoiler summary="Proof">↵
If the finally occupied bases do not form an interval containing $k$, then there must exist some $x, y$ such that $1 \le x < y < k$ or $k < y < 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$.↵
</spoiler>↵
↵
<spoiler summary="Claim 2">↵
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$.↵
</spoiler>↵
↵
<spoiler summary="Proof">↵
↵
Sufficiency:↵
↵
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.↵
↵
Necessity:↵
↵
We prove that for any strategy, the required number of days $m$ is at least $a + b + \max\{a, b\} - 1$.↵
↵
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.↵
↵
Assume without loss of generality that $a \ge b$.↵
↵
Define the potential function $h(S)$ of a state $S$ as the number of soldiers minus the number of occupied bases.↵
↵
Suppose the first move to the left is moving $t$ soldiers to the leftmost consecutive $t$ positions $k-a, \ldots, k-a+t-1$.↵
↵
(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.)↵
↵
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.↵
↵
We have $h(S_2) = h(S_1)$, $h(S_3) \ge h(S_2)$.↵
↵
$h(S_1) - h(S_0) \ge a - t$ (during the intermediate $a-t$ steps, the potential increases each time).↵
↵
$h(S_0) \ge t - 1$ (at least $t$ movable soldiers are needed).↵
↵
Summing up, we get $h(S_3) \ge a - 1$. Therefore, the number of days needed is at least $2a + b - 1$.↵
↵
In summary, at least $a + b + \max\{a, b\} - 1$ days are required.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We consider a greedy approach. First, if $k-1 < n-k$, we replace $k$ with $n+1-k$.↵
↵
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 < n-k$ and $a + (b+1) + \max
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
/*↵
OI 2025 RP++!!!↵
↵
author: wmrqwq[alsu]↵
↵
time: 2025/7/12↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) (x&-x)↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
#define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
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;}↵
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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
ll lg[1000010];↵
void Init(){↵
forl(i,2,1e6+5)↵
lg[i]=lg[i>>1]+1;↵
}↵
//sunny↵
ll n,m,k;↵
//tulpa↵
void _clear(){}↵
void solve()↵
{↵
ll ans=0;↵
_clear();↵
cin>>n>>m>>k;↵
forl(i,0,k-1)↵
{↵
ll lst=m-i*2+1;↵
if(lst<0)↵
continue;↵
ll S=1+i;↵
ll now=(m-i+1)/2;↵
Min(now,lst);↵
Min(now,n-k);↵
S+=now;↵
Max(ans,S);↵
}↵
cout<<ans<<endl;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
Solve the problem in $O(1)$ time per test case.↵
</spoiler>
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
using namespace std;↵
int n,k,m;↵
signed main(){↵
int T;↵
cin>>T;↵
while(T--){↵
cin>>n>>m>>k;↵
if(k-1<n-k)k=n+1-k;↵
int a=0,b=0;↵
while(1){↵
if(b<n-k&&a+(b+1)+max(a,b+1)-1<=m)++b;↵
if(a<k-1&&(a+1)+b+max(a+1,b)-1<=m)++a;↵
else break;↵
}↵
cout<<a+b+1<<endl;↵
}↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
Solve the problem in $O(1)$ or $O(\log n)$ time per test case.↵
</spoiler>↵
↵
↵
## [2183D1 — Tree Coloring (Easy Version)](https://mirror.codeforces.com/contest/2183/problem/D1)↵
↵
Idea & Preparation: [user:jiazhichen844,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 5, option1] Good Problem ↵
- [likes: 5, option2] Okay Problem ↵
- [likes: 5, option3] Bad Problem ↵
- [likes: 5, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider which points cannot be colored in the same operation.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Find a lower bound for the number of operations.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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$.↵
↵
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)$.↵
↵
We claim this is the answer. Proof follows from the constructive proof in D2.↵
</spoiler>↵
↵
## [2183D2 — Tree Coloring (Hard Version)](https://mirror.codeforces.com/contest/2183/problem/D2)↵
↵
Idea & Preparation: [user:jiazhichen844,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 6, option1] Good Problem ↵
- [likes: 6, option2] Okay Problem ↵
- [likes: 6, option3] Bad Problem ↵
- [likes: 6, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
When can the minimum number of operations reach $\max t_i$? How much more than $\max t_i$ can it be at most?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We claim the maximum number of operations is $\max t_i + 1$. Consider the following constructive proof.↵
↵
Let $S_i$ denote the set of points for the $i$ th operation.↵
↵
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.↵
↵
Then we only need to consider placing points of depth $\neq x$ into $S$. First, consider points of depth $>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$.↵
↵
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).↵
↵
<center>↵
<br/>↵
<img src="https://i.ibb.co/gLZWfH1F/D.png" alt="D" border="0"/>↵
<br/>↵
</center>↵
↵
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.↵
↵
Next, we construct the point of depth $<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:↵
↵
1. $a=T$ and $c=0$: All points at depth $k+1$ share a common parent.↵
↵
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.↵
↵
2. Points at depth $k$ have at least two non-leaf neighbors.↵
↵
We can rotate these fathers into their children's sets, placing the remaining unrestricted nodes arbitrarily.↵
↵
3. A node at depth $k$ has exactly one non-leaf child, and at least one set lacks any node at depth $k+1$.↵
↵
Place this father into the set lacking a node at depth $k+1$, then place the remaining nodes arbitrarily.↵
↵
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.↵
↵
Some bottom-up, directly greedy approaches are also valid, but their complexity is generally $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
#define int long long↵
using namespace std;↵
vector<int> e[300005],v[300005],g[300005];↵
int n,d[300005],t[300005],id[300005],son[300005],snum[300005],fa[300005];↵
bool flag[300005];↵
void dfs(int pos,int fa)↵
{↵
::fa[pos]=fa;↵
d[pos]=d[fa]+1;↵
t[d[pos]]++;↵
g[d[pos]].push_back(pos);↵
for(int x:e[pos])↵
{↵
if(x==fa)↵
continue;↵
snum[pos]++;↵
dfs(x,pos);↵
}↵
}↵
void test()↵
{↵
cin>>n;↵
for(int i=1;i<=n;i++)↵
e[i].clear(),g[i].clear(),v[i].clear(),d[i]=t[i]=id[i]=snum[i]=0;↵
for(int i=1;i<n;i++)↵
{↵
int u,v;↵
cin>>u>>v;↵
e[u].push_back(v);↵
e[v].push_back(u);↵
}↵
dfs(1,0);↵
int mx=0,mt=0;↵
for(int i=1;i<=n;i++)↵
if(t[i]>=mx)↵
mx=t[i],mt=i;↵
// for(int i=1;i<=n;i++)↵
// cerr<<i<<" "<<fa[i]<<" "<<d[i]<<"\n";↵
int ans=mx;↵
for(int i=1;i<=mx;i++)↵
id[g[mt][i-1]]=i,v[i].push_back(g[mt][i-1]);↵
for(int i=mt+1;i<=n;i++)↵
{↵
vector<int> vfa;↵
for(int j:g[i-1])↵
{↵
son[j]=0;↵
if(snum[j])↵
flag[id[j]]=1;↵
}↵
int pos=1;↵
for(int j:g[i])↵
{↵
if(!son[fa[j]])↵
son[fa[j]]=j,vfa.push_back(fa[j]);↵
else↵
{↵
while(flag[pos])↵
pos++;↵
assert(pos<=mx);↵
id[j]=pos,v[pos].push_back(j),pos++;↵
}↵
}↵
while(flag[pos])↵
pos++;↵
assert(pos<=mx);↵
int lst=pos;↵
for(int x:vfa)↵
{↵
id[son[x]]=lst;↵
v[lst].push_back(son[x]);↵
lst=id[x];↵
}↵
for(int j:g[i-1])↵
flag[id[j]]=0;↵
}↵
for(int i=mt-1;i>=1;i--)↵
{↵
vector<int> vfa;↵
for(int j:g[i])↵
son[j]=0;↵
for(int j:g[i+1])↵
{↵
flag[id[j]]=1;↵
if(!son[fa[j]])↵
son[fa[j]]=j,vfa.push_back(fa[j]);↵
}↵
assert(!vfa.empty());↵
if(vfa.size()==1)↵
{↵
if(ans==t[i+1])↵
ans++,id[vfa[0]]=ans,v[ans].push_back(vfa[0]);↵
else↵
{↵
int pos=1;↵
while(flag[pos])↵
pos++;↵
assert(pos<=ans);↵
id[vfa[0]]=pos,v[pos].push_back(vfa[0]);↵
}↵
}↵
else↵
{↵
for(int i=0;i<vfa.size();i++)↵
id[vfa[i]]=id[son[vfa[(i+1)%vfa.size()]]],v[id[vfa[i]]].push_back(vfa[i]);↵
}↵
for(int j:g[i+1])↵
flag[id[j]]=0;↵
for(int x:vfa)↵
flag[id[x]]=1;↵
int pos=1;↵
for(int x:g[i])↵
if(!son[x])↵
{↵
while(flag[pos])↵
pos++;↵
assert(pos<=ans);↵
id[x]=pos,v[pos].push_back(x);↵
pos++;↵
}↵
for(int x:vfa)↵
flag[id[x]]=0;↵
}↵
cout<<ans<<"\n";↵
for(int i=1;i<=ans;i++)↵
{↵
cout<<v[i].size()<<" ";↵
for(int x:v[i])↵
cout<<x<<" ";↵
cout<<"\n";↵
}↵
}↵
signed main()↵
{↵
ios::sync_with_stdio(0);↵
cin.tie(0);↵
cout.tie(0);↵
int t;↵
cin>>t;↵
for(int i=1;i<=t;i++)↵
test();↵
}↵
```↵
</spoiler>↵
↵
## [2183E — LCM is Legendary Counting Master](https://mirror.codeforces.com/contest/2183/problem/E)↵
↵
Idea & Preparation: [user:Gold14526,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 7, option1] Good Problem ↵
- [likes: 7, option2] Okay Problem ↵
- [likes: 7, option3] Bad Problem ↵
- [likes: 7, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider the term $\frac{1}{\operatorname{lcm}(a_i,a_{i+1})}$. What properties can you derive if $a_i < a_{i+1}$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
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 < a_{i+1}$, the inequality $\gcd(a_i,a_{i+1}) \le a_{i+1}-a_i$ always holds.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
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}$.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
If $y > 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 < y \le m$?↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Note that↵
$$↵
\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}↵
$$↵
The equality holds if and only if $\gcd(a_i,a_{i+1})=a_{i+1}-a_i$ for all $1\le i<n$, and $a_1=1$. Thus, the problem is transformed into counting the number of sequences that satisfy these conditions.↵
↵
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)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
#define cint const int↵
#define uint unsigned int↵
#define cuint const unsigned int↵
#define ll long long↵
#define cll const long long↵
#define ull unsigned long long↵
#define cull const unsigned long long↵
using namespace std;↵
namespace FastIO↵
{↵
const int BUF_SIZE=1<<20;↵
char in_buf[BUF_SIZE],out_buf[BUF_SIZE];↵
char* in_ptr=in_buf+BUF_SIZE;↵
char* out_ptr=out_buf;↵
char get_char()↵
{↵
if(in_ptr==in_buf+BUF_SIZE)↵
{↵
in_ptr=in_buf;↵
fread(in_buf,1,BUF_SIZE,stdin);↵
}↵
return *in_ptr++;↵
}↵
void put_char(char c)↵
{↵
if(out_ptr==out_buf+BUF_SIZE)↵
{↵
fwrite(out_buf,1,BUF_SIZE,stdout);↵
out_ptr=out_buf;↵
}↵
*out_ptr++=c;↵
}↵
struct Flusher↵
{↵
~Flusher()↵
{↵
if(out_ptr!=out_buf)↵
{↵
fwrite(out_buf,1,out_ptr-out_buf,stdout);↵
}↵
}↵
} flusher;↵
}↵
#define getchar FastIO::get_char↵
#define putchar FastIO::put_char↵
inline int read()↵
{↵
int x=0;↵
bool zf=1;↵
char ch=getchar();↵
while(ch<'0'||ch>'9')↵
{↵
if(ch=='-')↵
{↵
zf=0;↵
}↵
ch=getchar();↵
}↵
while(ch>='0'&&ch<='9')↵
{↵
x=(x<<1)+(x<<3)+(ch^48);↵
ch=getchar();↵
}↵
return zf?x:-x;↵
}↵
void print(cint x)↵
{↵
if(x==0)↵
{↵
putchar('0');↵
return;↵
}↵
char buf[12];↵
int len=0,y=x;↵
if(y<0)↵
{↵
putchar('-');↵
y=-y;↵
}↵
while(y)↵
{↵
buf[len++]=(y%10)+'0';↵
y/=10;↵
}↵
while(len--)↵
{↵
putchar(buf[len]);↵
}↵
}↵
inline void princh(cint x,const char ch)↵
{↵
print(x);↵
putchar(ch);↵
}↵
cint N=3000,M=3000;↵
cint mod=998244353;↵
int n,m;↵
int a[N+1];↵
int dp[N+1][M+1];↵
vector<int>d[M+1];↵
int ans;↵
void solve()↵
{↵
n=read();↵
m=read();↵
for(int i=1;i<=n;++i)↵
{↵
a[i]=read();↵
}↵
if(a[1]>1)↵
{↵
princh(0,'\n');↵
return;↵
}↵
dp[1][1]=1;↵
for(int i=2;i<=n;++i)↵
{↵
for(int j=1;j<=m;++j)↵
{↵
dp[i][j]=0;↵
for(int x:d[j])↵
{↵
(dp[i][j]+=dp[i-1][j-x])>=mod?(dp[i][j]-=mod):0;↵
}↵
}↵
if(a[i])↵
{↵
for(int j=1;j<=m;++j)if(j!=a[i])dp[i][j]=0;↵
}↵
}↵
ans=0;↵
for(int j=1;j<=m;++j)↵
{↵
(ans+=dp[n][j])>=mod?(ans-=mod):0;↵
}↵
princh(ans,'\n');↵
}↵
int main()↵
{↵
// freopen(".in","r",stdin);↵
// freopen(".out","w",stdout);↵
for(int i=1;i<=M;++i)↵
{↵
for(int j=i;j<=M;j+=i)↵
{↵
d[j].push_back(i);↵
}↵
}↵
int T=read();↵
while(T--)solve();↵
return 0;↵
}↵
↵
```↵
</spoiler>↵
↵
## [2183F — Jumping Man](https://mirror.codeforces.com/contest/2183/problem/F)↵
↵
Idea & Preparation: [user:Neil_Qian,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 8, option1] Good Problem ↵
- [likes: 8, option2] Okay Problem ↵
- [likes: 8, option3] Bad Problem ↵
- [likes: 8, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Calculating the sum of squares of counts is difficult.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. ↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try dynamic programming. ↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
The DP transition is continuous over the DFS sequence.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Calculating the sum of squares of counts is difficult, so we consider transforming it into the number of ways to choose two identical strings. ↵
↵
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. ↵
↵
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. ↵
↵
The time complexity is $O(n^2)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
typedef long long ll;↵
↵
const int MAXN = 5e3 + 10;↵
const int mod = 998244353;↵
↵
inline void cadd(int &x, int y) { x += y, x < mod || (x -= mod); }↵
inline int add(int x, int y) { return x += y, x < mod ? x : x - mod; }↵
inline int sub(int x, int y) { return x -= y, x < 0 ? x + mod : x; }↵
↵
int T, n, ans[MAXN], sum[MAXN][MAXN]; char s[MAXN];↵
↵
vector<int> g[MAXN]; int in[MAXN], out[MAXN], rev[MAXN], id;↵
↵
void init(int u, int f = 0) {↵
in[u] = ++id, rev[id] = u;↵
for (int v : g[u]) if (v != f) init(v, u);↵
out[u] = id;↵
}↵
↵
inline ↵
int query(int al, int ar, int bl, int br) {↵
return sub(add(sum[al][bl], sum[ar + 1][br + 1]), add(sum[al][br + 1], sum[ar + 1][bl]));↵
}↵
↵
int main() {↵
for (scanf("%d", &T); T--; ) {↵
scanf("%d%s", &n, s + 1), id = 0;↵
for (int i = 1, u, v; i < n; i++) {↵
scanf("%d%d", &u, &v);↵
g[u].emplace_back(v), g[v].emplace_back(u);↵
}↵
init(1);↵
for (int i = n; i; i--) {↵
for (int j = n; j; j--) {↵
if (s[rev[i]] == s[rev[j]]) {↵
sum[i][j] = add(query(in[rev[i]] + 1, out[rev[i]], in[rev[j]] + 1, out[rev[j]]), 1);↵
}↵
cadd(sum[i][j], sub(add(sum[i + 1][j], sum[i][j + 1]), sum[i + 1][j + 1]));↵
}↵
}↵
for (int i = 1; i <= n; i++) {↵
printf("%d ", query(in[i], out[i], in[i], out[i]));↵
}↵
puts("");↵
for (int i = 1; i <= n; i++) g[i].clear();↵
for (int i = 1; i <= n; i++) {↵
for (int j = 1; j <= n; j++) sum[i][j] = 0;↵
}↵
}↵
}↵
```↵
</spoiler>↵
↵
## [2183G — Snake Instructions](https://mirror.codeforces.com/contest/2183/problem/G)↵
↵
Idea & Preparation: [user:xvchongyv,2025-12-23] & [user:wangmarui,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 9, option1] Good Problem ↵
- [likes: 9, option2] Okay Problem ↵
- [likes: 9, option3] Bad Problem ↵
- [likes: 9, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Consider under what circumstances you need to return $-1$.↵
↵
<spoiler summary="Answer">↵
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.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Consider what information you can get by querying the string `L`.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
The case analysis process for this problem is not complicated.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Consider querying three fixed strings to determine all snakes' speeds.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
Consider querying the three strings: `L`, `LR`, and `R`.↵
↵
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.↵
↵
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`.↵
↵
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):↵
↵
- `01`.↵
- `02`.↵
- `0_2`.↵
- `12`.↵
↵
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.↵
↵
First, try to determine some snakes with speed $2$. For the position and speed of such a snake, the following cases allow direct determination:↵
↵
- The previous snake is at a distance of $1$ and has been determined to have speed $1$.↵
- 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:↵
- If the previous snake's speed is $0$, it will definitely not be killed in a collision, so this case is impossible.↵
- 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$.↵
- The previous snake is at a distance of $2$ and has been determined to have speed $0$.↵
↵
The case analysis above naturally eliminates the `0_2` and `12` scenarios.↵
↵
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.↵
↵
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.↵
↵
Time complexity: $O(\sum n)$ or $O(\sum n \log n)$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
/*↵
OI 2025 RP++!!!↵
↵
author: wmrqwq[alsu]↵
↵
time: 2025/7/12↵
↵
contest:↵
↵
Tips:↵
↵
RE, MLE?↵
greedy, dp?↵
natural time?↵
map, umap?↵
giveup rating, get score.↵
brute force, right solution?↵
%mod? std/run/maker/checker?↵
add bruteforce?↵
clear?↵
double, long double?↵
O(n)? O(n^2)!↵
make data!↵
↵
last but not least.↵
↵
bruteforce -> SegTree?↵
Think more.↵
*/↵
//#pragma GCC optimize("Ofast")↵
//#pragma GCC optimize("unroll-loops")↵
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
#include<bits/stdc++.h>↵
using namespace std;↵
//#define map unordered_map↵
#define re register↵
#define ll long long↵
#define cll const ll↵
#define forl(i,a,b) for(re ll (i)=(a);i<=(b);(i)++)↵
#define forr(i,a,b) for(re ll (i)=(a);i>=(b);(i)--)↵
#define forll(i,a,b,c) for(re ll (i)=(a);i<=(b);(i)+=(c))↵
#define forrr(i,a,b,c) for(re ll (i)=(a);i>=(b);(i)-=(c))↵
#define forL(i,a,b,c) for(re ll (i)=(a);((i)<=(b)) && (c);(i)++)↵
#define forR(i,a,b,c) for(re ll (i)=(a);((i)>=(b)) && (c);(i)--)↵
#define forLL(i,a,b,c,d) for(re ll (i)=(a);((i)<=(b)) && (d);(i)+=(c))↵
#define forRR(i,a,b,c,d) for(re ll (i)=(a);((i)>=(b)) && (d);(i)-=(c))↵
#define pii pair<ll,ll>↵
#define mid ((l+r)>>1)↵
#define lowbit(x) (x&-x)↵
#define pb push_back↵
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);↵
// #define endl '\n'↵
#define QwQ return 0;↵
#define db long double↵
#define ull unsigned long long↵
#define lcm(x,y) (1ll*(x)/__gcd(x,y)*(y))↵
#define Sum(x,y) (1ll*((x)+(y))*((y)-(x)+1)/2)↵
#define x first↵
#define y second↵
#define aty cout<<"Yes\n";↵
#define atn cout<<"No\n";↵
#define cfy cout<<"YES\n";↵
#define cfn cout<<"NO\n";↵
#define xxy cout<<"yes\n";↵
#define xxn cout<<"no\n";↵
#define printcf(x) x?cout<<"YES\n":cout<<"NO\n";↵
#define printat(x) x?cout<<"Yes\n":cout<<"No\n";↵
#define printxx(x) x?cout<<"yes\n":cout<<"no\n";↵
#define maxqueue priority_queue<ll>↵
#define minqueue priority_queue<ll,vector<ll>,greater<ll>>↵
#define bug1 cout<<"bug1,AWaDa?\n";↵
#define bug2 cout<<"bug2,AWaDa!\n";↵
#define bug3 cout<<"bug3,AKTang?\n";↵
#define bug4 cout<<"bug4,AKTang!\n";↵
#define IM (ll)1e9↵
#define LM (ll)1e18↵
#define MIM (ll)-1e9↵
#define MLM (ll)-1e18↵
#define sort stable_sort↵
ll rd(ll&x){cin>>x;return x;}ll rd(){ll x;cin>>x;return x;}↵
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;}↵
ll pw(ll x){return 1ll<<x;}↵
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;}↵
// 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;}↵
// 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;}↵
ll _t_;↵
struct BIT{↵
ll maxn;↵
ll tree[1000010];↵
void clear(ll l){↵
forl(i,0,l)↵
tree[i]=0;↵
}↵
void add(ll x,ll y){↵
for(;x<=maxn;x+=lowbit(x))↵
tree[x]+=y;↵
}↵
ll query(ll x){↵
ll S=0;↵
for(;x;x-=lowbit(x))↵
S+=tree[x];↵
return S;↵
}↵
ll query(ll l,ll r){↵
return query(r)-query(l-1);↵
}↵
};↵
// ll lg[1000010];↵
void Init(){↵
// forl(i,2,1e6+5)↵
// lg[i]=lg[i>>1]+1;↵
}↵
//sunny↵
ll n;↵
ll a[100010];↵
ll ans[100010];↵
vector<ll>vl,vr,vlr;↵
//tulpa↵
void ask(string s,vector<ll>&v)↵
{↵
cout<<"? "<<s<<endl;↵
v.pb(rd());↵
forl(i,1,v[0])↵
v.pb(rd());↵
}↵
/*↵
012↵
↵
01↵
02↵
↵
120↵
*/↵
void _clear(){}↵
void solve()↵
{↵
_clear();↵
vl.clear(),vr.clear(),vlr.clear();↵
cin>>n;↵
forl(i,1,n)↵
cin>>a[i],↵
ans[i]=-1;↵
ask("L",vl),ask("R",vr),ask("LR",vlr);↵
ll sz=vlr[0],L=1;↵
forl(i,1,n)↵
{↵
while(L<=sz && vlr[L]<a[i])↵
L++;↵
if(L<=sz && vlr[L]==a[i])↵
ans[i]=vlr[L]-vl[L];↵
}↵
forl(i,2,n)↵
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)))↵
{↵
// if(ans[i-1]==-1)↵
// ans[i-1]=1;↵
ans[i]=2;↵
}↵
forl(i,1,n)↵
if(ans[i]==-1)↵
ans[i]=*lower_bound(vr.begin()+2,vr.end(),a[i])-a[i];↵
forl(i,1,n-2)↵
if(a[i]+1==a[i+1] && a[i+1]+1==a[i+2] && ans[i]+ans[i+2]==0 && ans[i+1])↵
{↵
cout<<"! "<<-1<<endl;↵
return ;↵
}↵
cout<<"! ";↵
forl(i,1,n)↵
cout<<ans[i]<<' ';↵
cout<<endl;↵
}↵
int main()↵
{↵
Init();↵
// freopen("tst.txt","r",stdin);↵
// freopen("sans.txt","w",stdout);↵
IOS;↵
_t_=1;↵
cin>>_t_;↵
while(_t_--)↵
solve();↵
QwQ;↵
}↵
```↵
</spoiler>↵
↵
## [2183H — Minimise Cost](https://mirror.codeforces.com/contest/2183/problem/H)↵
↵
Idea & Preparation: [user:Hoks_,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 10, option1] Good Problem ↵
- [likes: 10, option2] Okay Problem ↵
- [likes: 10, option3] Bad Problem ↵
- [likes: 10, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Subsequences are too hard; can we find some properties? How should we approach the case where $n=k=500$?↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
The approach for $n=k=500$ is too naive; how can we optimize it? What if $n=k=5000$?↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
What if we are guaranteed that the count of positive numbers $m \le 5000$?↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
The requirement of **exactly** $k$ segments, combined with the previous optimizations, suggests what technique? Consider the data constraints.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
We can observe the following two conclusions:↵
↵
1. After sorting all elements, the subsequence we partition must correspond to a **substring** (contiguous segment) of the new sequence.↵
2. If the lengths of the partitioned segments are $l_1, l_2, \dots, l_k$, then it must hold that $l_i \ge l_{i+1}$ for $i \in [1, k)$.↵
↵
<spoiler summary="Proof of Length Monotonicity">↵
Define the range of a sequence $b$ as $[\min b_i, \max b_i]$.Take two subsequences $s_i, s_j$ such that their value ranges intersect. Let their lengths be $l_i, l_j$.Without loss of generality, assume $l_i > l_j$.Consider the set of all elements in $s_i$ and $s_j$. If we take the smallest $l_i$ elements to form a new $s_i$ and the remaining to form $s_j$, the cost decreases.↵
↵
Why? Consider an element $a_x$. It is multiplied by either $l_i$ or $l_j$. We only care about elements that switch coefficients. With the split point at the $l_i$-th number, the number of elements switching from coefficient $l_j$ to $l_i$ equals the number of elements switching from $l_i$ to $l_j$. Since the array is sorted, the former elements are strictly smaller than the latter. Given $l_i > l_j$, switching the larger coefficient to smaller numbers reduces the total sum.By repeatedly adjusting, we arrive at the conclusion.↵
</spoiler>↵
↵
Based on this, we can design a brute-force DP. Let $f_{i,j}$ be the minimum weight sum for partitioning the first $i$ numbers into exactly $j$ segments.$$f_{i,j}=\min\limits_{k=1}^{i-1} (f_{k,j-1}+(s_i-s_k)\cdot(i-k))$$ This runs in $O(n^2k)$ .↵
↵
We can optimize this DP. Let $w(l,r) = (r-l+1)\cdot(s_r-s_{l-1})$. If all numbers are non-negative, the cost function satisfies the Quadrangle Inequality (QI). Using Knuth Optimization, we can reduce the complexity to $O(nk)$.↵
↵
Now consider the case with negative numbers.We observe:↵
↵
1. For positive numbers, more segments are better (smaller coefficients).↵
2. For negative numbers, fewer segments are better (larger coefficients).↵
↵
Since $l_1$ is the largest coefficient, we prioritize assigning the negative numbers to the first segment. Let $m$ be the count of non-negative numbers.If $k \le m$, the optimal strategy is to assign a prefix (containing all negative numbers and some positive numbers) to the first segment, and partition the remaining suffix of positive numbers into $k-1$ segments.↵
↵
<spoiler summary="Proof: The segment containing negative numbers is exactly one">↵
We prove that splitting negative numbers into 2 segments is not optimal.Consider a configuration: $a_1, \dots, a_x$ (negative), $a_{x+1}, \dots, a_n$ (positive).Suppose we have a partition $[a_1, a_l]$ and $[a_{l+1}, a_r]$ where $l < x < r$. We can shift the split to $[a_1, a_x]$ and $[a_{x+1}, a_r]$.Let $l_1=l, l_2=x-l, l_3=r-x$. Let $S_1, S_2, S_3$ be the sum of absolute values in the respective ranges.The change in cost is a reduction of $S_1 l_2 + S_3 l_2 - S_2(l_1 - l_3)$.Since $S_3 l_2 + S_2 l_3 \ge 0$, we only need $S_1 l_2 \ge S_2 l_1$, or $S_1/l_1 \ge S_2/l_2$.This means the average absolute value of the earlier segment is larger. Since the array is sorted (and values are negative), the absolute values are indeed decreasing, so this holds.↵
</spoiler>↵
↵
If $k > m$, we assign each positive number to its own segment, and partition the negative numbers into the remaining segments.↵
↵
Finally, consider $n, k \le 2 \times 10^5$.The constraints and the "exactly $k$ segments" requirement suggest **Alien's Trick**. The cost function $w(l,r)$ for positive numbers satisfies QI, implying convexity.We binary search a penalty $\lambda$. The transitions become $dp[i] = \min (dp[j] + w(j+1, i) + \lambda)$.To handle negative numbers efficiently, we use the property that negative numbers (indices $x \le n-m$) cannot be optimal transition points (except for the base case $0$). By excluding these indices from the decision set, the cost function satisfies the Quadrangle Inequality for all valid transitions.↵
↵
<spoiler summary="Proof of QI with Restricted Transitions">↵
The Quadrangle Inequality condition simplifies to:$$(d-c)\cdot(s_b-s_a)+(b-a)\cdot(s_d-s_c)\ge0$$ If all $a_i \ge 0$ , $s$ is non-decreasing, and it holds.If we exclude negative indices, the only special case is transition from $0$ (where $s_a=0$). In this case, $(d-c)s_b + b(s_d-s_c) \ge 0$ holds because $s$ is increasing for the suffix and lengths are positive.Thus, the restricted DP has decision monotonicity.↵
</spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define S cerr << "SYT AK IOI" << endl;↵
#define M cerr << "MKF AK IOI" << endl;↵
↵
using ll = long long;↵
using pii = pair<int, int>;↵
using uint = unsigned int;↵
using ull = unsigned long long;↵
mt19937 rnd(0 ^ (*new int));↵
// #define int long long //use it if possible↵
#define pb(x) push_back(x)↵
#define F(i, a, b) for (int i = (a), i##end = (b); i <= (i##end); ++i)↵
#define UF(i, a, b) for (int i = (a), i##end = (b); i >= (i##end); --i)↵
#define gc() getchar()↵
#define pc putchar↵
#define popcount(x) __builtin_popcount(x)↵
↵
inline void init();↵
inline void IO();↵
__int128 n,k,p;↵
__int128 a[1000100],lim[1000100],q[1000100];↵
array<__int128,2>dp[1000100];↵
ll rd()↵
{↵
ll x;↵
cin>>x;↵
return x;↵
}↵
inline array<__int128,2> calc(__int128 i,__int128 j,__int128 x){↵
return (array<__int128,2>){dp[j][0]+(i-j)*(a[i]-a[j])-x,dp[j][1]+1};↵
}↵
inline bool c2(__int128 x,__int128 i,__int128 j,__int128 m){↵
return calc(x,j,m)>=calc(x,i,m);↵
}↵
inline __int128 find(__int128 i,__int128 j,__int128 m){↵
int l=i,r=n,mid,res=n+1;↵
while(l<=r) c2(mid=l+r>>1,i,j,m)?res=mid,r=mid-1:l=mid+1;↵
return res;↵
}↵
inline __int128 ck(__int128 mid){↵
for(__int128 i=p,l=1,r=1;i<=n;i++){↵
for(;l<r&&lim[l]<=i;l++);dp[i]=calc(i,q[l],mid);↵
for(;l<r&&lim[r-1]>=find(i,q[r],mid);r--);↵
lim[r]=find(i,q[r],mid);q[++r]=i;↵
}↵
return dp[n][1]<=k;↵
}↵
void print(__int128 x){if(x<0) putchar('-'),x=-x;if(x>9) print(x/10);putchar(x%10+'0');}↵
inline void mian()↵
{↵
// cin>>n>>k;↵
n=rd(),k=rd();↵
F(i,1,n)a[i]=rd();↵
sort(a+1,a+1+n);↵
F(i,2,n)a[i]+=a[i-1];↵
if(k==1){print(n*a[n]);putchar('\n');return;}↵
__int128 ans=(n-k+1)*a[n-k+1]+a[n]-a[n-k+1];p=1;↵
while(p<=n and a[p]-a[p-1]<=0)p++;↵
while(p<=n and p*a[p]-a[p]+a[p-1]<(p-1)*a[p-1])p++;↵
--p,p=max(p,(__int128)1);↵
if(n-p<k-1){print(ans);putchar('\n');return;}↵
__int128 l=-n*n*(__int128)(1e9),r=-l,mid,res=l;↵
while(l<=r) ck(mid=l+r>>1)?res=mid,l=mid+1:r=mid-1;↵
ck(res);↵
ans=min(ans,(__int128)k*res+dp[n][0]);↵
print(ans);putchar('\n');↵
}↵
signed main()↵
{↵
IO();↵
cin.tie(nullptr)->sync_with_stdio(false);↵
int T = 1;↵
#define multitest 1↵
#ifdef multitest↵
T=rd();↵
#endif↵
init();↵
↵
while (T--)↵
mian();↵
return 0;↵
}↵
↵
inline void init()↵
{↵
}↵
↵
#define NAME(x) #x↵
#define INNAME(x) NAME(x)↵
// #define FILEIO sub3_15↵
inline void IO()↵
{↵
#ifdef FILEIO↵
freopen(INNAME(FILEIO) ".in", "r", stdin), freopen(INNAME(FILEIO) ".out", "w", stdout);↵
#endif↵
}↵
↵
```↵
</spoiler>↵
↵
## [2183I1 — Pairs Flipping (Easy Version)](https://mirror.codeforces.com/contest/2183/problem/I1)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23] Special Thanks: [user:N_z_,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 11, option1] Good Problem ↵
- [likes: 11, option2] Okay Problem ↵
- [likes: 11, option3] Bad Problem ↵
- [likes: 11, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Hint 1">↵
Try dividing the sequence into two equal halves.↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
Let us assume $n$ is an odd number. We shall attempt to divide it into the first $\frac{n-1}2$ elements and the subsequent $\frac{n+1}2$ elements, eliminating both halves by assigning odd and even lengths respectively.↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
Try processing recursively to reduce $n$ to a smaller scale.↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
Try further optimizing one of the two halves.↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
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$.↵
↵
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.)↵
↵
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<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.↵
↵
Proof that the above situation occurs at most $\left\lfloor\log_3\frac{n}2\right\rfloor$ times：↵
↵
- 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 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.↵
</spoiler>↵
↵
↵
<spoiler summary="Implementation">↵
```↵
#include <bits/stdc++.h>↵
std::ostream& operator<<(std::ostream& os, const std::pair<T1, T2>& p) {↵
os << "(" << p.first << ", " << p.second << ")";↵
return os;↵
}↵
// your original is_iterable (unchanged)↵
template <typename T, typename = void>↵
struct is_iterable : std::false_type {};↵
↵
template <typename T>↵
struct is_iterable<T, std::void_t<↵
decltype(std::begin(std::declval<T>())),↵
decltype(std::end(std::declval<T>()))↵
>> : std::true_type {};↵
↵
// detect std::basic_string<...>↵
template <typename T>↵
struct is_string : std::false_type {};↵
↵
template <typename CharT, typename Traits, typename Alloc>↵
struct is_string<std::basic_string<CharT, Traits, Alloc>> : std::true_type {};↵
↵
// optionally also detect string_view (C++17)↵
template <typename CharT, typename Traits>↵
struct is_string<std::basic_string_view<CharT, Traits>> : std::true_type {};↵
↵
// now enable the generic container printer only when T is iterable AND not a string↵
template <typename T>↵
typename std::enable_if<↵
is_iterable<T>::value && !is_string<T>::value,↵
std::ostream&↵
>::type↵
operator<<(std::ostream& os, const T& container) {↵
os << "{ ";↵
for (auto it = std::begin(container); it != std::end(container); ++it) {↵
os << *it;↵
if (std::next(it) != std::end(container)) os << ", ";↵
}↵
os << " }";↵
return os;↵
}↵
↵
// Queue-like adapters (stack, queue, priority_queue)↵
template <typename T>↵
ostream& operator<<(ostream& os, queue<T> q) {↵
os << "{ ";↵
while (!q.empty()) { os << q.front(); q.pop(); if (!q.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
template <typename T>↵
ostream& operator<<(ostream& os, stack<T> st) {↵
os << "{ ";↵
while (!st.empty()) { os << st.top(); st.pop(); if (!st.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
template <typename T>↵
ostream& operator<<(ostream& os, priority_queue<T> pq) {↵
os << "{ ";↵
while (!pq.empty()) { os << pq.top(); pq.pop(); if (!pq.empty()) os << ", "; }↵
os << " }";↵
return os;↵
}↵
↵
// using namespace std;↵
using ll = long long;↵
#define add push_back ↵
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)↵
#define F0R(i,a) FOR(i,0,a)↵
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)↵
#define R0F(i,a) ROF(i,0,a)↵
#define f first↵
#define s second↵
#define trav(a,x) for (auto& a: x)↵
#define int long long↵
#define vt vector↵
#define endl "\n"↵
#define enld "\n"↵
#define double long double↵
const ll mod = 998244353;↵
const ll inf = 1e18;↵
template<typename T> using min_pq = std::priority_queue<T, std::vector<T>, std::greater<T>>; //defines min_pq↵
↵
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());↵
int rand_num(int l, int r) {↵
return rnd()%(r-l+1)+l;↵
}↵
signed main() {↵
ios_base::sync_with_stdio(false); ↵
cin.tie(0);↵
// freopen("input.txt" , "r" , stdin);↵
// freopen("output.txt" , "w", stdout
ios_base::sync_with_stdio(false); ↵
cin.tie(0);↵
int t;↵
cin >> t;↵
while(t--) {↵
int n;↵
cin >> n;↵
string a;↵
cin >> a;↵
vt
auto operate = [&](int i)->void{↵
if(ops[i]==0) return;↵
else {↵
if(a[ops[i]-1+i]=='1') a[ops[i]-1+i]='0'; else
a[ops[i]-1+i]
}↵
auto
if(l>r) return;↵
if(a[l]==a[r]) {↵
if(a[l]=='1') ops[r-l]=l+1, operate(r-l);↵
self(self, l+1, r-1, x);↵
return;↵
}↵
if(x!=-1 && x<l) {↵
if(x+r-l>=l) {↵
ops[r-l]=x+1, operate(r-l);↵
}↵
} else if(x!=-1 && x>r) {↵
if(x-r+l<=r) {↵
ops[r-l]=x-r+l+1, operate(r-l);↵
}↵
}↵
if(a[l]=='1') {↵
self(self, l+1, r-1, l);↵
} else {↵
self(self, l+1, r-1, r);↵
}↵
};↵
auto
if(l>r) return -1;↵
if(l==r) if(a[l]=='1') return l; else return -1;↵
int x = self(self, l+1, r-1);↵
if(a[l]=='1') ops[r-l]=l+1, operate(r-l);↵
return x;↵
} else {↵
if(x!=-1) {↵
ops[r-l]=x+1, operate(r-l);↵
}↵
if(a[l]=='1') return l;↵
else return r;↵
}↵
};↵
5↵
1-2 3-5↵
7↵
1-3 4-7↵
*/↵
g(g
if(n%2)
else
// cout << ops << endl;↵
FOR(i, 1, n/2+1) cout << ops[i] << " ";↵
cout << endl;↵
// cout << a << endl;↵
↵
}↵
return 0;↵
}↵
/*↵
1100111 01010100↵
1100111 ↵
0: ?↵
2: ?↵
↵
01010100↵
7 14↵
8 13↵
↵
1111111011↵
1111 11101↵
1 4↵
2 3↵
5 9↵
6 8↵
*/
for(int i=1; i<=n/2; i++) cout << ops[i] << " ";↵
cout << endl;↵
}↵
return 0;↵
}↵
```↵
</spoiler>↵
↵
## [2183I2 — Pairs Flipping (Hard Version)](https://mirror.codeforces.com/contest/2183/problem/I2)↵
↵
Idea & Preparation: [user:Network_Error,2025-12-23]↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 12, option1] Good Problem ↵
- [likes: 12, option2] Okay Problem ↵
- [likes: 12, option3] Bad Problem ↵
- [likes: 12, option4] Didn't Solve↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
In the approach of I1, we can see that the main cost comes from the fact that isolated $1$'s outside the interval sometimes cannot be eliminated. We consider optimizing this situation.↵
↵
The following diagram illustrates a scenario where one such elimination fails.↵
↵
```↵
1111111111111|1??????0|1111111111110↵
p l r q↵
```↵
↵
Here, $p$ is the previous $1$ we could not eliminate (assume without loss of generality that $p<l$), $[l, r]$ is the current interval being processed, and $l-p \ge r-l$ (making it impossible to eliminate directly using the previous method). $q$ is the symmetric point of $p$.↵
↵
The operation lengths we can use at this point are $q-p-3, q-p-5, q-p-7, \ldots, r-l$. Note that $q-p-1$ is excluded because we have already used it earlier.↵
↵
Let the lengths of the three segments be $A$, $B$, and $C$, where $A = C$. This scenario is denoted as $F(A, B)$.↵
↵
Next, we will study in detail how to perform elimination for $F(A, B)$.↵
↵
If $A < B-1$, we have essentially solved it in I1.↵
↵
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.↵
↵
For other cases, we can demonstrate that it is always possible to find a method to eliminate until only one $1$ remains. 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.↵
↵
Thus, between every two adjacent $1$'s that cannot be eliminated, we can always save one elimination, leaving a $1$ near $l$ or $r$. Let the interval length be $s$. Whenever a $1$ cannot be eliminated, $s$ becomes at least $\frac19 s + \frac{2}{3}$. The number of remaining $1$'s is approximately $\log_9\frac{n}{2}$. When the interval length does not exceed 18, we can use an $O(n^2 2^n)$ dynamic programming approach to find the optimal solution. The optimal solution can always leave no more than $1$ remaining $1$. It can be proven that when $n \le 2 \times 10^6$, the total number of $1$'s does not exceed $7$.↵
</spoiler>↵
↵
<spoiler summary="Implementation">↵
```↵
#include<bits/stdc++.h>↵
bool Mbg;↵
using namespace std;↵
#define vec vector↵
#define pb push_back↵
#define eb emplace_back↵
#define siz(vec) (int)((vec).size())↵
#define all(vec) (vec).begin(),(vec).end()↵
template<class T>↵
void operator +=(vec<T> &lhs,const T &rhs){lhs.push_back(rhs);}↵
#define pii pair<int,int>↵
#define x first↵
#define y second↵
#define mp make_pair↵
#define exc(expr) if(expr)continue;↵
#define stop(expr) if(expr)break;↵
#define ret(expr) if(expr)return;↵
#define deb(var) cout<<#var<<'='<<(var)<<"; "↵
#define debl(var) cout<<#var<<'='<<(var)<<";\n"↵
#define ins insert↵
#define era erase↵
#define lb lower_bound↵
#define ub upper_bound↵
#define int long long↵
#define inf (long long)(1.1e18)↵
template<class T>↵
bool Min(T &x,const T &y){return x>y?x=y,1:0;}↵
template<class T>↵
bool Max(T &x,const T &y){return x<y?x=y,1:0;}↵
const int mod=998244353;↵
void Add(int &x,const int &y){x=x+y<mod?x+y:x+y-mod;}↵
void Dec(int &x,const int &y){x=x>=y?x-y:x-y+mod;}↵
int fpm(int x,int y){↵
int ans=1;for(;y;y>>=1,x=1ll*x*x%mod)if(y&1)ans=1ll*x*ans%mod;return ans;↵
}↵
mt19937 eng(time(0));↵
↵
int n;↵
char s[2000010],S[2000010];↵
bool used[2000010];↵
int ans[2000010];↵
void Oper(int x,int y){↵
if(x>y)swap(x,y);↵
assert(1<=x&&x<y&&y<=n);↵
assert(!used[y-x]);↵
used[y-x]=1;↵
ans[y-x]=x;↵
s[x]^=1,s[y]^=1;↵
}↵
bool Delete(int x,int y){↵
assert(1<=x&&x<y&&y<=n);↵
if(!used[y-x])return 1;↵
if(ans[y-x]!=x)return 0;↵
used[y-x]=0;↵
ans[y-x]=0;↵
s[x]^=1,s[y]^=1;↵
return 1;↵
}↵
void solve(int l,int r,int p,bool fl){↵
if(l>r)return;↵
assert(~(r-l+1)&1);↵
if(!p){↵
if(s[l]=='1'&&s[r]=='1')Oper(l,r);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
// 鍋囧畾p!=0↵
↵
// 1. 妫€鏌ヤ笁鍊嶉暱搴?↵
↵
int x=l+r-p,y=p;↵
if(x>y)swap(x,y);↵
int A=l-x,B=r-l+1,C=y-r;↵
assert(A==C);↵
↵
int len=A+B+C-3;↵
auto Init=[&](){↵
for(int i=x+1;i<l;i++)assert(Delete(i,l+r-i));↵
};↵
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;↵
Oper(a,b);↵
};↵
↵
auto get1=[&](){↵
int tot=0,pos=0;↵
for(int i=x;i<=l;i++){↵
if(s[i]=='1'){↵
++tot,pos=i;↵
}↵
}↵
for(int i=r;i<=y;i++){↵
if(s[i]=='1'){↵
++tot,pos=i;↵
}↵
}↵
assert(tot<=1);↵
return pos;↵
};↵
if(!fl&&r-l+1>=10){ // 杩涘叆鍒嗘敮↵
int mask=(s[l]-'0')|((s[r]-'0')<<1);↵
if(p>r)mask=(s[r]-'0')|((s[l]-'0')<<1);↵
if(A==B-1){↵
Init();↵
if(mask==0){↵
for(int i=0;i<=B-4;i++)f(i);↵
f(2*B-5);↵
f(B-3);↵
}else if(mask==1){↵
f(0);↵
for(int i=3;i<=B-3;i+=2)f(i),f(i-1);↵
f(B-1);↵
f(1);↵
}else if(mask==2){↵
for(int i=0;i<=B-3;i++)f(i);↵
f(2*B-3);↵
}else if(mask==3){↵
for(int i=1;i<=B-2;i++)f(i);↵
f(0);↵
}↵
return solve(l+1,r-1,get1(),1);↵
}↵
else if(A==B){↵
// B B B↵
Init();↵
if(mask==0){↵
for(int i=0;i<=B-2;i++)f(i);↵
f(2*B-1);↵
}else if(mask==1){↵
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);↵
}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);↵
}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);↵
}↵
}else if(mask==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);↵
}else if(mask==3){↵
f(0);↵
for(int i=3;i<=B-1;i+=2)f(i),f(i-1);↵
f(1);↵
}↵
return solve(l+1,r-1,get1(),1);↵
}else if(A==B+1){↵
Init();↵
if(mask==0){↵
for(int i=1;i<=B;i++)f(i);↵
f(0);↵
}else if(mask==1){↵
for(int i=1;i<B;i++)f(i);↵
f(0);↵
f(B);↵
}else if(mask==2){↵
for(int i=1;i<=B-1;i+=2){↵
f(i),f(i-1);↵
}↵
f(2*B);↵
}else if(mask==3){↵
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);↵
}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);↵
}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);↵
}↵
}↵
return solve(l+1,r-1,get1(),1);↵
}↵
}↵
↵
if(s[l]=='1'&&s[r]=='1'){↵
Oper(l,r);↵
return solve(l+1,r-1,p,fl);↵
}else if(s[l]!=s[r]||s[l]=='0'&&s[r]=='0'){↵
int len=r-l;↵
if(p+len>l&&p+len<r){↵
Oper(p,p+len);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
if(p-len>l&&p-len<r){↵
Oper(p,p-len);↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
return solve(l+1,r-1,s[l]=='1'?l:s[r]=='1'?r:0,0);↵
}↵
}↵
vec<int> construct(int n){↵
int N=n;↵
fill(used+1,used+n+1,0);↵
fill(ans+1,ans+n+1,0);↵
for(int i=1;i<=n;i++)s[i]=S[i];↵
if(~n&1){↵
Oper(n-n/2,n);↵
--n;↵
}↵
int m=(n+1)/2;↵
if(~m&1)--m;↵
{↵
int r=0;↵
if(s[(m+1)/2]=='1')r=(m+1)/2;↵
for(int i=m/2;i;i--){↵
int j=m+1-i;↵
int mask=(s[i]-'0')<<1|(s[j]-'0');↵
if(mask==3){↵
Oper(i,j);↵
}else if(mask==1){↵
if(r)Oper(r,r+j-i);↵
r=j;↵
}else if(mask==2){↵
if(r)Oper(r,r+j-i);↵
r=i;↵
}↵
}↵
}↵
assert((n-m-1)&1);↵
// debl(m);↵
// debl(n); ↵
solve(m+1,n,0,0);↵
return vec<int>(ans+1,ans+N/2+1);↵
}↵
void work(){↵
cin>>n;↵
for(int i=1;i<=n;i++)cin>>S[i];↵
↵
auto A=construct(n);↵
int c1=count(s+1,s+n+1,'1');↵
↵
reverse(S+1,S+n+1);↵
auto B=construct(n);↵
int c2=count(s+1,s+n+1,'1');↵
↵
if(c1>c2){↵
A=B;↵
for(int i=0;i<n/2;i++){↵
if(A[i])A[i]=n+1-(A[i]+i+1);↵
}↵
}↵
#ifdef ONLINE_JUDGE↵
for(auto x:A)cout<<x<<' ';↵
cout<<'\n';↵
#endif↵
}↵
bool Med;↵
signed main(){↵
// freopen("d.out","r",stdin); ↵
ios::sync_with_stdio(0),↵
cin.tie(0),cout.tie(0);↵
int T=1;cin>>T;while(T--)work();↵
#ifndef ONLINE_JUDGE↵
cout<<"ok\n";↵
#endif↵
// cerr<<"Time: "<<clock()<<" ms;\n";↵
// cerr<<"Memory: "<<abs(&Med-&Mbg)/1024.0/1024.0<<" MiB.\n";↵
}↵
/*↵
- CONTINUE, NON-STOPPING, FOR THE FAITH↵
- START TYPING IF YOU DON'T KNOW WHAT TO DO↵
- STOP TYPING IF YOU DON'T KNOW WHAT YOU'RE DOING↵
*/ ↵
```↵
</spoiler>↵
↵
