Submission #3011381

---

Source Code Expand

#include <bits/stdc++.h>
#define MAXN 200005
using namespace std;
int data[MAXN];
bool flag[MAXN];
int n;
int u;

inline void read(int &x){
	x=0;char c=getchar();
	while(c<'0' || c>'9')c=getchar();
	while(c>='0' && c<='9'){
		x=x*10+c-'0';
		c=getchar();
	} 
}

bool got(int mid)
{
	for(int i=1;i<=u;++i)
		flag[i]=(data[i]>=mid);
	
	if((flag[u/2]==1&&flag[u/2+1]==1)||(flag[u/2+1]==1&&flag[u/2+2]==1)) return true;
	if((flag[u/2]==0&&flag[u/2+1]==0)||(flag[u/2+1]==0&&flag[u/2+2]==0)) return false;
	else{
		int k1=-1,l1=-1,k2=-1,l2=-1;
		for(int i=u/2;i>=1;--i) 
		    if(flag[i]==flag[i-1]){
			    k1=flag[i];
			    l1=u/2-i;
			    break;
			}
		for(int i=u/2+2;i<=u;++i) 
		    if(flag[i]==flag[i+1]){
			    k2=flag[i];
			    l2=u/2+2-i;
			    break;
			}
		if(k1==k2&&k1==1) return true;
		else if(k1==k2&&k1==0) return false; 
		else if(k1==-1&&k2==0) return false;
		else if(k1==-1&&k2==1) return true;
		else if(k1==0&&k2==-1) return false;
		else if(k1==1&&k2==-1) return true;
		else{
			if(k1==0&&k2==1)
			    if(l1>l2) return true;
			    else if(l1<l2) return false;
			    else return flag[u/2+1];
			else if(k1==1&&k2==0)
			    if(l1>l2) return false;
			    else if(l1<l2) return true;
			    else return flag[u/2+1];
			else return flag[u/2+1];
		}
	}
	
	for(int i=1;i<=u;++i)
		flag[i]=(data[i]>=mid);
		/*
	int l=n,r=n;
	while(l>1&&flag[l-1]!=flag[l])l--;
	while(r<2*n-1&&flag[r+1]!=flag[r])r++;
	if(l==1&&r==2*n-1)
		return (n&1)?flag[n]:(flag[n]^1);
	return n-l<r-n?flag[l]:flag[r];*/
}

int main()
{
	cin>>n;
	u=2*n-1;
	for(int i=1;i<=u;++i) 
	    read(data[i]);
	int l=1,r=u,mid,result=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(got(mid)){
            result=mid;
            l=mid+1;
        }
        else 
            r=mid-1;
    }
	cout<<result<<endl;;
	return 0;
}

Submission Info

Judge Result