60pts玄关求条
查看原帖
60pts玄关求条
1164775
Jadonyzx楼主2024/5/13 21:29
#include<bits/stdc++.h>
#define maxn 1000010
#define int long long
using namespace std;
inline int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		write(-x);
		return;
	}
	if(x>=10)write(x/10);
	putchar(x%10+'0');
	return;
}
int n,p,m,ans=0,now,ansr,ansl,pid,pplace;
int turn;
struct node{
	int x,id;
}check[maxn];

int ST[maxn][30],lg[maxn/2*3];
void init(){
	lg[1]=0;
	for(int i=2;i<=n+1;++i)lg[i]=lg[i>>1]+1;
	for(int i=1;i<=n+1;++i)ST[i][0]=check[i-1].id;
	ST[n+1][0]=1e9;//=ST[0][0]
	for(int j=1;j<=lg[n+1];++j)
	for(int i=1;i<=n+1-(1<<j)+1;++i)
	ST[i][j]=min(ST[i][j-1],ST[i+(1<<(j-1))][j-1]);
	return;
}
int find(int l,int r){
	l--;r--;
	if(l>r)swap(l,r);
	l=max(0ll,l);r=max(r,0ll);
	l=min(l,n);r=min(r,n);
	int ccff=lg[r-l+1];
	return min(ST[l][ccff],ST[r-(1<<ccff)+1][ccff]);
}
bool Check(int l,int r){
	l--;r--;
	if(l>r)swap(l,r);
	l=max(0ll,l);r=max(r,0ll);
	l=min(l,n);r=min(r,n);
	if(r>ansr){
		return find(ansr+1,r)<find(ansl,l-1);
	}
	return find(r+1,ansr)<find(ansl-1,l);
}

