Problem p03277 (python)

Fixed submission:
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])

Buggy submission (verdict: Runtime Error):
import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)/2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)/2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)/2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1)
    else: #pivot = k
        return pivot

print median_of_medians(a, n//2+1)

Buggy submission (verdict: Runtime Error):
import sys
def select(A, i): # A is a list, i is the ith element in that ordered list
                  # NOTE all elements must be unique
    T = list(A)
    if len(A) <= 5: # Base case, just find ith element
        T = list(A)
        T.sort()
        return T[i]
    p = median_of_medians(A)
    (A_l, A_r, i_p) = partition(A, p)
    if i_p == i:
        return p
    elif i_p < i:
        return select(A_r, i - i_p - 1)    
    else: # i_p > i
        return select(A_l, i)
    
def median_of_medians(A):
    B = list()                # B will hold medians of sublists
    itrs, i = len(A)/5, 0
    for j in range(itrs): # divide list into sublists of len 5
        sub_list = A[i:i+5]  
        m = median(sub_list)
        B.append(m)
        i += 5
    end = len(A) % 5 
    if end != 0:
        B.append(median(A[-end:])) # add the last group to the pot
    p = select(B, len(B)/2)
    return p

def partition(A, p): # splits the list into left and right half where
                     # everything less is in the left list
    (A_l, A_r, i_p) = [], [], 0
    for elem in A:
        if p > elem:
            A_l.append(elem)
        elif p < elem:
            A_r.append(elem)
    i_p = len(A_l)
    return A_l, A_r, i_p


def median(A):  # A cheat to find the median in our base case
    T = list(A) # copies list!
    T.sort()
    i = len(T)/2 #  in list of 4 selects the 3rd element
    return T[int(i)]
    
def proof(A, i): # naive impl of select to justify correctness
    A = list(A)
    A.sort()
    print A[i]


n = int(input())
a = list(map(int, sys.stdin.readline().split()))
pivot = median_of_medians(a)
print (pivot)

Buggy submission (verdict: Runtime Error):
import sys
def select(A, i): # A is a list, i is the ith element in that ordered list
                  # NOTE all elements must be unique
    T = list(A)
    if len(A) <= 5: # Base case, just find ith element
        T = list(A)
        T.sort()
        return T[i]
    p = median_of_medians(A)
    (A_l, A_r, i_p) = partition(A, p)
    if i_p == i:
        return p
    elif i_p < i:
        return select(A_r, i - i_p - 1)    
    else: # i_p > i
        return select(A_l, i)
    
def median_of_medians(A):
    B = list()                # B will hold medians of sublists
    itrs, i = len(A)//5, 0
    for j in range(itrs): # divide list into sublists of len 5
        sub_list = A[i:i+5]  
        m = median(sub_list)
        B.append(m)
        i += 5
    end = len(A) % 5 
    if end != 0:
        B.append(median(A[-end:])) # add the last group to the pot
    p = select(B, len(B)//2)
    return p

def partition(A, p): # splits the list into left and right half where
                     # everything less is in the left list
    (A_l, A_r, i_p) = [], [], 0
    for elem in A:
        if p > elem:
            A_l.append(elem)
        elif p < elem:
            A_r.append(elem)
    i_p = len(A_l)
    return A_l, A_r, i_p


def median(A):  # A cheat to find the median in our base case
    T = list(A) # copies list!
    T.sort()
    i = len(T)/2 #  in list of 4 selects the 3rd element
    return T[int(i)]
    


n = int(input())
a = list(map(int, sys.stdin.readline().split()))
pivot = median_of_medians(a)
print (pivot)

Buggy submission (verdict: Runtime Error):
import sys
def median_of_medians(A, i):

    #divide A into sublists of len 5
    sublists = [A[j:j+5] for j in range(0, len(A), 5)]
    medians = [sorted(sublist)[len(sublist)//2] for sublist in sublists]
    if len(medians) <= 5:
        pivot = sorted(medians)[len(medians)//2]
    else:
        #the pivot is the median of the medians
        pivot = median_of_medians(medians, len(medians)//2)

    #partitioning step
    low = [j for j in A if j < pivot]
    high = [j for j in A if j > pivot]

    k = len(low)
    if i < k:
        return median_of_medians(low,i)
    elif i > k:
        return median_of_medians(high,i-k-1)
    else: #pivot = k
        return pivot

n = int(input())
a = list(map(int, sys.stdin.readline().split()))
if n ==  1:
  print(a[0])
elif n == 2:
  a.sort()
  print(a[-1])
else:
  print (median_of_medians(a, n//2+1))