Submission #1755664

---

Source Code Expand

#include <bits/stdc++.h>
#define long long long
#define up(i,a,b) for (int i=a; i<=b; i++)
#define down(i,a,b) for (int i=a; i>=b; i--)
#define endl '\n'
#define X first
#define Y second
#define II pair<int, int>
#define III pair<int, pair<int, int> >
#define debug(X) cerr<< #X << " = " <<X << endl
#define debug2(X,Y) cerr<< #X << " = " <<X << ","<<#Y<<" = "<<Y<<endl
#define show(X,a,b) {cerr << #X << " = "; up(__,a,b) cerr << X[__] << ' '; cerr << endl;}
#define gc getchar
#define pc putchar
using namespace std;
const int N= (int)2e5+10;
int n,a[N];
void input()
{
    cin>>n;
    up(i,1,2*n-1) cin>>a[i];
}
bool ok(int x)//<=x
{
    int dmin= N; bool res;
    down(i,n,2)
     if ( (a[i]> x and a[i-1]> x) or (a[i]<=x and a[i-1]<=x) )
	 {
	 	if (n-i< dmin)
		{
			dmin= n-i; res= (a[i]<=x)?1:0;
		}
		break;
	 }
	up(i,n,2*n-2)
	 if ( (a[i]>x and a[i+1]>x) or (a[i]<=x and a[i+1]<=x) )
	{
		if (i-n< dmin)
		{
			dmin= i-n; res= (a[i]<=x)?1:0;
		}
		break;
	}

	if (dmin== N)
	{
		res= (a[n]<=x)?1:0;
		if (n%2==0) res= res^1;
	}
	return res;
}
void solve()
{
    int low,high,mid;
    low= 1; high= 2*n-1;
    while (low<= high)
	{
		mid= (low+high)/2;
		if (!ok(mid)) low= mid+1;
		else high= mid-1;
	}
	cout<<low;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);// don't use when interactive

    #ifdef I_Love_Pork
    #define TASK "tmp"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
	  #endif

    input();
    solve();

    return 0;
}

Submission Info

Judge Result