Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask.↵
↵
[problem:1711A]↵
↵
<spoiler summary="hint1.">↵
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
↵
void work()↵
{↵
int n;↵
cin>>n;↵
cout<<n<<' ';↵
for (int i=1;i<n;i++)↵
cout<<i<<' ';↵
cout<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1711B]↵
↵
<spoiler summary="hint1.">↵
See the party as a graph.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
Divide the vertices into two categories according to their degrees' parity.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's consider the case where $m$ is odd only, since if $m$ is even the answer is $0$.↵
↵
Assume that you delete $x$ vertices with even degrees and $y$ vertices with odd degrees.↵
↵
If $y \geq 1$, then only deleting one vertex with odd degree would have been enough.↵
↵
If $y=0$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degree.↵
↵
Thus, an optimal solution either has $(x, y) = (0, 1)$ or $(x, y) = (2, 0)$ and the two vertices are adjacent.↵
↵
One can iterate over all possible solutions with such a structure and take the optimal one.↵
↵
Total time complexity: $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100010↵
int x[MAXN],y[MAXN],a[MAXN],degree[MAXN];↵
int n,m;↵
void work()↵
{↵
cin>>n>>m;↵
for (int i=1;i<=n;i++)↵
{↵
degree[i]=0;↵
cin>>a[i];↵
}↵
for (int i=1;i<=m;i++)↵
{↵
cin>>x[i]>>y[i];↵
degree[x[i]]++;↵
degree[y[i]]++;↵
}↵
int ans=INT_MAX;↵
if (m%2==0)↵
ans=0;↵
for (int i=1;i<=n;i++)↵
if (degree[i]%2==1)↵
ans=min(ans,a[i]);↵
for (int i=1;i<=m;i++)↵
if (degree[x[i]]%2==0 && degree[y[i]]%2==0)↵
ans=min(ans,a[x[i]]+a[y[i]]);↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:1710A]↵
↵
<spoiler summary="hint1.">↵
The picture must consist of some stripes with at least $2$ rows or at least $2$ columns.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
When $n$ is odd and all $\lfloor \frac{a_i}{m} \rfloor=2$, we cannot draw a beautiful picture using row stripes.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's first prove hint1 first.↵
↵
If there is a pair of toroidal neighbors with different colors. For example, $col_{x,y}=a$ and $col_{x+1,y}=b(a\neq b)$. Then we will find $col_{x-1,y}=col_{x,y+1}=col_{x,y-1}=a$,$col_{x+2,y}=col_{x+1,y+1}=col_{x+1,y-1}=b$ must hold. Then we find another two pairs of toroidal neighbors $col_{x,y+1},col_{x+1,y+1}$ and $col_{x,y-1},col_{x+1,y-1}$. Repeat such process, we will find the boundary should be like:↵
↵
↵
↵
Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture.↵
↵
So the pattern should be row stripes both with at least $2$ rows or column stripes both with at least $2$ columns.↵
↵
Check if one can draw a beautiful picture with row stripes only or with column stripes only. We consider only the case of row stripes, the reasoning is analogous for column stripes.↵
↵
If it is possible, then $\sum_{i=1}^{n} \lfloor \frac{a_i}{m} \rfloor \geq n$ must hold.↵
↵
If $n$ is even, then such a condition is enough.↵
↵
If $n$ is odd, there must be some $\lfloor \frac{a_i}{m} \rfloor \geq 3$. In this case, you can draw a beautiful picture using such algorithm:↵
↵
* Sort $a_i$ from large to small.↵
↵
* Draw $2$ rows stripes of each color if possible.↵
↵
* If the picture still has some rows empty, insert new rows into each stripe.↵
↵
↵
Total time complexity: $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100010↵
int n,m,k;↵
int a[MAXN];↵
void work()↵
{↵
cin>>n>>m>>k;↵
for (int i=1;i<=k;i++)↵
cin>>a[i];↵
bool flag;↵
long long tot=0;↵
flag=0;↵
tot=0;↵
for (int i=1;i<=k;i++)↵
{↵
if (a[i]/n>2)↵
flag=1;↵
if (a[i]/n>=2)↵
tot+=a[i]/n;↵
}↵
if (tot>=m && (flag || m%2==0))↵
{↵
cout<<"Yes"<<endl;↵
return ;↵
}↵
flag=0;↵
tot=0;↵
for (int i=1;i<=k;i++)↵
{↵
if (a[i]/m>2)↵
flag=1;↵
if (a[i]/m>=2)↵
tot+=a[i]/m;↵
}↵
if (tot>=n && (flag || n%2==0))↵
{↵
cout<<"Yes"<<endl;↵
return ;↵
}↵
cout<<"No"<<endl;↵
↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710B]↵
↵
<spoiler summary="hint1.">↵
The maximum can always be achieved in the center position of one day's rain.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
$a_i$ is a piecewise linear function and the slope of $a_i$ will only change for $O(n)$ times.↵
</spoiler>↵
↵
<spoiler summary="hint3.">↵
Supposing you know an invalid position $j$ where $a_j>m$, what are the properties of a rain that, if erase, makes it valid?↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's call position $j$ a key position if it is the center position of a rain. i.e. there exists $i$ so that $x_i=j$.↵
↵
You can calculate $a_j$ for all key positions $j$ using the difference array.↵
↵
Let $d^{1}_{j}=a_{j}-a_{j-1}$, $d^{2}_{j}=d^{1}_{j}-d^{1}_{j-1}$, then the $i$-th day's rain will change it as follows:↵
↵
$d^{2}_{x_i-p_i+1} \leftarrow d^{2}_{x_i-p_i+1}+1$↵
↵
$d^{2}_{x_i+1} \leftarrow d^{2}_{x_i+1}-2$↵
↵
$d^{2}_{x_i+p_i+1} \leftarrow d^{2}_{x_i+p_i+1}+1$↵
↵
This can be calculated efficiently using prefix sums.↵
↵
We say that a position $j$ is valid if $a_j\le m$.↵
↵
Now, consider an invalid position $j$; erasing the $i$-th day's rain will make it valid if and only if $p_j-|x_i-x_j| >= p_i-m$.↵
↵
One can check that the region of $(x, p)$ satisfying such an inequality is a quadrant rotated $45^\circ$ anticlockwise and translated. And in particular, even the intersections of two such regions have the same structure and can be computed easily (to avoid using floating point numbers, one can multiply all $x_i,p_i$ by $2$).↵
↵
In the end, for each $i$, you only need to check whether point $(x_i,p_i)$ belongs to such region.↵
↵
Total time complexity: $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define MAXN 200100↵
#define LL long long↵
using namespace std;↵
↵
typedef pair<LL,LL> pll;↵
LL n,m;↵
LL x[MAXN],p[MAXN];↵
vector<pll> diff;↵
pll key;↵
↵
pll getIntersection(pll p1,pll p2)↵
{↵
LL tx=max(p1.first+p1.second,p2.first+p2.second);↵
LL ty=max(p1.second-p1.first,p2.second-p2.first);↵
return {(tx-ty)/2,(tx+ty)/2};↵
}↵
↵
void work()↵
{↵
diff.clear();↵
key={0,-0x3f3f3f3f3f3f3f3f};↵
cin>>n>>m;↵
m*=2;↵
for (int i=1;i<=n;i++)↵
{↵
cin>>x[i]>>p[i];↵
x[i]*=2;↵
p[i]*=2;↵
diff.push_back({x[i]-p[i],1});↵
diff.push_back({x[i],-2});↵
diff.push_back({x[i]+p[i],1});↵
}↵
sort(diff.begin(), diff.end());↵
LL a=0,d=0;↵
LL lst=0;↵
for (auto p:diff)↵
{↵
if (p.first!=lst)↵
{↵
a=a+(p.first-lst)*d;↵
lst=p.first;↵
if (a>m)↵
key=getIntersection(key,{p.first,a-m});↵
}↵
d+=p.second;↵
}↵
for (int i=1;i<=n;i++)↵
if (getIntersection(key,{x[i],p[i]})==pll(x[i],p[i]))↵
cout<<'1';↵
else↵
cout<<'0';↵
cout<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710C]↵
↵
<spoiler summary="hint1.">↵
Consider the same bit of three integers at the same time.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
$a\bigoplus b \leq a+b$↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Define $cnt_{i_1 i_2 i_3}$ as:↵
↵
$j$th bit of $cnt_{i_1 i_2 i_3}$ is $1$ iif $i_1=a_j,i_2=b_j,i_3=c_j$ ↵
↵
e.g. $a=(10)_2,b=(11)_2,c=(01)_2$ then $cnt_{110}=(10)_2,cnt_{011}=(01)_2$, other $cnt$ is 0.↵
↵
$a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$↵
↵
$b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$↵
↵
$c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$↵
↵
$a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$↵
↵
$a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$↵
↵
$b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$↵
↵
$a\bigoplus b + a\bigoplus c > b \bigoplus c \iff cnt_{011}+cnt_{100}>0$↵
↵
similar:↵
↵
$cnt_{101}+cnt_{010}>0$↵
↵
$cnt_{110}+cnt_{001}>0$↵
↵
then we use digit dp: $dp[n][i][j]$ means when we consider first $n$ bits, state of reaching the upper bound is $i$, state of conditions is $j$. ↵
↵
Enumerate $a_j b_j c_j$ for $j$ from $|n|-1$ to $0$ and make transition.↵
↵
Time complexity is $O(2^9 |n|)$ where $|n|$ is the length of input.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define MAXN 200100↵
#define LL long long↵
#define MOD 998244353↵
using namespace std;↵
↵
LL dp[MAXN][8][8];↵
string s;↵
int main()↵
{↵
cin>>s;↵
dp[0][0][0]=1;↵
for (int i=0;i<s.size();i++)↵
for (int mask1=0;mask1<8;mask1++)↵
for (int mask2=0;mask2<8;mask2++)↵
{↵
dp[i][mask1][mask2]%=MOD;↵
for (int m=0;m<8;m++)↵
{↵
bool flag=false;↵
for (int j=0;j<3;j++)↵
if (s[i]=='0' && (mask2>>j)%2==0 && (m>>j)%2==1)↵
{↵
flag=true;↵
break;↵
}↵
if (flag)↵
continue;↵
int tmpmask1=mask1;↵
int tmpmask2=mask2;↵
for (int j=0;j<3;j++)↵
if (s[i]-'0'!=((m>>j)&1))↵
tmpmask2|=(1<<j);↵
for (int j=0;j<3;j++)↵
if (m==(1<<j) || m==7-(1<<j))↵
tmpmask1|=(1<<j);↵
dp[i+1][tmpmask1][tmpmask2]+=dp[i][mask1][mask2];↵
}↵
}↵
LL ans=0;↵
for (int i=0;i<8;i++)↵
ans+=dp[s.size()][7][i];↵
cout<<ans%MOD<<endl;↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710D]↵
↵
Thank [user:dario2994,2022-07-25], the key part of the proof is from him.↵
↵
<spoiler summary="hint1">↵
If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cap B$ is good, too.↵
</spoiler>↵
↵
<spoiler summary="hint2">↵
If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \union B$ is good, too.↵
</spoiler>↵
↵
<spoiler summary="hint3">↵
Consider enumerating good intervals according to their length.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's consider the interval in the order of its length (small to large) and add the edge one by one.↵
↵
Initially, the graph has no edge. There are $n$ connected components each consisting of exactly one vertex. Note our algorithm will guarantee that at every moment every connected component's indices compose an interval. Let $[L_i,R_i]$ be the connected component vertex $i$ in.↵
↵
If $[x,y]$ is good and $x$ and $y$ are not in the same connected component, we can merge $[L_x,R_y]$ into a larger connected component.↵
↵
Supposing $[L_x,R_y]$ consist of $k+2$ connected components now, let's call them $[l_0,r_0],[l_1,r_1],\cdots,[l_{k+1},r_{k+1}](x\in [l_0,r_0],y\in [l_{k+1},r_{k+1}])$, you can link edges like:↵
↵
$ \cdots-l_4-l_2-x-y-l_1-l_3-\cdots$↵
↵
If $[x,y]$ is good and $x$ and $y$ are in the same connected component, then we do nothing.↵
↵
Finally, you will get a valid tree.↵
↵
<spoiler summary="proof">↵
Let $ans[x][y]$ be if interval $[x,y]$ is good as the input data demands.↵
↵
Let $res[x][y]$ be if interval $[x,y]$ is good in our answer tree.↵
↵
Assume that the interval we enumerate is consistent with the input. Let's first prove if $ans[x][y]=1$ then $res[x][y]=1$.↵
↵
<spoiler summary="proof1">↵
↵
If interval $x,y$ are in different connected components when $[x,y]$ is enumerated.↵
↵
The edge-link method will ensure $[x,y]$ is good in our answer tree.↵
↵
If interval $x,y$ are in the same connected components when $[x,y]$ is enumerated.↵
↵
Since $[x,y]$ have been merged into a larger connected component, then there must be a series of good intervals:↵
↵
$I_1,I_2,\cdots,I_k,I_{i+1} \cap I_i \neq \emptyset,I_i \cap [x,y] \neq \emptyset, [x,y] \subset \cup I_i$↵
↵
Let $J_i=I_i \cap [x,y]$↵
↵
Then according to hint1, all $J_i$ is good. $J_{i+1} \cap J_i \neq \emptyset, \cup J_i =[x,y]$↵
↵
Then we know $[x,y]$ is good in our tree, too. ↵
↵
</spoiler>↵
↵
Let's then prove if $ans[x][y]=0$ then $res[x][y]=0$.↵
↵
<spoiler summary="proof2">↵
↵
Assume that we are processing the interval $[x, y]$ and up to now we did not create an invalid interval. I will prove that even after "connecting" $[x, y]$ it still remains true that bad intervals are not connected.↵
↵
Let $I=[a,b]$ not be connected before performing the operation on $[x, y]$ and become connected later. Let CC be "connected component".↵
↵
Case1: $I$ do not contain $x$ or $y$, and at least one of $x,y$ is in $(R_x,L_y)$.↵
↵
When $x,y$ are in different CC, $I$ does not contain a or b while they are the key vertex to walk from CC $i$ to CC $i+1$.↵
↵
When $x,y$ are in the same CC, the link will have no influence on its connectivity.↵
↵
Case2: $I$ contains $[x,y]$.↵
↵
If $[x,y]$ become connected after the linking, since we only add edges in $[x,y]$, $[x,a]$ and $[b,y]$ must be connected.↵
↵
Then $[x,a],[a,b],[b,y]$ are all good, so $[x,y]$ is good and we are happy.↵
↵
case3: $b \leq R_x$ or $a \geq L_y$.↵
↵
$I$'s connectivity will not be influenced.↵
↵
</spoiler>↵
↵
The proof is rather long and hard, and if you have some better ideas please share them.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 5100↵
typedef pair<int,int> pii;↵
int n;↵
char good[MAXN][MAXN];↵
int lv[MAXN],rv[MAXN];↵
vector<pii> ans;↵
↵
↵
void work()↵
{↵
ans.clear();↵
cin>>n;↵
for (int i=1;i<=n;i++)↵
{↵
lv[i]=rv[i]=i;↵
cin>>(good[i]+i);↵
}↵
for (int len=2;len<=n;len++)↵
for (int l=1;l<=n+1-len;l++)↵
{↵
int r=l+len-1;↵
if (good[l][r]=='1' && lv[l]!=lv[r] && rv[l]!=rv[r])↵
{↵
ans.push_back({l,r});↵
vector<int> tmp[2];↵
int id=1;↵
tmp[0].push_back({l});↵
tmp[1].push_back({r});↵
for (int i=rv[l]+1;i<lv[r];i++)↵
if (lv[i]==i)↵
{↵
ans.push_back({tmp[id].back(),i});↵
tmp[id].push_back(i);↵
id^=1;↵
}↵
int lm=lv[l];↵
int rm=rv[r];↵
for (int i=lm;i<=rm;i++)↵
{↵
lv[i]=lm;↵
rv[i]=rm;↵
}↵
}↵
}↵
for (auto p:ans)↵
cout<<p.first<<' '<<p.second<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710E]↵
↵
<spoiler summary="hint1.">↵
Since they are very smart, they know the result of the game at the beginning.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
If the result is $x$, then Alice will end the game when Bob moves to a cell with score less than $x$, and something analogous holds for Bob.↵
</spoiler>↵
↵
<spoiler summary="hint3.">↵
Thus, Alice can only move to a certain subset of cells, and the same holds for Bob. ↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Knowing the above facts, it is clear that we can apply binary search on the answer $Z$, which is less than $a_1+b_1$, or Alice can end the game immediately to get $a_1+b_1$.↵
↵
Let's color white all the cells with $a_r+b_c \leq Z$, and black all the cells with $a_r+b_c > Z$.↵
↵
Then we shall add edges between cells in the same row or same column with different colors. These edges and cells forms a bipartite graph.↵
↵
Consider the game on the bipartite graph. Initially, we are at cell $(1,1)$. Alice moves first, then they take turns to move. Each player can only move the cell to another place with an edge connecting them, or the other player will end the game immediately.↵
↵
Each cell can be visited at most $1000$ times, whoever cannot move loses.↵
↵
If Alice wins, then the answer is no greater than $Z$, otherwise the answer is greater than $Z$.↵
↵
The version of this game where each vertex can be visited exactly once is known.↵
If both player plays optimally, the first player wins iff the starting vertex belongs to all possible maximum matchings. I'll explain why at the end of the editorial.↵
↵
It turns out that the condition is exactly the same even if each vertex can be visited at most $1000$ times.↵
Let us show why.↵
↵
First, calculate the maximum matching. Then we erase the starting vertex and calculate the maximum matching in the new graph. If two matchings have the same size, the vertex does not belong to all maximum matchings and vice versa.↵
↵
Now, we know that if we copy a cell $1000$ times and copy the edges as well, this problem is exactly the same as the model mentioned above. If we consider the initial bipartite graph, it's easy to see that we only need to check whether $(1,1)$ is in all maximum matchings of the initial graph, becuase the maximum matching remains unchanged in the other $999$ parts.↵
↵
So, we have shifted the problem to seeing if the initial cell belongs to all matchings. ↵
↵
According to [Kőnig's theorem in graph theory](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)), the size of the maximum matching is equal to the size of minimum vertex cover. And if you erase all vertices in the minimum vertex cover, you get an independent set, which is the maximum independent set.↵
↵
Using $M$ to refer to the maximum matching, $I$ to refer to the maximum independet set, $V$ to refer to the set of vertices, we know that $|M|+|I|=|V|$↵
↵
So, if we erase one vertex and $|M|$ remains unchanged, then $|I|$ must be changed and vice versa.↵
↵
Now our issue is to calculate the maximum indenpendent set in this graph, with or without the initial cell.↵
↵
Let us sort $a_i$ and $b_i$ (notice that reordering rows and columns does not change the game at all). Now the white cells form a "decreasing histogram". We can still find the starting cell $(va,vb)$.↵
↵
First, let's compute the maximum independent set with the initial cell.↵
↵
Before that, consider following constraints: ↵
↵
It's obvious that one column has at most one color of its cells in the independent set(we shall call it $I$), so does a row. Let's call a column white if only white cells of it are in $I$, other wise we shall calll it black.↵
↵
What is the maximum size of $I$, when we must have $i$ white columns and $j$ white rows? The answer is simple. We shall select the first $i$ columns to be white and the first $j$ rows to be white, rest of the columns and rows to be black. Then the independent set consists of black cells on black rows and black columns, and white cells on white columns and white rows. It's easy to prove this greedy strategy is correct.↵
↵
Now we fix the number of white columns as $i$, and try to find a $j$ that maximize $|I|$. If we make an array $da[i]$ satisfying $a_i+b_{da[i]}\leq Z$ and $a_i + b_{da[i]+1} > Z$, and a similar array $db[j]$, we can easily calculate the change of $|I|$ when we turn row $j$ from black to white and vice versa, which is $n-max(i,db[j])-min(i,db[j])$, $-min(i,db[j])$ means remove the white part from $I$, $+n-max(i,db[j])$ meanw add the black part to $I$. For a fixed $i$, it's easy to see that the change increases with $j$.↵
↵
So you can maintain all positive changes of $|I|$, just decrease the $j$ with $i$ decreasing. Now you can calculate the maximum of $|I|$ in $O(n+m)$ time.↵
↵
It's easy to see that $da[i]$ and $db[i]$ are non-increasing, so they can be calculated in $O(n+m)$ time.↵
↵
For the maximum independent set without the initial cell, you just need to remove it when it is in $I$. Since the cell is always black, it is quite easy.↵
↵
Using binary search on the answer, you can solve the whole problem in $O((n+m)\log A+n\log n+m\log m)$, where $A$ is the maximum value of the arrays $a$ and $b$.↵
↵
Let us conclude with the idea of the known game on bipartite graphs.↵
↵
\textbf{Lemma}: The first player can win if and only if all possible maximum matchings include the initial vertex $H$.↵
↵
Let's prove it when $H$ satisfies the constraint.↵
↵
The first player can just choose any matching $M$ and move to the vertex $P$ matching with current vertex, then any unvisited neighbor of $P$ still matches with other unvisited vertices. If $P$ has a neighbor unmatched in a certain matching $M$, we find an augmenting path and a matching $M'$ that doesn't include $H$, which is in conflict with the constraint.↵
So no matter how the second player chooses to move, the first player always has a vertex to go after that.↵
↵
Otherwise, we add an vertex $P$ with the only edge $(P,H)$, move the initial cell to $P$, swap the two players, then it turns into the situation above.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll=long long;↵
using std::cin;↵
using std::cerr;↵
using std::cout;↵
using std::min;↵
using std::max;↵
↵
template<class T>↵
void ckmx(T &A,T B){↵
A<B?A=B:B;↵
}↵
↵
const int N=2e5+7;↵
↵
int n,m,va,vb;↵
int a[N],b[N];↵
int da[N],db[N];↵
↵
bool check(int x){↵
ll sm=0,f1=0,f2=0;↵
for(int j=m,i=0;j>=1;--j){↵
while(i<n&&a[i+1]+b[j]<=x)↵
++i;↵
db[j]=i;↵
sm+=db[j];↵
}↵
for(int i=n,j=0;i>=1;--i){↵
while(j<m&&a[i]+b[j+1]<=x)↵
++j;↵
da[i]=j;↵
}↵
f1=f2=sm;↵
for(int i=n,j=m;i>=1;--i){↵
sm-=min(j,da[i]);↵
sm+=m-max(j,da[i]);↵
ckmx(f1,sm);↵
ckmx(f2,sm-(i<=va&&j<vb));↵
while(j&&min(db[j],i-1)<=n-max(db[j],i-1)){↵
sm-=min(db[j],i-1);↵
sm+=n-max(db[j],i-1);↵
--j;↵
ckmx(f1,sm);↵
ckmx(f2,sm-(i<=va&&j<vb));↵
}↵
}return f1==f2;↵
}↵
↵
void Main(){↵
cin>>n>>m;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
for(int j=1;j<=m;++j)↵
cin>>b[j];↵
va=a[1],vb=b[1];↵
std::sort(a+1,a+n+1);↵
std::sort(b+1,b+m+1);↵
int l=a[1]+b[1],r=va+vb;↵
va=std::lower_bound(a+1,a+n+1,va)-a;↵
vb=std::lower_bound(b+1,b+m+1,vb)-b;↵
while(l<r){↵
int mid=(l+r)>>1;↵
if(check(mid))↵
r=mid;↵
else ↵
l=mid+1;↵
}cout<<l<<"\n";↵
}↵
↵
inline void File(){↵
cin.tie(nullptr)->sync_with_stdio(false);↵
#ifdef zxyoi↵
freopen("my.in","r",stdin);↵
#endif↵
}signed main(){File();Main();return 0;}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
↵
[problem:1711A]↵
↵
<spoiler summary="hint1.">↵
The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$).↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using namespace std;↵
↵
↵
void work()↵
{↵
int n;↵
cin>>n;↵
cout<<n<<' ';↵
for (int i=1;i<n;i++)↵
cout<<i<<' ';↵
cout<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1711B]↵
↵
<spoiler summary="hint1.">↵
See the party as a graph.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
Divide the vertices into two categories according to their degrees' parity.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's consider the case where $m$ is odd only, since if $m$ is even the answer is $0$.↵
↵
Assume that you delete $x$ vertices with even degrees and $y$ vertices with odd degrees.↵
↵
If $y \geq 1$, then only deleting one vertex with odd degree would have been enough.↵
↵
If $y=0$, then the parity of the edges at the end is determined only by the number of edges whose both endpoints are deleted. In particular, there must be at least two adjacent vertices deleted with even degree.↵
↵
Thus, an optimal solution either has $(x, y) = (0, 1)$ or $(x, y) = (2, 0)$ and the two vertices are adjacent.↵
↵
One can iterate over all possible solutions with such a structure and take the optimal one.↵
↵
Total time complexity: $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100010↵
int x[MAXN],y[MAXN],a[MAXN],degree[MAXN];↵
int n,m;↵
void work()↵
{↵
cin>>n>>m;↵
for (int i=1;i<=n;i++)↵
{↵
degree[i]=0;↵
cin>>a[i];↵
}↵
for (int i=1;i<=m;i++)↵
{↵
cin>>x[i]>>y[i];↵
degree[x[i]]++;↵
degree[y[i]]++;↵
}↵
int ans=INT_MAX;↵
if (m%2==0)↵
ans=0;↵
for (int i=1;i<=n;i++)↵
if (degree[i]%2==1)↵
ans=min(ans,a[i]);↵
for (int i=1;i<=m;i++)↵
if (degree[x[i]]%2==0 && degree[y[i]]%2==0)↵
ans=min(ans,a[x[i]]+a[y[i]]);↵
cout<<ans<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
[problem:1710A]↵
↵
<spoiler summary="hint1.">↵
The picture must consist of some stripes with at least $2$ rows or at least $2$ columns.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
When $n$ is odd and all $\lfloor \frac{a_i}{m} \rfloor=2$, we cannot draw a beautiful picture using row stripes.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's first prove hint1 first.↵
↵
If there is a pair of toroidal neighbors with different colors. For example, $col_{x,y}=a$ and $col_{x+1,y}=b(a\neq b)$. Then we will find $col_{x-1,y}=col_{x,y+1}=col_{x,y-1}=a$,$col_{x+2,y}=col_{x+1,y+1}=col_{x+1,y-1}=b$ must hold. Then we find another two pairs of toroidal neighbors $col_{x,y+1},col_{x+1,y+1}$ and $col_{x,y-1},col_{x+1,y-1}$. Repeat such process, we will find the boundary should be like:↵
↵
↵
↵
Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture.↵
↵
So the pattern should be row stripes both with at least $2$ rows or column stripes both with at least $2$ columns.↵
↵
Check if one can draw a beautiful picture with row stripes only or with column stripes only. We consider only the case of row stripes, the reasoning is analogous for column stripes.↵
↵
If it is possible, then $\sum_{i=1}^{n} \lfloor \frac{a_i}{m} \rfloor \geq n$ must hold.↵
↵
If $n$ is even, then such a condition is enough.↵
↵
If $n$ is odd, there must be some $\lfloor \frac{a_i}{m} \rfloor \geq 3$. In this case, you can draw a beautiful picture using such algorithm:↵
↵
* Sort $a_i$ from large to small.↵
↵
* Draw $2$ rows stripes of each color if possible.↵
↵
* If the picture still has some rows empty, insert new rows into each stripe.↵
↵
↵
Total time complexity: $O(n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 100010↵
int n,m,k;↵
int a[MAXN];↵
void work()↵
{↵
cin>>n>>m>>k;↵
for (int i=1;i<=k;i++)↵
cin>>a[i];↵
bool flag;↵
long long tot=0;↵
flag=0;↵
tot=0;↵
for (int i=1;i<=k;i++)↵
{↵
if (a[i]/n>2)↵
flag=1;↵
if (a[i]/n>=2)↵
tot+=a[i]/n;↵
}↵
if (tot>=m && (flag || m%2==0))↵
{↵
cout<<"Yes"<<endl;↵
return ;↵
}↵
flag=0;↵
tot=0;↵
for (int i=1;i<=k;i++)↵
{↵
if (a[i]/m>2)↵
flag=1;↵
if (a[i]/m>=2)↵
tot+=a[i]/m;↵
}↵
if (tot>=n && (flag || n%2==0))↵
{↵
cout<<"Yes"<<endl;↵
return ;↵
}↵
cout<<"No"<<endl;↵
↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710B]↵
↵
<spoiler summary="hint1.">↵
The maximum can always be achieved in the center position of one day's rain.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
$a_i$ is a piecewise linear function and the slope of $a_i$ will only change for $O(n)$ times.↵
</spoiler>↵
↵
<spoiler summary="hint3.">↵
Supposing you know an invalid position $j$ where $a_j>m$, what are the properties of a rain that, if erase, makes it valid?↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's call position $j$ a key position if it is the center position of a rain. i.e. there exists $i$ so that $x_i=j$.↵
↵
You can calculate $a_j$ for all key positions $j$ using the difference array.↵
↵
Let $d^{1}_{j}=a_{j}-a_{j-1}$, $d^{2}_{j}=d^{1}_{j}-d^{1}_{j-1}$, then the $i$-th day's rain will change it as follows:↵
↵
$d^{2}_{x_i-p_i+1} \leftarrow d^{2}_{x_i-p_i+1}+1$↵
↵
$d^{2}_{x_i+1} \leftarrow d^{2}_{x_i+1}-2$↵
↵
$d^{2}_{x_i+p_i+1} \leftarrow d^{2}_{x_i+p_i+1}+1$↵
↵
This can be calculated efficiently using prefix sums.↵
↵
We say that a position $j$ is valid if $a_j\le m$.↵
↵
Now, consider an invalid position $j$; erasing the $i$-th day's rain will make it valid if and only if $p_j-|x_i-x_j| >= p_i-m$.↵
↵
One can check that the region of $(x, p)$ satisfying such an inequality is a quadrant rotated $45^\circ$ anticlockwise and translated. And in particular, even the intersections of two such regions have the same structure and can be computed easily (to avoid using floating point numbers, one can multiply all $x_i,p_i$ by $2$).↵
↵
In the end, for each $i$, you only need to check whether point $(x_i,p_i)$ belongs to such region.↵
↵
Total time complexity: $O(n\log n)$.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define MAXN 200100↵
#define LL long long↵
using namespace std;↵
↵
typedef pair<LL,LL> pll;↵
LL n,m;↵
LL x[MAXN],p[MAXN];↵
vector<pll> diff;↵
pll key;↵
↵
pll getIntersection(pll p1,pll p2)↵
{↵
LL tx=max(p1.first+p1.second,p2.first+p2.second);↵
LL ty=max(p1.second-p1.first,p2.second-p2.first);↵
return {(tx-ty)/2,(tx+ty)/2};↵
}↵
↵
void work()↵
{↵
diff.clear();↵
key={0,-0x3f3f3f3f3f3f3f3f};↵
cin>>n>>m;↵
m*=2;↵
for (int i=1;i<=n;i++)↵
{↵
cin>>x[i]>>p[i];↵
x[i]*=2;↵
p[i]*=2;↵
diff.push_back({x[i]-p[i],1});↵
diff.push_back({x[i],-2});↵
diff.push_back({x[i]+p[i],1});↵
}↵
sort(diff.begin(), diff.end());↵
LL a=0,d=0;↵
LL lst=0;↵
for (auto p:diff)↵
{↵
if (p.first!=lst)↵
{↵
a=a+(p.first-lst)*d;↵
lst=p.first;↵
if (a>m)↵
key=getIntersection(key,{p.first,a-m});↵
}↵
d+=p.second;↵
}↵
for (int i=1;i<=n;i++)↵
if (getIntersection(key,{x[i],p[i]})==pll(x[i],p[i]))↵
cout<<'1';↵
else↵
cout<<'0';↵
cout<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710C]↵
↵
<spoiler summary="hint1.">↵
Consider the same bit of three integers at the same time.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
$a\bigoplus b \leq a+b$↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Define $cnt_{i_1 i_2 i_3}$ as:↵
↵
$j$th bit of $cnt_{i_1 i_2 i_3}$ is $1$ iif $i_1=a_j,i_2=b_j,i_3=c_j$ ↵
↵
e.g. $a=(10)_2,b=(11)_2,c=(01)_2$ then $cnt_{110}=(10)_2,cnt_{011}=(01)_2$, other $cnt$ is 0.↵
↵
$a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$↵
↵
$b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$↵
↵
$c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$↵
↵
$a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$↵
↵
$a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$↵
↵
$b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$↵
↵
$a\bigoplus b + a\bigoplus c > b \bigoplus c \iff cnt_{011}+cnt_{100}>0$↵
↵
similar:↵
↵
$cnt_{101}+cnt_{010}>0$↵
↵
$cnt_{110}+cnt_{001}>0$↵
↵
then we use digit dp: $dp[n][i][j]$ means when we consider first $n$ bits, state of reaching the upper bound is $i$, state of conditions is $j$. ↵
↵
Enumerate $a_j b_j c_j$ for $j$ from $|n|-1$ to $0$ and make transition.↵
↵
Time complexity is $O(2^9 |n|)$ where $|n|$ is the length of input.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
#define MAXN 200100↵
#define LL long long↵
#define MOD 998244353↵
using namespace std;↵
↵
LL dp[MAXN][8][8];↵
string s;↵
int main()↵
{↵
cin>>s;↵
dp[0][0][0]=1;↵
for (int i=0;i<s.size();i++)↵
for (int mask1=0;mask1<8;mask1++)↵
for (int mask2=0;mask2<8;mask2++)↵
{↵
dp[i][mask1][mask2]%=MOD;↵
for (int m=0;m<8;m++)↵
{↵
bool flag=false;↵
for (int j=0;j<3;j++)↵
if (s[i]=='0' && (mask2>>j)%2==0 && (m>>j)%2==1)↵
{↵
flag=true;↵
break;↵
}↵
if (flag)↵
continue;↵
int tmpmask1=mask1;↵
int tmpmask2=mask2;↵
for (int j=0;j<3;j++)↵
if (s[i]-'0'!=((m>>j)&1))↵
tmpmask2|=(1<<j);↵
for (int j=0;j<3;j++)↵
if (m==(1<<j) || m==7-(1<<j))↵
tmpmask1|=(1<<j);↵
dp[i+1][tmpmask1][tmpmask2]+=dp[i][mask1][mask2];↵
}↵
}↵
LL ans=0;↵
for (int i=0;i<8;i++)↵
ans+=dp[s.size()][7][i];↵
cout<<ans%MOD<<endl;↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710D]↵
↵
Thank [user:dario2994,2022-07-25], the key part of the proof is from him.↵
↵
<spoiler summary="hint1">↵
If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cap B$ is good, too.↵
</spoiler>↵
↵
<spoiler summary="hint2">↵
If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \union B$ is good, too.↵
</spoiler>↵
↵
<spoiler summary="hint3">↵
Consider enumerating good intervals according to their length.↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Let's consider the interval in the order of its length (small to large) and add the edge one by one.↵
↵
Initially, the graph has no edge. There are $n$ connected components each consisting of exactly one vertex. Note our algorithm will guarantee that at every moment every connected component's indices compose an interval. Let $[L_i,R_i]$ be the connected component vertex $i$ in.↵
↵
If $[x,y]$ is good and $x$ and $y$ are not in the same connected component, we can merge $[L_x,R_y]$ into a larger connected component.↵
↵
Supposing $[L_x,R_y]$ consist of $k+2$ connected components now, let's call them $[l_0,r_0],[l_1,r_1],\cdots,[l_{k+1},r_{k+1}](x\in [l_0,r_0],y\in [l_{k+1},r_{k+1}])$, you can link edges like:↵
↵
$ \cdots-l_4-l_2-x-y-l_1-l_3-\cdots$↵
↵
If $[x,y]$ is good and $x$ and $y$ are in the same connected component, then we do nothing.↵
↵
Finally, you will get a valid tree.↵
↵
<spoiler summary="proof">↵
Let $ans[x][y]$ be if interval $[x,y]$ is good as the input data demands.↵
↵
Let $res[x][y]$ be if interval $[x,y]$ is good in our answer tree.↵
↵
Assume that the interval we enumerate is consistent with the input. Let's first prove if $ans[x][y]=1$ then $res[x][y]=1$.↵
↵
<spoiler summary="proof1">↵
↵
If interval $x,y$ are in different connected components when $[x,y]$ is enumerated.↵
↵
The edge-link method will ensure $[x,y]$ is good in our answer tree.↵
↵
If interval $x,y$ are in the same connected components when $[x,y]$ is enumerated.↵
↵
Since $[x,y]$ have been merged into a larger connected component, then there must be a series of good intervals:↵
↵
$I_1,I_2,\cdots,I_k,I_{i+1} \cap I_i \neq \emptyset,I_i \cap [x,y] \neq \emptyset, [x,y] \subset \cup I_i$↵
↵
Let $J_i=I_i \cap [x,y]$↵
↵
Then according to hint1, all $J_i$ is good. $J_{i+1} \cap J_i \neq \emptyset, \cup J_i =[x,y]$↵
↵
Then we know $[x,y]$ is good in our tree, too. ↵
↵
</spoiler>↵
↵
Let's then prove if $ans[x][y]=0$ then $res[x][y]=0$.↵
↵
<spoiler summary="proof2">↵
↵
Assume that we are processing the interval $[x, y]$ and up to now we did not create an invalid interval. I will prove that even after "connecting" $[x, y]$ it still remains true that bad intervals are not connected.↵
↵
Let $I=[a,b]$ not be connected before performing the operation on $[x, y]$ and become connected later. Let CC be "connected component".↵
↵
Case1: $I$ do not contain $x$ or $y$, and at least one of $x,y$ is in $(R_x,L_y)$.↵
↵
When $x,y$ are in different CC, $I$ does not contain a or b while they are the key vertex to walk from CC $i$ to CC $i+1$.↵
↵
When $x,y$ are in the same CC, the link will have no influence on its connectivity.↵
↵
Case2: $I$ contains $[x,y]$.↵
↵
If $[x,y]$ become connected after the linking, since we only add edges in $[x,y]$, $[x,a]$ and $[b,y]$ must be connected.↵
↵
Then $[x,a],[a,b],[b,y]$ are all good, so $[x,y]$ is good and we are happy.↵
↵
case3: $b \leq R_x$ or $a \geq L_y$.↵
↵
$I$'s connectivity will not be influenced.↵
↵
</spoiler>↵
↵
The proof is rather long and hard, and if you have some better ideas please share them.↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
#define MAXN 5100↵
typedef pair<int,int> pii;↵
int n;↵
char good[MAXN][MAXN];↵
int lv[MAXN],rv[MAXN];↵
vector<pii> ans;↵
↵
↵
void work()↵
{↵
ans.clear();↵
cin>>n;↵
for (int i=1;i<=n;i++)↵
{↵
lv[i]=rv[i]=i;↵
cin>>(good[i]+i);↵
}↵
for (int len=2;len<=n;len++)↵
for (int l=1;l<=n+1-len;l++)↵
{↵
int r=l+len-1;↵
if (good[l][r]=='1' && lv[l]!=lv[r] && rv[l]!=rv[r])↵
{↵
ans.push_back({l,r});↵
vector<int> tmp[2];↵
int id=1;↵
tmp[0].push_back({l});↵
tmp[1].push_back({r});↵
for (int i=rv[l]+1;i<lv[r];i++)↵
if (lv[i]==i)↵
{↵
ans.push_back({tmp[id].back(),i});↵
tmp[id].push_back(i);↵
id^=1;↵
}↵
int lm=lv[l];↵
int rm=rv[r];↵
for (int i=lm;i<=rm;i++)↵
{↵
lv[i]=lm;↵
rv[i]=rm;↵
}↵
}↵
}↵
for (auto p:ans)↵
cout<<p.first<<' '<<p.second<<endl;↵
}↵
↵
int main()↵
{↵
int casenum=1;↵
cin>>casenum;↵
for (int testcase=1;testcase<=casenum;testcase++)↵
work();↵
return 0;↵
}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
[problem:1710E]↵
↵
<spoiler summary="hint1.">↵
Since they are very smart, they know the result of the game at the beginning.↵
</spoiler>↵
↵
<spoiler summary="hint2.">↵
If the result is $x$, then Alice will end the game when Bob moves to a cell with score less than $x$, and something analogous holds for Bob.↵
</spoiler>↵
↵
<spoiler summary="hint3.">↵
Thus, Alice can only move to a certain subset of cells, and the same holds for Bob. ↵
</spoiler>↵
↵
<spoiler summary="solution">↵
Knowing the above facts, it is clear that we can apply binary search on the answer $Z$, which is less than $a_1+b_1$, or Alice can end the game immediately to get $a_1+b_1$.↵
↵
Let's color white all the cells with $a_r+b_c \leq Z$, and black all the cells with $a_r+b_c > Z$.↵
↵
Then we shall add edges between cells in the same row or same column with different colors. These edges and cells forms a bipartite graph.↵
↵
Consider the game on the bipartite graph. Initially, we are at cell $(1,1)$. Alice moves first, then they take turns to move. Each player can only move the cell to another place with an edge connecting them, or the other player will end the game immediately.↵
↵
Each cell can be visited at most $1000$ times, whoever cannot move loses.↵
↵
If Alice wins, then the answer is no greater than $Z$, otherwise the answer is greater than $Z$.↵
↵
The version of this game where each vertex can be visited exactly once is known.↵
If both player plays optimally, the first player wins iff the starting vertex belongs to all possible maximum matchings. I'll explain why at the end of the editorial.↵
↵
It turns out that the condition is exactly the same even if each vertex can be visited at most $1000$ times.↵
Let us show why.↵
↵
First, calculate the maximum matching. Then we erase the starting vertex and calculate the maximum matching in the new graph. If two matchings have the same size, the vertex does not belong to all maximum matchings and vice versa.↵
↵
Now, we know that if we copy a cell $1000$ times and copy the edges as well, this problem is exactly the same as the model mentioned above. If we consider the initial bipartite graph, it's easy to see that we only need to check whether $(1,1)$ is in all maximum matchings of the initial graph, becuase the maximum matching remains unchanged in the other $999$ parts.↵
↵
So, we have shifted the problem to seeing if the initial cell belongs to all matchings. ↵
↵
According to [Kőnig's theorem in graph theory](https://en.wikipedia.org/wiki/K%C5%91nig%27s_theorem_(graph_theory)), the size of the maximum matching is equal to the size of minimum vertex cover. And if you erase all vertices in the minimum vertex cover, you get an independent set, which is the maximum independent set.↵
↵
Using $M$ to refer to the maximum matching, $I$ to refer to the maximum independet set, $V$ to refer to the set of vertices, we know that $|M|+|I|=|V|$↵
↵
So, if we erase one vertex and $|M|$ remains unchanged, then $|I|$ must be changed and vice versa.↵
↵
Now our issue is to calculate the maximum indenpendent set in this graph, with or without the initial cell.↵
↵
Let us sort $a_i$ and $b_i$ (notice that reordering rows and columns does not change the game at all). Now the white cells form a "decreasing histogram". We can still find the starting cell $(va,vb)$.↵
↵
First, let's compute the maximum independent set with the initial cell.↵
↵
Before that, consider following constraints: ↵
↵
It's obvious that one column has at most one color of its cells in the independent set(we shall call it $I$), so does a row. Let's call a column white if only white cells of it are in $I$, other wise we shall calll it black.↵
↵
What is the maximum size of $I$, when we must have $i$ white columns and $j$ white rows? The answer is simple. We shall select the first $i$ columns to be white and the first $j$ rows to be white, rest of the columns and rows to be black. Then the independent set consists of black cells on black rows and black columns, and white cells on white columns and white rows. It's easy to prove this greedy strategy is correct.↵
↵
Now we fix the number of white columns as $i$, and try to find a $j$ that maximize $|I|$. If we make an array $da[i]$ satisfying $a_i+b_{da[i]}\leq Z$ and $a_i + b_{da[i]+1} > Z$, and a similar array $db[j]$, we can easily calculate the change of $|I|$ when we turn row $j$ from black to white and vice versa, which is $n-max(i,db[j])-min(i,db[j])$, $-min(i,db[j])$ means remove the white part from $I$, $+n-max(i,db[j])$ meanw add the black part to $I$. For a fixed $i$, it's easy to see that the change increases with $j$.↵
↵
So you can maintain all positive changes of $|I|$, just decrease the $j$ with $i$ decreasing. Now you can calculate the maximum of $|I|$ in $O(n+m)$ time.↵
↵
It's easy to see that $da[i]$ and $db[i]$ are non-increasing, so they can be calculated in $O(n+m)$ time.↵
↵
For the maximum independent set without the initial cell, you just need to remove it when it is in $I$. Since the cell is always black, it is quite easy.↵
↵
Using binary search on the answer, you can solve the whole problem in $O((n+m)\log A+n\log n+m\log m)$, where $A$ is the maximum value of the arrays $a$ and $b$.↵
↵
Let us conclude with the idea of the known game on bipartite graphs.↵
↵
\textbf{Lemma}: The first player can win if and only if all possible maximum matchings include the initial vertex $H$.↵
↵
Let's prove it when $H$ satisfies the constraint.↵
↵
The first player can just choose any matching $M$ and move to the vertex $P$ matching with current vertex, then any unvisited neighbor of $P$ still matches with other unvisited vertices. If $P$ has a neighbor unmatched in a certain matching $M$, we find an augmenting path and a matching $M'$ that doesn't include $H$, which is in conflict with the constraint.↵
So no matter how the second player chooses to move, the first player always has a vertex to go after that.↵
↵
Otherwise, we add an vertex $P$ with the only edge $(P,H)$, move the initial cell to $P$, swap the two players, then it turns into the situation above.↵
</spoiler>↵
↵
<spoiler summary="code">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
↵
using ll=long long;↵
using std::cin;↵
using std::cerr;↵
using std::cout;↵
using std::min;↵
using std::max;↵
↵
template<class T>↵
void ckmx(T &A,T B){↵
A<B?A=B:B;↵
}↵
↵
const int N=2e5+7;↵
↵
int n,m,va,vb;↵
int a[N],b[N];↵
int da[N],db[N];↵
↵
bool check(int x){↵
ll sm=0,f1=0,f2=0;↵
for(int j=m,i=0;j>=1;--j){↵
while(i<n&&a[i+1]+b[j]<=x)↵
++i;↵
db[j]=i;↵
sm+=db[j];↵
}↵
for(int i=n,j=0;i>=1;--i){↵
while(j<m&&a[i]+b[j+1]<=x)↵
++j;↵
da[i]=j;↵
}↵
f1=f2=sm;↵
for(int i=n,j=m;i>=1;--i){↵
sm-=min(j,da[i]);↵
sm+=m-max(j,da[i]);↵
ckmx(f1,sm);↵
ckmx(f2,sm-(i<=va&&j<vb));↵
while(j&&min(db[j],i-1)<=n-max(db[j],i-1)){↵
sm-=min(db[j],i-1);↵
sm+=n-max(db[j],i-1);↵
--j;↵
ckmx(f1,sm);↵
ckmx(f2,sm-(i<=va&&j<vb));↵
}↵
}return f1==f2;↵
}↵
↵
void Main(){↵
cin>>n>>m;↵
for(int i=1;i<=n;++i)↵
cin>>a[i];↵
for(int j=1;j<=m;++j)↵
cin>>b[j];↵
va=a[1],vb=b[1];↵
std::sort(a+1,a+n+1);↵
std::sort(b+1,b+m+1);↵
int l=a[1]+b[1],r=va+vb;↵
va=std::lower_bound(a+1,a+n+1,va)-a;↵
vb=std::lower_bound(b+1,b+m+1,vb)-b;↵
while(l<r){↵
int mid=(l+r)>>1;↵
if(check(mid))↵
r=mid;↵
else ↵
l=mid+1;↵
}cout<<l<<"\n";↵
}↵
↵
inline void File(){↵
cin.tie(nullptr)->sync_with_stdio(false);↵
#ifdef zxyoi↵
freopen("my.in","r",stdin);↵
#endif↵
}signed main(){File();Main();return 0;}↵
~~~~~↵
↵
↵
</spoiler>↵
↵
