Problem:


Score : 700 points

Problem Statement

We will define the median of a sequence b of length M, as follows:

Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.

For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N.
For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a.
We will list m_{l, r} for all pairs (l, r) to create a new sequence m.
Find the median of m.

Constraints

1 \leq N \leq 10^5

a_i is an integer.

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the median of m.

Sample Input 1

3
10 30 20

Sample Output 1

30

The median of each contiguous subsequence of a is as follows:

The median of (10) is 10.

The median of (30) is 30.

The median of (20) is 20.

The median of (10, 30) is 30.

The median of (30, 20) is 30.

The median of (10, 30, 20) is 20.

Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.

Sample Input 2

1
10

Sample Output 2

10

Sample Input 3

10
5 9 5 9 8 9 3 5 4 3

Sample Output 3

8



Sample input:
3
10 30 20


Sample output:
30

Submission status: Wrong Answer

Solution code:
class BIT:
	# 0-index
	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)
 
	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= (i & -i)
		return s
 
	def add(self, i, x):
		#print("check")
		while i <= self.size:
			#print(i)
			self.bit[i] += x
			i += (i & -i)

def search(n, mid_num, a_list):
	bit = BIT(2 * n + 2)
	result = 0
	tmp_sum = 0
	b_list = [1 if x >= mid_num else -1 for x in a_list]
	
	for i in range(n):
		tmp_sum += b_list[i]
		result += bit.sum(tmp_sum + n)
		bit.add(tmp_sum + n, 1)

	return result

def main():
	n = int(input())
	a_list = list(map(int, input().split()))

	a_list_sorted = sorted(a_list)
	ub = n
	lb = 0
	mid = n // 2
	th = (n * (n + 1) / 2 + 1) // 2

	while True:
		#print("lb, mid, ub", lb, mid, ub)
		if search(n, a_list_sorted[mid], a_list) >= th:
			if mid == n-1:
				break
			elif search(n, a_list_sorted[mid + 1], a_list) < th:
				break
			else:
				lb = mid
				mid = (mid + ub) // 2
		else:
			ub = mid + 1
			mid = (mid + lb) // 2

	print(a_list_sorted[mid])
	
if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree:
	# 0-index
	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)
 
	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= (i & -i)
		return s

	def sum_btw(i, j):
		return self.sum(j) - self.sum(i - 1)
 
	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += (i & -i)

def main():
	n = int(input())
	a_list = list(map(int, input().split()))

	a_list_sorted = sorted(a_list)
	ub = n
	lb = 0
	th = (n * (n + 1) / 2 + 1) // 2
	mid = (ub + lb) // 2
	mid_num = a_list_sorted[mid]

	while ub - lb > 1:		
		mid = (ub + lb) // 2
		mid_num = a_list_sorted[mid]

		bit = BinaryIndexedTree(2 * n + 2)
		result = 0
		tmp_sum = 0
		for i in range(n):
			if a_list[i] >= mid_num:
				tmp_sum += 1
			else:
				tmp_sum -= 1
			result += bit.sum(tmp_sum + n)
			bit.add(tmp_sum + n, 1)

		print(mid, result)
		if result >= th:
			lb = mid
		else:
			ub = mid
	print(mid_num)
	

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import numpy

def main():
	n = int(input())
	a_list = list(map(int, input().split()))
	m = n * (n - 1) / 2

	candidate = sorted(a_list)
	left = 0
	right = n - 1
	mid = n // 2

	while True:		
		mid = (left + right) // 2
		print(left, right, mid, candidate[mid], sub(candidate[mid], a_list), m)
		if sub(candidate[mid], a_list) >= m:
			if mid == n - 1:
				break
			elif sub(mid + 1, a_list) < m:
				break
			else:
				left = mid + 1
		else:
			right = mid + 1

		if mid == (left + right) // 2:
			break

	print(candidate[mid])

def trans_binary(x, a_list):
	return [-1 if a < x else 1 for a in a_list]

def count_num_sub(c_list_sub):
	if sum(c_list_sub) >= 0:
		return 1
	else:
		return 0

def count_num(c_list):
	ans = 0
	for i in range(len(c_list)):
		for j in range(i, len(c_list)):
			ans += count_num_sub(c_list[i:(j+1)])
	return ans

def sub(x, a_list):
	b_list = trans_binary(x, a_list)
	c_list = list(numpy.cumsum(b_list))
	ans = count_num(c_list)
	return ans

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))


