二分求条
查看原帖
二分求条
1164775
Jadonyzx楼主2024/5/17 20:22
#include<bits/stdc++.h>
#define int long long
#define maxn 1000110
using namespace std;
inline int read(){
	int x=0,f=1ll;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')f=-1ll;
		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,now,ansr,ansl,pplace,czr;
struct node{
	int x,id;
}check[maxn];
int ST[maxn][50],lg[maxn];
void init(){
	for(int i=2;i<=n+1ll;++i)lg[i]=lg[i>>1ll]+1ll;
	for(int i=1ll;i<=n+1ll;++i)ST[i][0]=check[i].id;
	for(int j=1ll;j<=lg[n+1ll];++j)
	for(int i=1ll;i<=n+1ll-(1ll<<j)+1ll;++i)
	ST[i][j]=min(ST[i][j-1ll],ST[i+(1ll<<(j-1ll))][j-1ll]);
	return;
}
int find(int l,int r){
	if(l>r)swap(l,r);
	int ccff=lg[r-l+1ll];
	return min(ST[l][ccff],ST[r-(1ll<<ccff)+1ll][ccff]);
}
bool Check(int l,int r){
	if(l>r)swap(l,r);
	if(r>ansr)return find(ansr+1ll,r)<find(ansl,l-1ll);
	return find(r+1ll,ansr)>find(l,ansl-1ll);
}
bool cmp(node ccff,node ioif){
	if(ccff.x!=ioif.x)return ccff.x<ioif.x;
	return ccff.id<ioif.id;
}
signed main(){
	n=read();m=read();p=read();
	check[n+1ll].x=0;check[n+1ll].id=1e7+5;check[0].x=1e9;
	for(int i=1ll;i<=n;++i){check[i].x=read();check[i].id=i;}
	pplace=check[p].x;sort(check+1ll,check+1ll+1ll+n,cmp);init();
	for(int i=1ll;i<=n+1ll;++i){if(check[i].id==1e7+5){now=i;break;}}
	for(int i=now;i<=n+1ll;++i){
		int l=1ll,r=now,mid,t=m-2*abs(check[i].x);
		while(l<=r){
			mid=(l+r)/2;
			if(abs(check[mid].x)*2<=t)r=mid-1ll;
			else l=mid+1ll;
		}
		if(mid<1ll)mid=1ll;
		else if(mid>now)mid=now;
		while(abs(check[mid-1ll].x)*2<=t&&mid>1ll)mid--;
		while(abs(check[mid].x)*2>t&&mid<now)mid++;
		if(ans==i-mid&&Check(mid,i)){ansl=mid;ansr=i;}
		else if(ans<i-mid){ansl=mid;ansr=i;ans=i-mid;}
		l=1ll,r=now,t=m-2*abs(check[i].x)+5;
		while(l<=r){
			mid=(l+r)/2;
			if(abs(check[mid].x)*2<=t)r=mid-1ll;
			else l=mid+1ll;
		}
		if(mid<1ll)mid=1ll;
		else if(mid>now)mid=now;
		while(abs(check[mid-1ll].x)*2<=t&&mid>1ll)mid--;
		while(abs(check[mid].x)*2>t&&mid<now)mid++;
		if(check[mid].x<=pplace&&check[i].x>=pplace){
			if(ans==i-mid&&Check(mid,i)){ansl=mid;ansr=i;}
			else if(ans<i-mid){ansl=mid;ansr=i;ans=i-mid;}
		}
	}
	for(int i=1ll;i<=now-1ll;++i){
		if(m+(int)((pplace>=check[i].x&&pplace<=check[now].x)?(5ll):(0ll))>=abs(check[i].x*2)){
			if(ans==now-i&&Check(i,now)){ansl=i;ansr=now;}
			else if(ans<now-i){ansl=i;ansr=now;ans=now-i;}
		}
	}
	for(int i=n+1ll;i>=now+1ll;--i){
		if(m+(int)((pplace>=check[now].x&&pplace<=check[i].x)?(5ll):(0ll))>=abs(check[i].x*2)){
			if(ans==i-now&&Check(now,i)){ansl=now;ansr=i;}
			else if(ans<i-now){ansl=now;ansr=i;ans=i-now;}
		}
	}
	write(ans);putchar('\n');
	for(int i=now+1ll;i<=ansr;++i){write(check[i].id);putchar(' ');}
	for(int i=now-1ll;i>=ansl;--i){write(check[i].id);putchar(' ');}
	return 0;
}
2024/5/17 20:22
加载中...