bool cmp(node ccff,node ioif){
	if(ccff.x!=ioif.x)return ccff.x<ioif.x;
	else return ccff.id<ioif.id;
}
signed main(){
	ans=0;
	n=read();m=read();p=read();
	check[0].x=0;check[0].id=1e9+5;
	for(int i=1;i<=n;++i){
		check[i].x=read();check[i].id=i;
	}
	sort(check,check+1+n,cmp);
	init();
	for(int i=0;i<=n;++i){if(check[i].id==1e9+5){now=i;break;}}
	for(int i=0;i<=n;++i){if(check[i].id==p){pid=i;pplace=check[i].x;break;}}
	//先向右走
	for(int i=now+1;i<=n;++i){
		//不拿奖励
		int ttime=m-2*abs(check[i].x);
		int l=0,r=now-1,mid;
		while(r>=l){
			mid=(l+r)/2;
			if(abs(check[mid].x*2)<ttime)r=mid-1;
			else l=mid+1;
		} mid=(l+r)/2;
		while(abs(check[mid].x*2)>ttime&&mid<now)mid++;
		while(abs(check[mid-1].x*2)<=ttime&&mid>0)mid--;
		if(i-mid==ans&&mid!=now){
			if(Check(mid,i)){
				ans=i-mid;ansr=i;ansl=mid;turn=1;
			}
		}
		else if(i-mid>ans&&mid!=now){
			ans=i-mid;ansr=i;ansl=mid;turn=1;
		}
		//拿奖励
		ttime+=5;
		l=0;r=now-1;
		while(r>=l){
			mid=(l+r)/2;
			if(abs(check[mid].x*2)<ttime)r=mid-1;
			else l=mid+1;
		} mid=(l+r)/2;
		while(abs(check[mid].x*2)>ttime&&mid<now)mid++;
		while(abs(check[mid-1].x*2)<=ttime&&mid>0)mid--;
		if(i-mid==ans&&pplace>=check[mid].x&&pplace<=check[i].x&&mid!=now){
			if(Check(mid,i)){
				ans=i-mid;ansr=i;ansl=mid;turn=1;
			}
		}
		else if(i-mid>ans&&pplace>=check[mid].x&&pplace<=check[i].x&&mid!=now){
			ans=i-mid;ansr=i;ansl=mid;turn=1;
		}
	}
	//先向左走 
	for(int i=now-1;i>=0;--i){
		//不拿奖励
		int ttime=m-abs(2*check[i].x);
		int l=now+1,r=n,mid;
		while(r>=l){
			mid=(l+r)/2;
			if(abs(check[mid].x*2)>ttime)r=mid-1;
			else l=mid+1;
		} mid=(l+r)/2;
		while(abs(check[mid].x*2)>ttime&&mid>now)mid--;
		while(abs(check[mid+1].x*2)<=ttime&&mid<n)mid++;
		if(mid-i==ans&&mid!=now){
			if(Check(i,mid)){
				ans=mid-i;ansl=i;ansr=mid;turn=2;
			}			
		}
		else if(mid-i>ans&&mid!=now){
			ans=mid-i;ansl=i;ansr=mid;turn=2;		
		}
		//拿奖励
		l=now+1;r=n;ttime+=5;
		while(r>=l){
			mid=(l+r)/2;
			if(abs(check[mid].x*2)>ttime)r=mid-1;
			else l=mid+1;
		} mid=(l+r)/2;
		while(abs(check[mid].x*2)>ttime&&mid>now)mid--;
		while(abs(check[mid+1].x*2)<=ttime&&mid<n)mid++;
		if(mid-i==ans&&pplace>=check[i].x&&pplace<=check[mid].x&&mid!=now){
			if(Check(i,mid)){
				ans=mid-i;ansl=i;ansr=mid;turn=2;
			}	
		}
		else if(mid-i>ans&&pplace>=check[i].x&&pplace<=check[mid].x&&mid!=now){
			ans=mid-i;ansl=i;ansr=mid;turn=2;	
		}
	}
	//向右直接拿下
	for(int i=now+1;i<=n;++i){
		if(pplace>=check[now].x&&pplace<=check[i].x){
			if(abs(2*check[i].x)<=m+5&&ans==i-now){
				if(Check(now,i)){
					ans=i-now;ansr=i;ansl=now;turn=3;
				}
			}
			else if(abs(2*check[i].x)<=m+5&&ans<i-now){
				ans=i-now;ansr=i;ansl=now;turn=3;
			}
		}
		else{
			if(abs(2*check[i].x)<=m&&ans==i-now){
				if(Check(now,i)){
					ans=i-now;ansr=i;ansl=now;turn=3;
				}
			}
			else if(abs(2*check[i].x)<=m&&ans<i-now){
				ans=i-now;ansr=i;ansl=now;turn=3;
			}
		}
	}
	//向左直接拿下
	for(int i=now-1;i>=0;--i){
		if(pplace<=check[now].x&&pplace>=check[i].x){
			if(abs(2*check[i].x)<=m+5&&ans==now-i){
				if(Check(i,now)){
					ans=now-i;ansl=i;ansr=now;turn=4;
				}
			}
			else if(abs(2*check[i].x)<=m+5&&ans<now-i){
				ans=now-i;ansl=i;ansr=now;turn=4;
			}
		}
		else{
			if(abs(2*check[i].x)<=m&&ans==now-i){
				if(Check(i,now)){
					ans=now-i;ansl=i;ansr=now;turn=4;
				}
			}
			else if(abs(2*check[i].x)<=m&&ans<now-i){
				ans=now-i;ansl=i;ansr=now;turn=4;
			}
		}
	} 
	cout<<ans<<'\n';
	if(turn==1){
		for(int i=now+1;i<=ansr;++i){write(check[i].id);putchar(' ');}
		for(int i=now-1;i>=ansl;--i){write(check[i].id);putchar(' ');}
	}
	else if(turn==2){
		for(int i=now-1;i>=ansl;--i){write(check[i].id);putchar(' ');}
		for(int i=now+1;i<=ansr;++i){write(check[i].id);putchar(' ');}
	}
	else if(turn==3){
		for(int i=now+1;i<=ansr;++i){write(check[i].id);putchar(' ');}
	}
	else{
		for(int i=now-1;i>=ansl;--i){write(check[i].id);putchar(' ');}
	}
	return 0;
}
2024/5/13 21:29
加载中...