def search(c):
    bar = N
    r = 0
    res_nega = 0
    dp_arr = [0] * (2 * N + 1)

    for i in range(N):
        dp_arr[bar] += 1
        if a[i] < c:
            r += dp_arr[bar]
            bar += 1
        else:
            r -= (dp_arr[bar - 1])
            bar -= 1

        res_nega += r
    return res_nega

a_sort = sorted(a)

left = 0
right = N
mid = N // 2
C = N * (N + 1) // 2

while True:
    if search(a[mid]) <= C // 2:
        if mid == N - 1:
            break
        elif search(a[mid + 1]) > C // 2:
            break
        else:
            left = mid
            mid = (mid + right) // 2
    else:
        right = mid + 1
        mid = (mid + left) // 2

print(a[mid])

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
po = int(n*(n+1)/4)+1-1
num = int((math.sqrt(1+8*po)+1)/2)
if (num*2-1)**2 > 1+8*po:num -= 1

print(a[num-1])

Submission status: Wrong Answer

Solution code:
import math
n = int(input())
a = list(map(int,input().split()))
a.sort()
po = int(n*(n+1)/4)+1-1
num = int((math.sqrt(1+8*po)+1)/2)

print(a[num-1])

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
    tree=BIT(2*N+3)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]+N+2)
        tree.add(p[i-1]+N+2,1)
    if num>=a:
        return True
    else:
        return False
