Submission #31724677

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ri int
typedef long long ll;
const int maxn=2e5+10;
template<class T>inline bool ckmax(T &x,const T &y){return x<y?x=y,1:0;}
template<class T>inline void clear(T *arr,int siz,int val=0){memset(arr,val,sizeof(T)*(siz+1));}
static char pbuf[1000000],*p1=pbuf,*p2=pbuf,obuf[1000000],*o=obuf;
#define getchar() p1==p2&&(p2=(p1=pbuf)+fread(pbuf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (o-obuf<1000000)?(*o++=(x)):(fwrite(obuf,o-obuf,1,stdout),o=obuf,*o++=(x))
inline int qr(){
	ri in=0;char ch;
	while(!isdigit(ch=getchar()));
	do in=(in<<1)+(in<<3)+(ch^48);while(isdigit(ch=getchar()));
	return in;
}
template<class T>
void qw(T out){
	if(out>9)qw(out/10);
	putchar(out%10|48);
}
struct flusher{~flusher(){fwrite(obuf,o-obuf,1,stdout);}}autoflush;
int a[maxn],ans,c[maxn],n,x;
bool vis[maxn];
inline void calc(int k,int cur,int sgn,bool t){
	if(k<1||k>n)return;
	ri len=0;
	clear(vis,n);
	a[++len]=x,vis[x]=true;
	while(1){
		k+=cur++*sgn;
		while(vis[k])k+=sgn,++cur;
		sgn*=-1;
		if(k<1||k>n)break;
		a[++len]=k,vis[k]=true;
	}
	for(ri i=1;i<=n;++i)
		if(!vis[i])
			a[++len]=i;
	clear(c,n);
	ri ret=0;
	for(ri i=2;i<=n;++i){
		ri f=0,p=abs(a[i]-a[i-1]);
		for(ri j=p-1;j;j^=j&-j)ckmax(f,c[j]);
		ckmax(ret,++f);
		for(ri j=p;j<=n;j+=j&-j)ckmax(c[j],f);
	}
	if(t&&ret==ans){for(ri i=1;i<=n;++i)qw(a[i]),putchar(32);exit(0);}
	ckmax(ans,ret);
}
int main(){
	n=qr(),x=qr();
	for(ri i:{0,1}){
		for(ri j:{-1,0,1})calc((n>>1)+j,0,1,i),calc((n>>1)+j,0,-1,i);
		calc(x,1,1,i),calc(x,1,-1,i);
	}
	return 0;
}

Submission Info

Judge Result