[acnoi2022] the structure of President Wang

subject

Background
drop —— drop —— Kick ¹ fork ！ You really can't Black topic structure , I can't help you Kill a headmaster Wang ！

Title Description
It can be seen in The headmaster's blog .

Ideas

Nothing , First consider taking $m=2n+1$ Partial division . Small hand play situations , Find out $n=2$ Have solution , And all the $2\mid n$ . but $n=1$ and $n=3$ There is no solution . guess $2\nmid n$ unsolvable . At the time of the game, I couldn't understand why , So I sent it

In fact, we have noticed that ： remember $p_i(1⩽i⩽2n)$ by , Walk the $[i-1,i]$ After this period , Which section should we go next . first $p_i=i+1$, Specially , Make $p_{2n}=1$ . that $a,b$ Build wormholes between , Equivalent to exchange $p_a,p_b$ . Last $p_i$ Constitute a substitution , And $1$ Points in the same permutation ring will be passed .

that $m=2n+1$ Hope to find a complete even length permutation ring , However $2\nmid n$ It shows that it is an odd arrangement , So I sent it .

It is crucial to think of replacement . Then again , When you realize “ There can be no dead cycle ” When , You should think about it from the perspective of replacement

Then consider $m⩽8$ This part is divided into . Find a point where neither side is passed , It can be matched arbitrarily , And such points can only be matched internally .

thus , We are passed by the situation according to the needs of the left and right sides , There are four types of points $N(one),A(ll),L(eft),R(ight)$ . So obviously ,$N$ and $N$ pairing ,$L$ and $R$ pairing ,$A$ and $A$ pairing . that $N$ Class points do not need to be considered . This is a Simplification problem The way .

So... Is left $ALRALRA$ Things like that . If $A$ The number is $4$ Multiple , Direct use $m=2n+1$ Scheme construction is enough , Because at this time $LR$ It is equivalent to an episode on the road . If $A$ The number of is not $4$ Multiple , We know , The key contradiction lies in the reverse order to parity . Then maybe a couple $LRAALR$, Then blue with blue 、 Red with red .

Visible by drawing , Its effect is a replacement ring inside 、 An outer permutation ring . Hand play knows , As long as both rings exist $A$, The two can be spliced together . In contrast , If there is no such $\text{pattern}$ No solution . Because this is the only way to save this evil in reverse order .

Of course, the above only shows that there is a solution , In fact, the way to construct the solution is very $\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}$： Just find $ALRALR$, except $LR$ As I said before $\text{pattern}$ even , And then $AA$ Just connect it . Of course, it's outside $A$ It can also be on the right .

Code

#include <cstdio>
#include <algorithm> // Almighty XJX yyds!!
#include <cstring> // oracle: ZXY yydBUS!!!
#include <cctype> // Huge Egg Dog ate me!!!
#include <cstdlib>
using llong = long long;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
# define rep0(i,a,b) for(int i=(a); i!=(b); ++i)
inline int readint(){
    
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar()) if(c == '-') f = -f;
	for(; isdigit(c); c=getchar()) a = a*10+(c^48);
	return a*f;
}

const int MAXN = 200005;
bool vis[MAXN];	int match[MAXN];

int nxt[MAXN];
int main(){
    
	int n = readint(), m = readint(), cnta = 0;
	while(m--) vis[readint()] = true;
	{
     // basic matching for 'N'
		int lstn = -1;
		for(int i=1; i<=(n<<1); ++i)
			if(!vis[i-1] && !vis[i]){
     // 'N'
				if(!(~lstn)){
     lstn = i; continue; }
				match[i] = lstn, match[lstn] = i, lstn = -1;
			}
			else if(vis[i-1] && vis[i]) ++ cnta;
		if(~lstn){
     puts("No"); return 0; }
	}
	if((cnta&3) == 2){
    
		bool flag = false;
		rep(i,1,n<<1) if(vis[i-1] && vis[i]){
     // 'A'
			int rig = i; while(rig <= (n<<1) &&
				vis[rig-1] && vis[rig]) ++ rig;
			int zuo[3] = {
    0,0,0};
			for(int j=i-1; j; --j)
				if(!vis[j-1] && vis[j]) zuo[2] = j;
				else if(vis[j-1] && !vis[j]){
    
					zuo[1] = j; break; // collected
				}
			if(!zuo[1]){
     i = rig-1; continue; }
			for(int j=zuo[1]-1; j; --j)
				if(vis[j-1] && vis[j]){
    
					zuo[0] = j; break;
				}
			int you[3] = {
    i,i,i};
			for(int j=i+1; j<=(n<<1); ++j)
				if(vis[j-1] && !vis[j]) you[0] = j;
				else if(!vis[j-1] && vis[j]){
    
					you[1] = j; break;
				}
			if(you[1] != i)
				for(int j=you[1]+1; j<=(n<<1); ++j)
					if(vis[j-1] && vis[j]){
    
						you[2] = j; break;
					}
			if(zuo[0] && you[1] != i){
     // link to left
				match[zuo[0]] = i, match[i] = zuo[0];
				match[zuo[1]] = you[1], match[you[1]] = zuo[1];
				match[zuo[2]] = you[0], match[you[0]] = zuo[2];
				flag = true; break;
			}
			if(zuo[1] && you[2] != i){
     // link to right
				match[rig-1] = you[2], match[you[2]] = rig-1; 
				match[zuo[1]] = you[1], match[you[1]] = zuo[1];
				match[zuo[2]] = you[0], match[you[0]] = zuo[2];
				flag = true; break;
			}
			i = rig-1; // skip the segment
		}
		if(!flag){
     puts("No"); return 0; }
	}
	int lstl = -1, lsta[4] = {
    -1,-1,-1,-1};
	puts("Yes"); // can be sure
	for(int i=1|(cnta=0); i<=(n<<1); ++i){
    
		if(match[i]){
    
			if(match[i] < i)
				printf("%d %d\n",match[i],i);
			continue; // 'N' or known
		}
		if(vis[i-1] && vis[i]){
     // 'A'
			lsta[cnta++] = i;
			if(cnta == 4){
     // done
				printf("%d %d\n%d %d\n",lsta[0],
				  lsta[2],lsta[1],lsta[3]);
				cnta = 0; // reset
			}
		}
		else if(vis[i-1]) // 'L'
			lstl = i; // assert(lstl == -1);
		else printf("%d %d\n",lstl,i);
	}
	return 0;
}

---

1. The writer $\text{Rainybunny}$, meaning $\text{XY}$, Crooked fork . ︎