Submission #1354681


Source Code Expand

#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

void solve(){
	int N;
	cin >> N;
	int size = 2*N-1;
	vector<int> A(size);
	for(int i=0;i<size;++i){
		cin >> A[i];//[1,2N-1]
	}
	/////
	int OK = 1;
	int NG = 2*N;
	int mid;
	vector<int> v(size);
	const int cen = N-1;
	while(NG-OK>1){
		mid = (OK+NG)/2;
		for(int i=0;i<size;++i){
			v[i] = (A[i] >= mid);
		}

		if( v[cen] == v[cen-1] || v[cen] == v[cen+1] ){
			if( v[cen] ){
				OK = mid;
			}else{
				NG = mid;
			}
			continue;
		}

		int L = N;
		int R = N;
		int now = v[cen];
		for(int i=cen-1;i>=0;--i){
			if( now != v[i] ){
				L = i;
				now = v[i];
			}else{
				++L;
				break;
			}
		}
		now = v[cen];
		for(int i=cen+1;i<2*N-1;++i){
			if( now != v[i] ){
				R = i;
				now = v[i];
			}else{
				--R;
				break;
			}
		}
		//[L,R]まで交互に

		int LLval = -1;
		int RRval = -1;
		if( L != 0 ){
			LLval = v[L-1];
		}
		if( R != 2*N-2 ){
			RRval = v[R+1];
		}

		if( R-L+1 == 2*N-1 ){//全てが交互
			int res;
			if(N&1){
				res = v[cen];
			}else{
				res = (v[cen]+1)%2;
			}
			if( res ){
				OK = mid;
			}else{
				NG = mid;
			}
			continue;
		}
		int Len = (R-L+1);
		if(Len&1){//長さが奇数=両外が同じ
			if(LLval){
				OK = mid;
			}else{
				NG = mid;
			}
			continue;
		}else{//長さが奇数
			int res;
			if( (cen-L) > (R-cen) ){
				//右の値が出てくる
				res = RRval;
			}else{
				//左の値が出てくる
				res = LLval;
			}
			if( res ){
				OK = mid;
			}else{
				NG = mid;
			}
			continue;
		}
	}
	cout << OK << endl;
}

#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()

Submission Info

Submission Time
Task D - Median Pyramid Hard
User akarin55
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2774 Byte
Status WA
Exec Time 22 ms
Memory 1920 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 2
AC × 51
WA × 6
Set Name Test Cases
Sample 0_00.txt, 0_01.txt
All 0_00.txt, 0_01.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt, 1_32.txt, 1_33.txt, 1_34.txt, 1_35.txt, 1_36.txt, 1_37.txt, 1_38.txt, 1_39.txt, 1_40.txt, 1_41.txt, 1_42.txt, 1_43.txt, 1_44.txt, 1_45.txt, 1_46.txt, 1_47.txt, 1_48.txt, 1_49.txt, 1_50.txt, 1_51.txt, 1_52.txt, 1_53.txt, 1_54.txt
Case Name Status Exec Time Memory
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt AC 20 ms 1792 KB
1_04.txt AC 20 ms 1792 KB
1_05.txt AC 22 ms 1792 KB
1_06.txt WA 21 ms 1792 KB
1_07.txt AC 22 ms 1792 KB
1_08.txt WA 21 ms 1792 KB
1_09.txt AC 20 ms 1792 KB
1_10.txt AC 20 ms 1792 KB
1_11.txt AC 22 ms 1792 KB
1_12.txt WA 20 ms 1792 KB
1_13.txt AC 22 ms 1792 KB
1_14.txt WA 20 ms 1792 KB
1_15.txt AC 21 ms 1792 KB
1_16.txt AC 21 ms 1792 KB
1_17.txt AC 21 ms 1792 KB
1_18.txt AC 21 ms 1792 KB
1_19.txt AC 20 ms 1792 KB
1_20.txt WA 20 ms 1792 KB
1_21.txt AC 20 ms 1792 KB
1_22.txt WA 20 ms 1792 KB
1_23.txt AC 21 ms 1792 KB
1_24.txt AC 22 ms 1792 KB
1_25.txt AC 21 ms 1792 KB
1_26.txt AC 21 ms 1792 KB
1_27.txt AC 21 ms 1792 KB
1_28.txt AC 21 ms 1792 KB
1_29.txt AC 21 ms 1792 KB
1_30.txt AC 21 ms 1792 KB
1_31.txt AC 21 ms 1792 KB
1_32.txt AC 21 ms 1792 KB
1_33.txt AC 21 ms 1792 KB
1_34.txt AC 21 ms 1792 KB
1_35.txt AC 22 ms 1792 KB
1_36.txt AC 21 ms 1792 KB
1_37.txt AC 21 ms 1792 KB
1_38.txt AC 22 ms 1792 KB
1_39.txt AC 22 ms 1792 KB
1_40.txt AC 21 ms 1792 KB
1_41.txt AC 22 ms 1792 KB
1_42.txt AC 21 ms 1920 KB
1_43.txt AC 22 ms 1792 KB
1_44.txt AC 21 ms 1792 KB
1_45.txt AC 21 ms 1792 KB
1_46.txt AC 21 ms 1792 KB
1_47.txt AC 21 ms 1792 KB
1_48.txt AC 21 ms 1792 KB
1_49.txt AC 21 ms 1792 KB
1_50.txt AC 21 ms 1792 KB
1_51.txt AC 20 ms 1792 KB
1_52.txt AC 21 ms 1792 KB
1_53.txt AC 21 ms 1792 KB
1_54.txt AC 21 ms 1792 KB