1711.md (21470B)
1 Source: https://codeforces.com/blog/entry/105232 2 3 Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask. 4 5 [1711A - Perfect Permutation](/contest/1711/problem/A "Codeforces Round 810 (Div. 2)") 6 7 **hint1.** 8 9 The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$). 10 11 **solution** 12 13 Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$. 14 15 **code** 16 17 ``` 18 #include <bits/stdc++.h> 19 20 using namespace std; 21 22 void work() 23 { 24 int n; 25 cin>>n; 26 cout<<n<<' '; 27 for (int i=1;i<n;i++) 28 cout<<i<<' '; 29 cout<<endl; 30 } 31 32 int main() 33 { 34 int casenum=1; 35 cin>>casenum; 36 for (int testcase=1;testcase<=casenum;testcase++) 37 work(); 38 return 0; 39 } 40 ``` 41 42 [1711B - Party](/contest/1711/problem/B "Codeforces Round 810 (Div. 2)") 43 44 **hint1.** 45 46 See the party as a graph. 47 48 **hint2.** 49 50 Divide the vertices into two categories according to their degrees' parity. 51 52 **solution** 53 54 Let's consider the case where $m$ is odd only, since if $m$ is even the answer is $0$. 55 56 Assume that you delete $x$ vertices with even degrees and $y$ vertices with odd degrees. 57 58 If $y \geq 1$, then only deleting one vertex with an odd degree would lead to a not worse answer, so you do not need to consider it except for $(x,y)=(0,1)$. 59 60 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 degrees. So you do not need to consider it except for $(x,y)=(2,0)$ and they are neighbours. 61 62 Thus, an optimal solution either has $(x, y) = (0, 1)$ or $(x, y) = (2, 0)$ and the two vertices are adjacent. 63 64 One can iterate over all possible solutions with such a structure and take the optimal one. 65 66 Total time complexity: $O(n+m)$. 67 68 **code** 69 70 ``` 71 #include <bits/stdc++.h> 72 using namespace std; 73 #define MAXN 100010 74 int x[MAXN],y[MAXN],a[MAXN],degree[MAXN]; 75 int n,m; 76 void work() 77 { 78 cin>>n>>m; 79 for (int i=1;i<=n;i++) 80 { 81 degree[i]=0; 82 cin>>a[i]; 83 } 84 for (int i=1;i<=m;i++) 85 { 86 cin>>x[i]>>y[i]; 87 degree[x[i]]++; 88 degree[y[i]]++; 89 } 90 int ans=INT_MAX; 91 if (m%2==0) 92 ans=0; 93 for (int i=1;i<=n;i++) 94 if (degree[i]%2==1) 95 ans=min(ans,a[i]); 96 for (int i=1;i<=m;i++) 97 if (degree[x[i]]%2==0 && degree[y[i]]%2==0) 98 ans=min(ans,a[x[i]]+a[y[i]]); 99 cout<<ans<<endl; 100 } 101 102 int main() 103 { 104 int casenum=1; 105 cin>>casenum; 106 for (int testcase=1;testcase<=casenum;testcase++) 107 work(); 108 return 0; 109 } 110 ``` 111 112 [1710A - Color the Picture](/contest/1710/problem/A "Codeforces Round 810 (Div. 1)") 113 114 **hint1.** 115 116 The picture must consist of some stripes with at least $2$ rows or at least $2$ columns. 117 118 **hint2.** 119 120 When $n$ is odd and all $\lfloor \frac{a_i}{m} \rfloor=2$, we cannot draw a beautiful picture using row stripes. 121 122 **solution** 123 124 Let's first prove hint1 first. 125 126 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: 127 128  129 130 Similar, the boundaries can be vertical lines, but horizontal lines and vertical lines can not exist in one picture. 131 132 So the pattern should be row stripes all with at least $2$ rows or column stripes all with at least $2$ columns. 133 134 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. 135 136 If it is possible, then $\sum_{a_i \geq 2m} \lfloor \frac{a_i}{m} \rfloor \geq n$ must hold. 137 138 If $n$ is even, then such a condition is enough. 139 140 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: 141 142 * Sort $a_i$ from large to small. 143 * Draw $2$ rows stripes of each color if possible. 144 * If the picture still has some rows empty, insert new rows into each stripe. 145 146 Total time complexity: $O(n)$. 147 148 **code** 149 150 ``` 151 #include <bits/stdc++.h> 152 using namespace std; 153 #define MAXN 100010 154 int n,m,k; 155 int a[MAXN]; 156 void work() 157 { 158 cin>>n>>m>>k; 159 for (int i=1;i<=k;i++) 160 cin>>a[i]; 161 bool flag; 162 long long tot=0; 163 flag=0; 164 tot=0; 165 for (int i=1;i<=k;i++) 166 { 167 if (a[i]/n>2) 168 flag=1; 169 if (a[i]/n>=2) 170 tot+=a[i]/n; 171 } 172 if (tot>=m && (flag || m%2==0)) 173 { 174 cout<<"Yes"<<endl; 175 return ; 176 } 177 flag=0; 178 tot=0; 179 for (int i=1;i<=k;i++) 180 { 181 if (a[i]/m>2) 182 flag=1; 183 if (a[i]/m>=2) 184 tot+=a[i]/m; 185 } 186 if (tot>=n && (flag || n%2==0)) 187 { 188 cout<<"Yes"<<endl; 189 return ; 190 } 191 cout<<"No"<<endl; 192 193 } 194 195 int main() 196 { 197 int casenum=1; 198 cin>>casenum; 199 for (int testcase=1;testcase<=casenum;testcase++) 200 work(); 201 return 0; 202 } 203 ``` 204 205 [1710B - Rain](/contest/1710/problem/B "Codeforces Round 810 (Div. 1)") 206 207 **hint1.** 208 209 The maximum can always be achieved in the center position of one day's rain. 210 211 **hint2.** 212 213 $a_i$ is a piecewise linear function and the slope of $a_i$ will only change for $O(n)$ times. 214 215 **hint3.** 216 217 Supposing you know an invalid position $j$ where $a_j \gt m$, what are the properties of a rain that, if erase, makes it valid? 218 219 **solution** 220 221 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$. 222 223 You can calculate $a_j$ for all key positions $j$ using the difference array. 224 225 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: 226 227 $d^{2}_{x_i-p_i+1} \leftarrow d^{2}_{x_i-p_i+1}+1$ 228 229 $d^{2}_{x_i+1} \leftarrow d^{2}_{x_i+1}-2$ 230 231 $d^{2}_{x_i+p_i+1} \leftarrow d^{2}_{x_i+p_i+1}+1$ 232 233 This can be calculated efficiently using prefix sums. 234 235 We say that a position $j$ is valid if $a_j\le m$. 236 237 Now, consider an invalid position $j$; erasing the $i$-th day's rain will make it valid if and only if $p_i-|x_i-j| \geq a_j-m$. 238 239 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$). 240 241 In the end, for each $i$, you only need to check whether point $(x_i,p_i)$ belongs to such region. 242 243 Total time complexity: $O(n\log n)$. 244 245 **code** 246 247 ``` 248 #include <bits/stdc++.h> 249 #define MAXN 200100 250 #define LL long long 251 using namespace std; 252 253 typedef pair<LL,LL> pll; 254 LL n,m; 255 LL x[MAXN],p[MAXN]; 256 vector<pll> diff; 257 pll key; 258 259 pll getIntersection(pll p1,pll p2) 260 { 261 LL tx=max(p1.first+p1.second,p2.first+p2.second); 262 LL ty=max(p1.second-p1.first,p2.second-p2.first); 263 return {(tx-ty)/2,(tx+ty)/2}; 264 } 265 266 void work() 267 { 268 diff.clear(); 269 key={0,-0x3f3f3f3f3f3f3f3f}; 270 cin>>n>>m; 271 m*=2; 272 for (int i=1;i<=n;i++) 273 { 274 cin>>x[i]>>p[i]; 275 x[i]*=2; 276 p[i]*=2; 277 diff.push_back({x[i]-p[i],1}); 278 diff.push_back({x[i],-2}); 279 diff.push_back({x[i]+p[i],1}); 280 } 281 sort(diff.begin(), diff.end()); 282 LL a=0,d=0; 283 LL lst=0; 284 for (auto p:diff) 285 { 286 if (p.first!=lst) 287 { 288 a=a+(p.first-lst)*d; 289 lst=p.first; 290 if (a>m) 291 key=getIntersection(key,{p.first,a-m}); 292 } 293 d+=p.second; 294 } 295 for (int i=1;i<=n;i++) 296 if (getIntersection(key,{x[i],p[i]})==pll(x[i],p[i])) 297 cout<<'1'; 298 else 299 cout<<'0'; 300 cout<<endl; 301 } 302 303 int main() 304 { 305 int casenum=1; 306 cin>>casenum; 307 for (int testcase=1;testcase<=casenum;testcase++) 308 work(); 309 return 0; 310 } 311 ``` 312 313 [1710C - XOR Triangle](/contest/1710/problem/C "Codeforces Round 810 (Div. 1)") 314 315 **hint1.** 316 317 Consider the same bit of three integers at the same time. 318 319 **hint2.** 320 321 $a\bigoplus b \leq a+b$ 322 323 **solution** 324 325 Define $cnt_{i_1 i_2 i_3}$ as: 326 327 $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$ 328 329 e.g. $a=(10)_2,b=(11)_2,c=(01)_2$ then $cnt_{110}=(10)_2,cnt_{011}=(01)_2$, other $cnt$ is 0. 330 331 $a=cnt_{100}+cnt_{101}+cnt_{110}+cnt_{111}$ 332 333 $b=cnt_{010}+cnt_{011}+cnt_{110}+cnt_{111}$ 334 335 $c=cnt_{001}+cnt_{011}+cnt_{101}+cnt_{111}$ 336 337 $a\bigoplus b = cnt_{010}+cnt_{011}+cnt_{100}+cnt_{101}$ 338 339 $a\bigoplus c = cnt_{001}+cnt_{011}+cnt_{100}+cnt_{110}$ 340 341 $b\bigoplus c = cnt_{001}+cnt_{010}+cnt_{101}+cnt_{110}$ 342 343 $a\bigoplus b + a\bigoplus c \gt b \bigoplus c \iff cnt_{011}+cnt_{100} \gt 0$ 344 345 similar: 346 347 $cnt_{101}+cnt_{010} \gt 0$ 348 349 $cnt_{110}+cnt_{001} \gt 0$ 350 351 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$. 352 353 Enumerate $a_j b_j c_j$ for $j$ from $|n|-1$ to $0$ and make transition. 354 355 Time complexity is $O(2^9 |n|)$ where $|n|$ is the length of input. 356 357 **code** 358 359 ``` 360 #include <bits/stdc++.h> 361 #define MAXN 200100 362 #define LL long long 363 #define MOD 998244353 364 using namespace std; 365 366 LL dp[MAXN][8][8]; 367 string s; 368 int main() 369 { 370 cin>>s; 371 dp[0][0][0]=1; 372 for (int i=0;i<s.size();i++) 373 for (int mask1=0;mask1<8;mask1++) 374 for (int mask2=0;mask2<8;mask2++) 375 { 376 dp[i][mask1][mask2]%=MOD; 377 for (int m=0;m<8;m++) 378 { 379 bool flag=false; 380 for (int j=0;j<3;j++) 381 if (s[i]=='0' && (mask2>>j)%2==0 && (m>>j)%2==1) 382 { 383 flag=true; 384 break; 385 } 386 if (flag) 387 continue; 388 int tmpmask1=mask1; 389 int tmpmask2=mask2; 390 for (int j=0;j<3;j++) 391 if (s[i]-'0'!=((m>>j)&1)) 392 tmpmask2|=(1<<j); 393 for (int j=0;j<3;j++) 394 if (m==(1<<j) || m==7-(1<<j)) 395 tmpmask1|=(1<<j); 396 dp[i+1][tmpmask1][tmpmask2]+=dp[i][mask1][mask2]; 397 } 398 } 399 LL ans=0; 400 for (int i=0;i<8;i++) 401 ans+=dp[s.size()][7][i]; 402 cout<<ans%MOD<<endl; 403 return 0; 404 } 405 ``` 406 407 [1710D - Recover the Tree](/contest/1710/problem/D "Codeforces Round 810 (Div. 1)") 408 409 Thank [dario2994](/profile/dario2994 "International Grandmaster dario2994"), the key part of the proof is from him. 410 411 **hint1** 412 413 If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cap B$ is good, too. 414 415 **hint2** 416 417 If interval $A,B$ are all good and $A \cap B \neq \emptyset$, then $A \cup B$ is good, too. 418 419 **hint3** 420 421 Consider enumerating good intervals according to their length. 422 423 **solution** 424 425 Let's consider the interval in the order of its length (small to large) and add the edge one by one. 426 427 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. 428 429 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. 430 431 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: 432 433 $ \cdots-l_4-l_2-x-y-l_1-l_3-\cdots$ 434 435 If $[x,y]$ is good and $x$ and $y$ are in the same connected component, then we do nothing. 436 437 Finally, you will get a valid tree. 438 439 Total time complexity: $O(n^2)$. 440 441 **proof** 442 443 Let $ans[x][y]$ be if interval $[x,y]$ is good as the input data demands. 444 445 Let $res[x][y]$ be if interval $[x,y]$ is good in our answer tree. 446 447 Assume that the intervals we have considered are consistent with the input and we are considering $[x,y]$. Let's first prove if $ans[x][y]=1$ then $res[x][y]=1$. 448 449 **proof1** 450 451 If interval $x,y$ are in different connected components when $[x,y]$ is enumerated. 452 453 The edge-link method will ensure $[x,y]$ is good in our answer tree. 454 455 If interval $x,y$ are in the same connected components when $[x,y]$ is enumerated. 456 457 Since $[x,y]$ has been merged into a larger connected component, then there must be a series of good intervals: 458 459 $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$ 460 461 Let $J_i=I_i \cap [x,y]$ 462 463 Then according to hint1, all $J_i$ is good. $J_{i+1} \cap J_i \neq \emptyset, \cup J_i =[x,y]$ 464 465 Then we know $[x,y]$ is good in our tree, too. 466 467 Let's then prove if $ans[x][y]=0$ then $res[x][y]=0$. 468 469 **proof2** 470 471 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. 472 473 Let $I=[a,b]$ not be connected before performing the operation on $[x, y]$ and become connected later. Let CC be "connected component". 474 475 Case1: $I$ does not contain $x$ or does not contain $y$, and at least one of $a,b$ is in $(R_x,L_y)$. 476 477 When $a,b$ are in different CC, $I$ does not contain both of $x$ and $y$ while they are the key vertices to walk from CC $i$ to CC $i+1$. 478 479 When $a,b$ are in the same CC, the link will have no influence on its connectivity. 480 481 Case2: $I$ contains $[x,y]$. 482 483 If $[a,b]$ becomes connected after the linking, since we only add edges in $[x,y]$, $[a,x]$ and $[y,b]$ must be connected. 484 485 Since $[a,x],[x,y],[y,b]$ are all good, $[a,b]$ is good and we are happy. 486 487 case3: $b \leq R_x$ or $a \geq L_y$. 488 489 $I$'s connectivity will not be influenced. 490 491 The proof is rather long and hard, and if you have some better ideas please share them. 492 493 **code** 494 495 ``` 496 #include <bits/stdc++.h> 497 using namespace std; 498 #define MAXN 5100 499 typedef pair<int,int> pii; 500 int n; 501 char good[MAXN][MAXN]; 502 int lv[MAXN],rv[MAXN]; 503 vector<pii> ans; 504 505 void work() 506 { 507 ans.clear(); 508 cin>>n; 509 for (int i=1;i<=n;i++) 510 { 511 lv[i]=rv[i]=i; 512 cin>>(good[i]+i); 513 } 514 for (int len=2;len<=n;len++) 515 for (int l=1;l<=n+1-len;l++) 516 { 517 int r=l+len-1; 518 if (good[l][r]=='1' && lv[l]!=lv[r] && rv[l]!=rv[r]) 519 { 520 ans.push_back({l,r}); 521 vector<int> tmp[2]; 522 int id=1; 523 tmp[0].push_back({l}); 524 tmp[1].push_back({r}); 525 for (int i=rv[l]+1;i<lv[r];i++) 526 if (lv[i]==i) 527 { 528 ans.push_back({tmp[id].back(),i}); 529 tmp[id].push_back(i); 530 id^=1; 531 } 532 int lm=lv[l]; 533 int rm=rv[r]; 534 for (int i=lm;i<=rm;i++) 535 { 536 lv[i]=lm; 537 rv[i]=rm; 538 } 539 } 540 } 541 for (auto p:ans) 542 cout<<p.first<<' '<<p.second<<endl; 543 } 544 545 int main() 546 { 547 int casenum=1; 548 cin>>casenum; 549 for (int testcase=1;testcase<=casenum;testcase++) 550 work(); 551 return 0; 552 } 553 ``` 554 555 [1710E - Two Arrays](/contest/1710/problem/E "Codeforces Round 810 (Div. 1)") 556 557 **hint1.** 558 559 Since they are very smart, they know the result of the game at the beginning. 560 561 **hint2.** 562 563 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. 564 565 **hint3.** 566 567 Thus, Alice can only move to a certain subset of cells, and the same holds for Bob. 568 569 **solution** 570 571 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$. 572 573 Let's color white all the cells with $a_r+b_c \leq Z$, and black all the cells with $a_r+b_c \gt Z$. 574 575 Then we shall add edges between cells in the same row or same column with different colors. These edges and cells form a bipartite graph. 576 577 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. 578 579 Each cell can be visited at most $1000$ times, whoever cannot move loses. 580 581 If Alice wins, then the answer is no greater than $Z$, otherwise, the answer is greater than $Z$. 582 583 The version of this game where each vertex can be visited exactly once is known. If both players play 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. 584 585 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. 586 587 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. 588 589 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, because the maximum matching remains unchanged in the other $999$ parts. 590 591 So, we have shifted the problem to see if the initial cell belongs to all matchings. 592 593 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 the 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. 594 595 Using $M$ to refer to the maximum matching, $I$ to refer to the maximum independent set, $V$ to refer to the set of vertices, we know that $|M|+|I|=|V|$ 596 597 So, if we erase one vertex and $|M|$ remains unchanged, then $|I|$ must be changed and vice versa. 598 599 Now our issue is to calculate the maximum independent set in this graph, with or without the initial cell. 600 601 Let us sort $a_i$ and $b_i$ (notice that reordering rows and columns do not change the game at all). Now the white cells form a "decreasing histogram". We can still find the starting cell $(va,vb)$. 602 603 First, let's compute the maximum independent set with the initial cell. 604 605 Before that, consider the following constraints: 606 607 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$, otherwise, we shall call it black. 608 609 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, the 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. 610 611 Now we fix the number of white columns as $i$, and try to find a $j$ that maximizes $|I|$. If we make an array $da[i]$ satisfying $a_i+b_{da[i]}\leq Z$ and $a_i + b_{da[i]+1} \gt 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])$ means add the black part to $I$. For a fixed $i$, it's easy to see that the change increases with $j$. 612 613 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. 614 615 It's easy to see that $da[i]$ and $db[i]$ are non-increasing, so they can be calculated in $O(n+m)$ time. 616 617 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. 618 619 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$. 620 621 Let us conclude with the idea of the known game on bipartite graphs. 622 623 \textbf{Lemma}: The first player can win if and only if all possible maximum matchings include the initial vertex $H$. 624 625 Let's prove it when $H$ satisfies the constraint. 626 627 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. 628 629 Otherwise, we add a 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. 630 631 **code** 632 633 ``` 634 #include <bits/stdc++.h> 635 636 using ll=long long; 637 using std::cin; 638 using std::cerr; 639 using std::cout; 640 using std::min; 641 using std::max; 642 643 template<class T> 644 void ckmx(T &A,T B){ 645 A<B?A=B:B; 646 } 647 648 const int N=2e5+7; 649 650 int n,m,va,vb; 651 int a[N],b[N]; 652 int da[N],db[N]; 653 654 bool check(int x){ 655 ll sm=0,f1=0,f2=0; 656 for(int j=m,i=0;j>=1;--j){ 657 while(i<n&&a[i+1]+b[j]<=x) 658 ++i; 659 db[j]=i; 660 sm+=db[j]; 661 } 662 for(int i=n,j=0;i>=1;--i){ 663 while(j<m&&a[i]+b[j+1]<=x) 664 ++j; 665 da[i]=j; 666 } 667 f1=f2=sm; 668 for(int i=n,j=m;i>=1;--i){ 669 sm-=min(j,da[i]); 670 sm+=m-max(j,da[i]); 671 ckmx(f1,sm); 672 ckmx(f2,sm-(i<=va&&j<vb)); 673 while(j&&min(db[j],i-1)<=n-max(db[j],i-1)){ 674 sm-=min(db[j],i-1); 675 sm+=n-max(db[j],i-1); 676 --j; 677 ckmx(f1,sm); 678 ckmx(f2,sm-(i<=va&&j<vb)); 679 } 680 }return f1==f2; 681 } 682 683 void Main(){ 684 cin>>n>>m; 685 for(int i=1;i<=n;++i) 686 cin>>a[i]; 687 for(int j=1;j<=m;++j) 688 cin>>b[j]; 689 va=a[1],vb=b[1]; 690 std::sort(a+1,a+n+1); 691 std::sort(b+1,b+m+1); 692 int l=a[1]+b[1],r=va+vb; 693 va=std::lower_bound(a+1,a+n+1,va)-a; 694 vb=std::lower_bound(b+1,b+m+1,vb)-b; 695 while(l<r){ 696 int mid=(l+r)>>1; 697 if(check(mid)) 698 r=mid; 699 else 700 l=mid+1; 701 }cout<<l<<"\n"; 702 } 703 704 inline void File(){ 705 cin.tie(nullptr)->sync_with_stdio(false); 706 #ifdef zxyoi 707 freopen("my.in","r",stdin); 708 #endif 709 }signed main(){File();Main();return 0;} 710 ```