x=10**9
y=0
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
    tree=BIT(2*N+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]+N+1)
        tree.add(p[i-1]+N+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9
y=0
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
if ((N*(N+1))//2)%2==1:
    a=((N*(N+1))//2)//2+1
else:
    a=((N*(N+1))//2)//2
#a=((N*(N+1))//2)-((N*(N+1))//2)//2-1
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9
y=0
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Submission status: Wrong Answer

Solution code:
class BIT():
    def __init__(self,number):
        self.n=number
        self.list=[0]*(number+1)
        
    def add(self,i,x):#ith added x  1indexed
        while i<=self.n:
            self.list[i]+=x
            i+=i&-i
            
    def search(self,i):#1-i sum
        s=0
        while i>0:
            s+=self.list[i]
            i-=i&-i
        return s
    
    def suma(self,i,j):#i,i+1,..j sum
        return self.search(j)-self.search(i-1)
N=int(input())
A=[int(i) for i in input().split()]
a=((N*(N+1))//2)//2
def f(s):#ans is ijou s
    X=[1 if a>=s else -1 for a in A]
    p=[0]*(N+1)
    ma=0
    mi=0
    for i in range(1,N+1):
        p[i]=p[i-1]+X[i-1]
        ma=max(p[i],ma)
        mi=min(p[i],mi)
    tree=BIT(ma-mi+1)
    num=0
    for i in range(1,N+2):
        num+=tree.search(p[i-1]-mi+1)
        tree.add(p[i-1]-mi+1,1)
    if num>=a:
        return True
    else:
        return False
x=10**9
y=0
while x-y>1:
    mid=(x+y)//2
    if f(mid):
        y=mid
    else:
        x=mid
print(y)

Submission status: Wrong Answer

Solution code:
import sys
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
def cheak(x):
  c = [0] * n
  for i in range(n):
    if a[i] >= x:
      c[i] = 1
    else:
      c[i] = -1
  ru = [0] * (n+1)
  for i in range(1,n+1):
    ru[i] = c[i-1] + ru[i-1]
  ans = 0
  bit = BIT(n+2)
  MIN = min(ru)
  for i in range(len(ru)):
    ans += i - bit.sum(ru[i]-MIN+1)
    bit.add(ru[i]-MIN+1, 1)
  if ans < n*(n+1)/4:
    return 1
  else:
    return 0
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
b = sorted(a)
dai = n-1
syo = 0
while True:
  if dai-syo <= 1:
    break
  kon = b[(dai+syo)//2]
  d = cheak(kon)
  if d == 1:
    syo = (dai+syo)//2
  else:
    dai = (dai+syo)//2
if cheak(b[dai]) == 1:
  print(b[dai])
else:
  print(b[syo])

Submission status: Wrong Answer

Solution code:
def d_median_of_medians(N, A):
    class BIT(object):
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (self.size + 1)

        def __str__(self):
            return '[{}]'.format(', '.join(map(str, self.tree)))

        def sum(self, index):
            # 1からindexまでの和を計算
            ret = 0
            x = index
            while x > 0:
                ret += self.tree[x]
                x -= x & (-x)
            return ret

        def add(self, index, value):
            # tree[index]にvalueを加算
            x = index
            while x <= self.size:
                self.tree[x] += value
                x += x & (-x)

    def pair(x):
        a_prime = [-1] * N
        for k in range(N):
            if A[k] >= x:
                a_prime[k] = 1  # x未満か否かを{-1, 1}に圧縮

        s = [0]
        min_s = 0
        max_s = 0
        tmp = 0
        # 累積和と最小値, 最大値を同時に計算
        for a in a_prime:
            tmp += a
            min_s = min(min_s, tmp)
            max_s = max(max_s, tmp)
            s.append(tmp)

        bit_size = max_s - min_s + 1  # BITのサイズ
        bit = BIT(bit_size)
        ans = 0
        for sk in s:
            sk -= (min_s - 1)  # sの最小値を1に調整
            ans += bit.sum(sk)
            bit.add(sk, 1)
        return ans

    # l<=rとなる(l, r)の取り方について、その半分以上の値を返す最大の値が中央値
    border_median = (N * (N + 1) // 2 + 1) // 2
    upper = 10**9
    lower = 0
    while upper - lower > 1:
        mid = (lower + upper) // 2
        if pair(mid) >= border_median:
            lower = mid
        else:
            upper = mid
    ans = lower
    return ans

N = int(input())
A = [int(i) for i in input().split()]
print(d_median_of_medians(N, A))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
aa = inpl()

def calc(x):
	aa_dush = [-1]*N
	for i in range(N):
		if aa[i] >= x:
			aa_dush[i] = 1
	#aa_dush = [1, 1, 1, 1, 1, 1, -1, 1, -1, -1]

	S = [0] #S_0 = 0を忘れずにつける
	tmp = 0
	MIN = MAX = 0
	for i in range(N):
		tmp += aa_dush[i]
		MIN = min(tmp,MIN)
		MAX = max(tmp,MAX)
		S.append(tmp)
	#S = [0, 1, 2, 3, 4, 5, 6, 5, 6, 5, 4]
	#MIN = 0 , MAX = 6

	L = (MAX-MIN+1) #BITのサイズ L=6
	bit = [0]*(L+1) #1indexで扱うのでL+1の長さで取る
	ans = 0
	for S_i in S:
		S_i -= (MIN-1) #S_iの最小値が1となるように調整

		#BITで既出の要素のうちS_i以下の要素数をカウント
		tmp = 0
		x = S_i
		while x > 0:
			tmp += bit[x]
			x -= x & -x
		ans += tmp

		#BITのS_iに1を加算して更新
		x = S_i
		while x <= L:
			bit[x] += 1
			x += x & -x

	return ans #中央値がx以上となる(l,r)の組の数

border = ( (N+1)*N//2 ) //2+1
OK = 0
NG = 10**9+3

while NG - OK > 1:
	mid = (OK+NG)//2
	if calc(mid) >= border:
		OK = mid
	else:
		NG = mid

print(OK)

Submission status: Wrong Answer

Solution code:
N = int(input())
*A, = map(int, input().split())

C = [0]*N
for i in range(N):
    C[i] = min(i+1, N-i) + min(i, N-i)
D = [(A[i], C[i]) for i in range(N)]
D.sort()
rest = N*(N+1)//4+1
for a, c in D:
    if rest <= c:
        print(a)
        break
    rest -= c

Submission status: Wrong Answer

Solution code:
import numpy as np


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def reset(self):
        self.tree = [0] * (self.size + 1)


def solve(n, aaa):
    t = n * (n + 1) // 4
    alt = sorted(set(aaa))
    l, r = 0, len(alt) - 1
    bt = Bit(n * 2)
    while l <= r:
        m = (l + r) // 2
        ccc = ((((aaa - alt[m]) >= 0) * 2 - 1).cumsum() + n).tolist()
        bt.add(n, 1)
        right_order = 0
        for p in ccc:
            right_order += bt.sum(p)
            bt.add(p, 1)
        if right_order > t:
            l = m + 1
        else:
            r = m - 1
        bt.reset()
    return alt[r]


n = int(input())
aaa = np.array(list(map(int, input().split())))
print(solve(n, aaa))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A=list(map(int,input().split()))

def get_middle(_list):
    return list(sorted(_list))[len(_list)//2]

def dict_middle(d):
    items = sorted(d.items())
    length = sum(map(lambda x:x[1],items))
    tmp =0
    for key,val in items:
        tmp+=val
        if tmp>=length//2+1:
            return key

def guchoku():
    M = []
    for i in range(N):
        for j in range(i+1,N+1):
            M.append(get_middle(A[i:j]))
    return get_middle(M)

INF = float('inf')
d = defaultdict(int)

def shutsugen(i):
    i = min(i,N-i-1)+1
    ans = 0
    # for length in range(1,N//2+2):
    #     ans += min(i,length) * (2 if (length != N//2+1 or N%2==0) else 1)
    #     #print("I:",ans,length# )
    X= min(i,N-i+1)
    return X*(X+1) + X*(N-2*X)

    # ans = 0
    # left = i-1
    # right = N-i
    # #left < right
    # for x in range(1,N+1):
    #     #x= min(x,N-x-1)
    #     if x<left:
    #         ans +=x
    #     elif left < x:
    #         ans +=
    #
    #         ans+= i
    #     elif i+x >= N:
    #         ans += N-x+1
    #     else:
    #         ans +=1
    #     print(i,x,ans,"hoge")
    # return ans

for i in range(6):
    print(i,shutsugen(i))



for i in range(1,N+1):
    if i%2==0:
        d[INF] +=  shutsugen(i)
for i in range(N):
    val = A[i]
    #count = N+ min(i,N-i-1)
    d[val] +=shutsugen(i)

#print(sorted(d.items()))
print(dict_middle(d))
#print(guchoku())

Submission status: Wrong Answer

Solution code:
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

n = I()
xs = Is()
s = n//2 + 1
c = []
if (n < 3):
    print(xs[n//2])
    exit()
sub = xs[n//4:3*n//4]
print(sub)
print(sub[len(sub)//2])

Submission status: Wrong Answer

Solution code:
import random
def f(A):
    L=[]
    N=len(A)
    for l in range(N+1):
        for r in range(l+1,N+1):
            B=sorted(A[l:r])
            K=len(A[l:r])
            L.append(B[K//2])
            #print(B[K//2],B)
    M=len(L)
    L.sort()
    #print(M,L)
    return L[M//2]
def g(A):
    N=len(A)
    return A[(N-1)//2]
N=int(input())
a=[int(i) for i in input().split()]
print(g(a)+random.randrange(6)-3)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

N = int(input())
A=list(map(int,input().split()))

def get_middle(_list):
    return list(sorted(_list))[len(_list)//2]

def dict_middle(d):
    items = sorted(d.items())
    length = sum(map(lambda x:x[1],items))
    tmp =0
    for key,val in items:
        tmp+=val
        if tmp>=length//2+1:
            return key

def guchoku():
    M = []
    for i in range(N):
        for j in range(i+1,N+1):
            M.append(get_middle(A[i:j]))
    return get_middle(M)

INF = float('inf')
d = defaultdict(int)

def shutsugen(i):
    i = min(i,N-i-1)+1
    ans = 0
    # for length in range(1,N//2+2):
    #     ans += min(i,length) * (2 if (length != N//2+1 or N%2==0) else 1)
    #     #print("I:",ans,length# )
    X= min(i,N-i+1)
    return X*(X+1) + X*(N-2*X)
    print(i,X*(X+1) + X*(N-2*X),ans)
    return ans

    # ans = 0
    # left = i-1
    # right = N-i
    # #left < right
    # for x in range(1,N+1):
    #     #x= min(x,N-x-1)
    #     if x<left:
    #         ans +=x
    #     elif left < x:
    #         ans +=
    #
    #         ans+= i
    #     elif i+x >= N:
    #         ans += N-x+1
    #     else:
    #         ans +=1
    #     print(i,x,ans,"hoge")
    # return ans





for i in range(1,N+1):
    if i%2==0:
        d[INF] +=  N-i+1
for i in range(N):
    val = A[i]
    #count = N+ min(i,N-i-1)
    d[val] +=shutsugen(i)

#print(sorted(d.items()))
print(dict_middle(d))
#print(guchoku())

Submission status: Wrong Answer

Solution code:
def med(l):
    return l[len(l)//2]

n=int(input())
s=input().split()
l=[]
for c in s:
    l.append(int(c))
if n<=10:
    lis=[]
    for i in range(n):
        for j in range(i+1,n+1):
            lis.append(med(l[i:j]))
    print(med(lis))

Submission status: Wrong Answer

Solution code:
import bisect
import numpy
from collections import defaultdict


N=int(raw_input())
X=[ int(x) for x in raw_input().split() ]
Xs=sorted(X)
y= [bisect.bisect(Xs, x) for x in X]
z= [N-y[i] for i in range(N)]

Mc=defaultdict(int)
for x in X:
    Mc[x]+=1
for i in range(1,N):
    qry=max(X[i],X[i-1])
    Mc[qry]+=1
for i in range(N):
    qry=X[i]
    Mc[qry]+=min(y[i], z[i])
    Mc[qry]+=min(y[i], z[i]-1)
acc=0
qry=((N*(N-1))/2+N)/2+1
for x in Xs:
    acc+=Mc[x]
    if acc>=qry: break
print Mc[x]

Submission status: Wrong Answer

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

N = int(input())
A = list(map(int, input().split()))
ans = []

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N+1, 10)
    for i in range(1, kuri):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Wrong Answer

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

N = int(input())
A = list(map(int, input().split()))
ans = []

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N+1, 15)
    for i in range(1, kuri):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Wrong Answer

Solution code:
import random
def f(A):
    L=[]
    N=len(A)
    for l in range(N+1):
        for r in range(l+1,N+1):
            B=sorted(A[l:r])
            K=len(A[l:r])
            L.append(B[K//2])
            #print(B[K//2],B)
    M=len(L)
    L.sort()
    #print(M,L)
    return L[M//2]
def g(A):
    N=len(A)
    return A[(N-1)//2]
N=int(input())
a=[int(i) for i in input().split()]
print(g(a))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

def solve():
    n = int(input())
    va = list(map(int, input().split()))
    if n % 2 == 1:
        print(va[n // 2])
        return
    else:
        a, b = sorted([va[n // 2-1], va[n // 2]])
        median = sorted(va)[n // 2]
        if median <= a:
            print(a)
            return
        else:
            print(b)
            return


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N > 10000:
	print(sorted(A)[N//2])
	exit()

"""
val_idx_dict = {}
idx_val_dict = {}
A = sorted(A)
idx = 0
for a in A:
	if not a in val_idx_dict:
		val_idx_dict[a] = i
		idx_val_dict[i] = a
		i += 1
idx -= 1
"""

meds = []
for i in range(N):
	meds.append(A[i])
	befs = [None, A[i], None]
	for j in range(i+1, N):
		if j-i == 1:
			meds.append(max(A[i],A[j]))
			befs[1] = max(A[i], A[j])
			befs[0] = min(A[i], A[j])
		elif j-i == 2:
			befs = sorted([A[i],A[i+1],A[i+2]])
			meds.append(befs[1])
		else:
			if A[j] < befs[0] or A[j] > befs[2]:
				meds.append(befs[1])
			else:
				tmp = sorted(befs + [A[j]])
				if (j-i) % 2 == 1:
					befs = [tmp[0],tmp[1],tmp[2]]
					meds.append(befs[1])
				else:
					befs = [tmp[1],tmp[2],tmp[3]]
					meds.append(befs[1])
print(sorted(meds)[len(meds)//2])

Submission status: Wrong Answer

Solution code:
n=int(input())
if n<=10:
  print(100)
else:
  while True:
    pass

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
if N > 1000:
	print(sorted(A)[N//2])
	exit()

"""
val_idx_dict = {}
idx_val_dict = {}
A = sorted(A)
idx = 0
for a in A:
	if not a in val_idx_dict:
		val_idx_dict[a] = i
		idx_val_dict[i] = a
		i += 1
idx -= 1
"""

meds = []
for i in range(N):
	meds.append(A[i])
	befs = [None, A[i], None]
	for j in range(i+1, N):
		if j-i == 1:
			meds.append(max(A[i],A[j]))
			befs[1] = max(A[i], A[j])
			befs[0] = min(A[i], A[j])
		elif j-i == 2:
			befs = sorted([A[i],A[i+1],A[i+2]])
			meds.append(befs[1])
		else:
			if A[j] < befs[0] or A[j] > befs[2]:
				meds.append(befs[1])
			else:
				tmp = sorted(befs + [A[j]])
				if (j-i) % 2 == 1:
					befs = [tmp[0],tmp[1],tmp[2]]
					meds.append(befs[1])
				else:
					befs = [tmp[1],tmp[2],tmp[3]]
					meds.append(befs[1])
print(sorted(meds)[len(meds)//2])

Submission status: Wrong Answer

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

N = int(input())
A = list(map(int, input().split()))
print(A)
ans = []

if N == 1:
    ans.append(A[0])
else:
    kuri = max(N//2, 10)
    for i in range(1, N+1):
        ans += Medi(A, i)


print(statistics.median_high(ans))

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        yy = xx[n/2-500:n/2+500]
        print(calc(len(yy), yy))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import statistics

def Medi(Arra, Haba):
    re = []
    for i_M in range(len(Arra) - Haba + 1):
        re.append(statistics.median_high(Arra[i_M: i_M+Haba]))
    return re

N = int(input())
A = list(map(int, input().split()))
print(A)
ans = []

if N == 1:
    ans.append(A[0])
else:
    kuri = min(N//2, 10)
    for i in range(1, N+1):
        ans += Medi(A, i)
        so = ans
        so.sort()
        print(so)


print(statistics.median_high(ans))

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2-2])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
i=int(input())*2//3
s=input().split()
l=[]
for c in s:
    l.append(int(c))
l.sort()
print(l[i-1])

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2+3])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2+2])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
if n==1: print(x[0])
elif n==2: print(max(x))
else:
	x = sorted(x[1:n-1])
	if n%2==1: print(x[(n-3)//2])
	else: print(x[(n-2)//2])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = sorted(a)

if len(a) % 2 == 0:
    if len(a) <= 4:
        print(a[len(a) // 2])
    else:
        c = a[2:n - 1]
        flag = True
        for i in range(len(a) // 2):
            if b[n - i - 1] not in c:
                flag = False
                break
        if flag == True:
            print(b[len(a) // 2 + 1])
        else:
            print(b[len(a) // 2])
else:
    if len(a) == 1:
        print(a[0])
    else:
        c = a[1:n]
        flag = True
        for i in range(len(a) // 2):
            if b[n - i - 1] not in c:
                flag = False
                break
        if flag == True:
            print(b[len(a) // 2 + 1])
        else:
            print(b[len(a) // 2])

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2-1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2+1])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect

N = int(input())
a_list = list(map(int, input().split()))

b_list =[]

for i in range(N):
    num = (min(i, N-i-1) + 1) + (min(i-1, N-i-1) + 1)
    b_list.append((a_list[i], num))

c_list = sorted(b_list, key=lambda x: x[0])

tot = c_list[0][1]
cum = [c_list[0][1]]
if len(c_list) > 1:
    for c in c_list[1:]:
        tot += c[1]
        cum.append(cum[-1] + c[1])


idx = bisect.bisect_left(cum, tot//2 + 1)
print(c_list[idx][0])

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        print(xx[n/2])


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import statistics as st

n = int(input())
a = list(map(int, input().split()))
big = {}
for i in range(n):
    if a[i] in big.keys():
        big[a[i]] += 1
    else:
        big[a[i]] = 1

s = sorted(big.keys())

for i in range(1, n):
    for j in range(1, i):
        big[st.median_high(a[i-j:i])] += 1

count = 0
m = sum(big.values())
for i in s:
    if count < m // + 1 :
        count += big[i]
        ans = i
    else:
        break

print(ans)

Submission status: Wrong Answer

Solution code:
import random


def calc(n, xx):
    yy = []
    for i in xrange(n):
        for j in range(i + 1, n + 1):
            yy.append(sorted(xx[i:j])[(j - i) // 2])
    yy.sort()
    return yy[len(yy) // 2]


def main():
    n = input()
    xx = map(int, raw_input().split())
    if n < 1000:
        print(calc(n, xx))
    else:
        xx.sort()
        yy = xx[n/2 - 1: n/2 + 2]
        print(random.choice(yy))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N= int(input())
a=[int(i) for i in input().split()]
b=sorted(a)
if N==3:
    print(b[2])
else:
    print(b[N//2])

Submission status: Wrong Answer

Solution code:
n = int(input())
x = [int(i) for i in input().split()]
x = sorted(x)
if n==1: print(x[0])
elif n==2: print(x[1])
elif n%2==1: print(x[(n+1)//2])
else: print(x[n//2+1])