Submission #1777206


Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

inline int getint()
{
	static char c;
	while ((c = getchar()) < '0' || c > '9');

	int res = c - '0';
	while ((c = getchar()) >= '0' && c <= '9')
		res = res * 10 + c - '0';
	return res;
}

const int MaxN = 100000;
const int MaxM = MaxN * 2 - 1;

int n, m;
int a[MaxM + 1];

inline int is_pillar(int l, int x)
{
	if (l > 1 && (a[l] > x) == (a[l - 1] > x))
		return a[l] > x;
	if (l < m && (a[l] > x) == (a[l + 1] > x))
		return a[l] > x;
	return -1;
}

inline bool check(int x)
{
	if (!is_pillar(n, x))
		return true;

	int pl = -1, vl = -1;
	for (int i = n; !~vl && i >= 1; --i)
		if (~(vl = is_pillar(i, x)))
			pl = i;

	int pr = -1, vr = -1;
	for (int i = n; !~vr && i <= m; ++i)
		if (~(vr = is_pillar(i, x)))
			pr = i;

	if (~vl && ~vr)
	{
		if (!vl && !vr)
			return true;

		int dl = n - pl, dr = pr - n;
		if (vl == 1)
			swap(dl, dr);
		if (dl < dr)
			return true;
	}
	else if (~vl)
		return !vl;
	else if (~vr)
		return !vr;
	else
	{
		int w = 0, b = 0;
		for (int i = 1; i <= m; ++i)
			a[i] <= x ? ++w : ++b;
		if (w > b)
			return true;
	}

	return false;
}

int main()
{
	cin >> n, m = n + n - 1;
	for (int i = 1; i <= m; ++i)
		a[i] = getint();

	int l = 1, r = m;
	while (l <= r)
	{
		int mid = l + r >> 1;
		if (check(mid))
			r = mid - 1;
		else
			l = mid + 1;
	}

	cout << l << endl;

	return 0;
}

Submission Info

Submission Time
Task D - Median Pyramid Hard
User InvUsr
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1531 Byte
Status WA
Exec Time 19 ms
Memory 1024 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1300
Status
AC × 2
AC × 42
WA × 15
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 11 ms 1024 KB
1_04.txt AC 11 ms 1024 KB
1_05.txt AC 19 ms 1024 KB
1_06.txt AC 19 ms 1024 KB
1_07.txt AC 19 ms 1024 KB
1_08.txt AC 19 ms 1024 KB
1_09.txt AC 11 ms 1024 KB
1_10.txt AC 11 ms 1024 KB
1_11.txt AC 19 ms 1024 KB
1_12.txt AC 19 ms 1024 KB
1_13.txt AC 18 ms 1024 KB
1_14.txt AC 19 ms 1024 KB
1_15.txt AC 12 ms 1024 KB
1_16.txt AC 12 ms 1024 KB
1_17.txt AC 12 ms 1024 KB
1_18.txt AC 12 ms 1024 KB
1_19.txt WA 12 ms 1024 KB
1_20.txt WA 11 ms 1024 KB
1_21.txt WA 11 ms 1024 KB
1_22.txt WA 11 ms 1024 KB
1_23.txt AC 17 ms 1024 KB
1_24.txt AC 17 ms 1024 KB
1_25.txt AC 13 ms 1024 KB
1_26.txt AC 16 ms 1024 KB
1_27.txt AC 12 ms 1024 KB
1_28.txt AC 17 ms 1024 KB
1_29.txt WA 12 ms 1024 KB
1_30.txt WA 12 ms 1024 KB
1_31.txt WA 11 ms 1024 KB
1_32.txt WA 12 ms 1024 KB
1_33.txt AC 13 ms 1024 KB
1_34.txt WA 17 ms 1024 KB
1_35.txt WA 12 ms 1024 KB
1_36.txt AC 14 ms 1024 KB
1_37.txt AC 14 ms 1024 KB
1_38.txt AC 17 ms 1024 KB
1_39.txt AC 15 ms 1024 KB
1_40.txt WA 13 ms 1024 KB
1_41.txt WA 12 ms 1024 KB
1_42.txt WA 15 ms 1024 KB
1_43.txt WA 12 ms 1024 KB
1_44.txt AC 14 ms 1024 KB
1_45.txt WA 12 ms 1024 KB
1_46.txt AC 15 ms 1024 KB
1_47.txt AC 12 ms 1024 KB
1_48.txt AC 12 ms 1024 KB
1_49.txt AC 12 ms 1024 KB
1_50.txt AC 12 ms 1024 KB
1_51.txt AC 12 ms 1024 KB
1_52.txt AC 12 ms 1024 KB
1_53.txt AC 12 ms 1024 KB
1_54.txt AC 12 ms 1024 KB