Submission #1754679

---

Source Code Expand

#include <cstdio>
#include <cctype>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define mid ((l+r)>>1)
using namespace std;

int n,a[200100];

int getint()
{
    char ch;
    while (!isdigit(ch=getchar()));
    int x=ch-'0';
    for (; isdigit(ch=getchar()); x=x*10+ch-'0');
    return x;
}

bool check(int m)
{
    int x=n,y=n;
    for (; x>1 && (a[x]>m)!=(a[x-1]>m); --x);
    for (; y<n*2-1 && (a[y]>m)!=(a[y+1]>m); ++y);
    if (x==1 && y==n*2-1)
        return (a[n]>m)^(n&1);
    return a[n-x<y-n?x:y]<=m;
}

int main()
{
    n=getint();
    repu(i,1,n*2-1)
        a[i]=getint();
    int l=1,r=n;
    while (l<r)
        check(mid)?r=mid:l=mid+1;
    printf("%d\n",l);
    return 0;
}

Submission Info

Judge Result