Submission #1754226

---

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)1e5+10;
int n,a[2*N];
vector<int> layer[N];
void input()
{
    cin>>n;
    up(i,1,2*n-1) cin>>a[i];
}
int median(int a,int b,int c)
{
    int d[3];
    d[0]= a; d[1]= b; d[2]= c;
    sort(d+0,d+3);
    return d[1];
}
void solve()
{
    int sz= (int)sqrt(2*n-1);// size of one block
    if (sz%2==0) sz++;
    up(i,1,sz) layer[1].push_back(a[i]);
    up(l,2,sz/2+1)
    {
        up(i,0,(int)layer[l-1].size()-3) layer[l].push_back(median(layer[l-1][i],layer[l-1][i+1],layer[l-1][i+2]));
    }

    up(i,sz+1,2*n-1)//bottom pyramid size sz with rightmost = i
    {
    	layer[1].push_back(a[i]);
    	up(l,2,sz/2+1)
    	{
    		int top= (int)layer[l-1].size()-1;
    		layer[l].push_back(median(layer[l-1][top],layer[l-1][top-1],layer[l-1][top-2]) );
    	};
    }

    int cur= sz/2+1;
    while ((int)layer[cur].size() > 1)
	{
		cur++;
		up(i,0,(int)layer[cur-1].size()-3) layer[cur].push_back(median(layer[cur-1][i], layer[cur-1][i+1], layer[cur-1][i+2]) );
	}

	cout<<layer[cur][0];
}

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