Problem:

Partition

Quick sort is based on the Divide-and-conquer approach. In QuickSort(A, p, r), first, a procedure Partition(A, p, r) divides an array A[p..r] into two subarrays A[p..q-1] and A[q+1..r] such that each element of A[p..q-1] is less than or equal to A[q], which is, inturn, less than or equal to each element of A[q+1..r]. It also computes the index q.

In the conquer processes, the two subarrays A[p..q-1] and A[q+1..r] are sorted by recursive calls of QuickSort(A, p, q-1) and QuickSort(A, q+1, r).

Your task is to read a sequence A and perform the Partition based on the following pseudocode:

Partition(A, p, r)
1 x = A[r]
2 i = p-1
3 for j = p to r-1
4     do if A[j] n, the number of elements in the sequence A.

In the second line, Ai (i = 1,2,...,n), elements of the sequence are given separated by space characters.

Output

Print the sorted sequence. Two contiguous elements of the sequence should be separated by a space character. The element which is selected as the pivot of the partition should be indicated by [  ].

Constraints

  
1 ≤ n ≤ 100,000

  
0 ≤ Ai ≤ 100,000

Sample Input 1

12
13 19 9 5 12 8 7 4 21 2 6 11

Sample Output 1

9 5 8 7 4 2 6 [11] 21 13 19 12



Sample input:
12
13 19 9 5 12 8 7 4 21 2 6 11


Sample output:
9 5 8 7 4 2 6 [11] 21 13 19 12

Submission status: Accepted

Solution code:
def partition(A, n):
    r = A[-1]
    i = -1
    for j in range(n-1):
        if A[j] <= r:
            i = i + 1
            (A[i], A[j]) = (A[j], A[i])

    (A[i+1], A[-1]) = (A[-1], A[i+1])

    return " ".join(map(str, A[:i+1])) + " [" + str(A[i+1]) + "] " + " ".join(map(str, A[i+2:]))
    
n = int(input())
X = list(map(int, input().split()))

print(partition(X, n))

Submission status: Accepted

Solution code:
def partition(A, l, r):
    x = A[r - 1]
    i = l - 1
    for j in range(l, r - 1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r - 1] = A[r - 1], A[i + 1]
    return i + 1


n = int(input())
*A, = map(int, input().split())
r = str(A[-1])
partition(A, 0, n)
A = list(map(str, A))
B = []
flg = True
for a in A[::-1]:
    if a == r and flg:
        b = '[{}]'.format(a)
        flg = False
    else:
        b = a
    B.append(b)
print(*B[::-1])

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
            
    A[i+1], A[r] = A[r], A[i+1]
    return i+1
    
n = int(input())
A = [int(x) for x in input().split()]

p = partition(A, 0, n-1)

for i in range(n):
    if i:
        print(" ", end = "")
    if i == p:
        print("[", end = "")
    print(A[i], end = "")
    if i == p:
        print("]", end = "")
print()

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r] # last item
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

n = int(input())
A = [i for i in map(int,input().split())]

x = partition(A,0,n-1)
ans = []

for i in range(n):
    if i == x:
        ans.append('[' + str(A[i]) + ']')
    else:
        ans.append(str(A[i]))
print(' '.join(ans))

Submission status: Accepted

Solution code:
def partition(A: list, p: int = 0, r: int = None):
    if r is None:
        r = len(A) - 1
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


N = int(input())
A = list(map(int, input().split()))
r = partition(A)
A = ["[{}]".format(a) if i == r else str(a) for i, a in enumerate(A)]
print(*A)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def pertision(A, l, r):
    pivot = A[r]
    i = 0
    for j in range(l, r):
        if A[j] <= pivot:
            A[l+i], A[j] = A[j], A[l+i]
            i += 1
    A[l+i], A[r] = A[r], A[l+i]      
    
    return l+i

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

pivot_i = pertision(A, 0, N-1)

s = []
for i in range(N):
    if i == pivot_i:
        s.append('[{}]'.format(A[i]))
    else:
        s.append(str(A[i]))

print(*s)

Submission status: Accepted

Solution code:
N = int(input())
num_list = [int(item) for item in input().split()]

def partition(A, p, r):
    x = A[r]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return A, i+1


res, index = partition(num_list, 0, len(num_list)-1)

res_out = ''
for i, v in enumerate(res):
    if i == index:
        res_out += '['+ str(v) + '] '
    else:
        res_out += str(v) + ' ' 
    
print(res_out[:-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j, n in enumerate(A[:-1]):
        if n <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

_ = int(raw_input())
nums = map(int, raw_input().split(" "))
p = partition(nums, 0, len(nums)-1)
nums[p] = "[{}]".format(nums[p])
sys.stdout.write(str(nums[0]))
for n in nums[1:]:
    sys.stdout.write(" {}".format(n))
sys.stdout.write("\n")

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
        else:
            continue
    A[r] = A[i+1]
    A[i+1] = x
    return i+1

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    x = partition(a, 0, n-1) 
    A = [str(a[i]) for i in range(n)]
    A[x] = '[' + A[x] + ']'
    for i in range(n):
        if i == n-1:
            print(A[i])
        else:
            print(A[i], end=' ')
main()

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))

def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    
    return i+1

p_ind = partition(a, 0, n-1)

print(*a[:p_ind], '['+str(a[p_ind])+']', *a[p_ind+1:])

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i + 1], A[r] = A[r], A[i + 1]

    return i + 1


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

index = partition(A, 0, len(A) - 1)
A[index] = "[{}]".format(A[index])
print(*A)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    A[i+1] = '[{}]'.format(A[i+1])
    return i + 1


if __name__ == "__main__":
    input()
    A = [int(x) for x in input().split()]
    target = A[-1]

    partition(A, 0, len(A) - 1)
    output_str = [str(a) for a in A]
    print(' '.join(output_str))

Submission status: Accepted

Solution code:
def partition(A, l, r):
    """ partition A[l:r] using q(A[r]) and return q's index
    """
    q = A[r]
    sep_i = l # left elements of seq <= q < right ones
    for j in range(l, r):
        if A[j] <= q:
            # A[j] is left element
            
            # add A[j] to last of left, and replace first of right to last
            A[sep_i], A[j] = A[j],  A[sep_i]
            sep_i += 1 # update separator
        else:
            # A[j] is right element
            pass

    A[sep_i], A[r] = A[r], A[sep_i]
    
    return sep_i

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

q_i = partition(A, 0, n-1)

print(*A[:q_i],  '[' + str(A[q_i]) + ']', *A[q_i+1:])

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

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

p = partition(A, 0, n-1)

for i in range(n):
    if i:
        print(' ', end = '')
    if i == p:
        print('[', end = '')
    print(A[i], end = '')
    if i == p:
        print(']', end = '')
print()

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


n = int(input())
A = [int(x) for x in input().split()]

p = partition(A, 0, n-1)

for i in range(n):
    if i:
        print(" ", end = "")
    if i == p:
        print("[", end="")
    print(A[i], end="")
    if i == p:
        print("]", end="")
print()

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p-1
    # iは必ず1ずつ増える、jでx以下の要素を検出し、iの位置に持って行く
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1

N = int(input())
B = list(map(int,input().split()))
b = partition(B,0,N-1)
#print(b)
B_str = list(map(str,B))
B_str[b] = '[' + B_str[b] +']'
print(' '.join(B_str))

Submission status: Accepted

Solution code:
#インプットdata
input_n = int(input())
input_a = list(map(int, input().split()))
position = -1

#Partitionアルゴリズム
def partition(list, n):
    x = list[n-1]
    i = 0
    for j in range(n-1):
        if list[j] <= x:
            list[i], list[j] = list[j], list[i]
            i += 1
    list[i], list[n-1] = list[n-1], list[i]
    return i

#実行結果
position = partition(input_a, input_n)
print(" ".join(map(str, input_a[0:position])), end="")
print(f" [{input_a[position]}] ", end="")
print(" ".join(map(str, input_a[position+1:])))

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p 
    for j in range(p,r):
        if A[j] <= x:
            A[i],A[j] = A[j],A[i]
            i += 1

    A[i],A[r] = A[r],A[i]

    return i

n = int(input())
a = [int(s) for s in input().split()]
t = partition(a,0,n-1)
print(*(str(x) if i != t else "[%d]"%x for i,x in enumerate(a)))

Submission status: Accepted

Solution code:
# Partition
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if (A[j] <= x):
            i += 1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    return i+1

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

idx = partition(A, 0, len(A) - 1)
A[idx] = f'[{A[idx]}]'
print(*A)

Submission status: Accepted

Solution code:
def partition(p, r):
    x = A[r]
    i = - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = [A[r]], A[i+1]
    print(' '.join(list(map(str, A))))

if __name__ == "__main__":
    n = int(input())
    A = list(map(int, input().split()))
    partition(0, n-1)

Submission status: Accepted

Solution code:
def part(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if(A[j]<=x):
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1

n=int(input())
a=list(map(int,input().split()))

qi=part(a,0,len(a)-1)
list_qi=[a[qi]]
a[qi]=list_qi
print(*a)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp
    return A, i+1
n = int(input())
A = list(map(int, input().split(' ')))
parted_A, idx = partition(A, 0, n-1)
str_parted_A = list(map(str, parted_A))
str_parted_A[idx] = "[{}]".format(str_parted_A[idx])
print(" ".join(str_parted_A))

Submission status: Accepted

Solution code:
n = int(input())

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

def partition(B, p, r):
  x = B[r]
  global i
  i = p-1
  for j in range(p, r):
    if B[j] <= x:
      i += 1
      y = B[i]
      z = B[j]
      B[i] = z
      B[j] = y
  a = B[i+1]
  b = B[r]
  B[i+1] = b
  B[r] = a

partition(A, 0, n-1)

print(" ".join(map(str, A[:i+1])), end='')
print(" [" + str(A[i+1]) + "] ", end='')
print(" ".join(map(str, A[i+2:])))

Submission status: Accepted

Solution code:
"""
配列の一番左の値Xを基準に
それより小さい値と大きい値を分けて再配置するコード
Xより小さい値はiより左に、大きい値は右側に配置する。
jは現在探索している添字
"""


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        # 小さい値があればそれより左に移動させる
        if A[j] <= x:
            # 添字iも大きくする
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return A, i + 1


# if __name__ == "__main__":
n = int(input())
A = list(map(int, input().split()))

A, I = partition(A, 0, n - 1)
# 標準出力に癖がある
# new_A=[]
# for i in range(n):
#     if i==I:
#         # new_A.append('[')
#         # new_A.append(str(A[i]))
#         # new_A.append(']')

#         print('[',end='')
#         print(A[i],end='')
#         print(']',end=' ')
#     else:
#         print(A[i],end=' ')
#         # new_A.append(str(A[i]))
# print()
# # print(' '.join(list(map(str, new_A))))

for i in range(n):
    if i:
        print(" ", end="")
    if i == I:
        print("[", end="")
    print(A[i], end="")
    if i == I:
        print("]", end="")
print()

Submission status: Accepted

Solution code:
#!/usr/bin/python
#-- coding=utf8



def exchangeData(A, it1, it2):
    tmp = A[it1]
    A[it1] = A[it2]
    A[it2] = tmp


def partition(A, p, r):
    x=A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i+1
            exchangeData(A, i, j)

    exchangeData(A, i+1, r)
    return i+1


def print_partitionData(A, part_index):
    for i, s in enumerate(A):
        if i !=0:
            print(" ", end= "")

        if i==part_index :
            print ("[{}]".format( s), end="")
        else:
            print (s, end="")
    print("")

        
def inputData():
    data = map(int, input().split())
    return list(data)

if __name__ == "__main__" :
    input()
    A = inputData()
    part_index = partition(A, 0, len(A)-1)
    print_partitionData(A, part_index)

Submission status: Accepted

Solution code:
#partition

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(r):
        if A[j] <= x:
            i += 1
            a = A[j]
            A[j] = A[i]
            A[i] = a
    a = A[i+1]
    A[i+1] = A[r]
    A[r] = a

    return i+1

n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, len(A)-1)

result = ''
for i in range(len(A)):
    if i == p:
        result += '['+str(A[i])+'] '
    else:
        result += str(A[i]) + ' '

print(result[:-1])

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i = i + 1
            y = A[i]
            A[i] = A[j]
            A[j] = y
    z = A[i+1]
    A[i+1] = '['+str(A[r])+']'
    A[r] = z
    return i + 1

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

partition(A, 0, n-1)

print(*A)

Submission status: Accepted

Solution code:
def partition(p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    A[i + 1] = f"[{A[i + 1]}]"
    print(" ".join(map(str, A)))
    return i + 1


input()
A = list(map(int, input().split()))
partition(0, len(A) - 1)

Submission status: Accepted

Solution code:
"""
パーティションを作成する
"""
def partition(A, p, r):
    x = A[r]
    i = p-1 #A[i+1], A[i+2],,,がxより大きくなるようにしたい
    #jはxより大きいを指す
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[j], A[i] = A[i], A[j]
        else:
            pass #何もできない
    A[i+1], A[r] = A[r], A[i+1]
    return i+1, A #交換したあとのxのインデックスを返す


n = int(input())
a = list(map(int, input().split()))
index, a = partition(a, 0, n-1)
a = list(map(str, a))
a[index] = "[" + str(a[index]) + "]"
print(' '.join(a))

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p - 1

    for j in range(p,r):
        if A[j] <= x:
            i += 1
            temp = A[i]
            A[i] = A[j]
            A[j] = temp
    temp = A[i + 1]
    A[i + 1] = A[r]
    A[r] = temp

    return i + 1

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().split()))
    q = partition(A,0,n - 1)

    for i in range(n):
        if i:
            print(" ", end="")
        if i == q:
            print("[", end="")
        if i == n - 1:
            print(A[i])
        else:
            print(A[i], end="")
        if i == q:
            print("]", end="")

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r-1]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i +1
            A[i], A[j] = A[j], A[i]
            
    return i
        

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

num = partition(A,0,n)
A[num] = "[" + str(A[num]) +"]"
print(*A)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


if __name__ == '__main__':
    import sys

    n = int(input())
    A = list(map(int, sys.stdin.readline().split()))
    q = partition(A, 0, n - 1)
    end = ' '
    for i in range(n):
        if i == n - 1:
            end = '\n'
        if i == q:
            print('[{}]'.format(A[i]), end=end)
        else:
            print(A[i], end=end)

Submission status: Accepted

Solution code:
# ALDS1_6_B
def partition(a, p, r):
    x = a[r]
    i = p
    for j in range(p, r):
        if a[j] <= x: # 最後の要素が基準
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[r] = a[r], a[i]
    return i

n = int(input())
a = list(map(int, input().split()))
index = partition(a, 0, n-1)
print(*a[:index], "[" + str(a[index]) + "]", *a[index+1:])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]

x = A[-1]
i = -1
for j in range(0, len(A) - 1):
    if x >= A[j]:
        i += 1
        A[i], A[j] = A[j], A[i]
A[i+1], A[-1] = A[-1], A[i+1]
q = i + 1

return_str = str(A[0])
for i, k in enumerate(A):
    if i != 0:
        if i == q:
            return_str += " [" + str(k) + "]"
        else:
            return_str += ' ' + str(k)

print(return_str)

Submission status: Accepted

Solution code:
def partition(array, start, end):
    end_val = array[end]
    left_end = start - 1
    for search_idx in range(start, end):
        if array[search_idx] <= end_val:
            left_end += 1
            array[left_end], array[search_idx] = array[search_idx], array[left_end]
    array[left_end + 1], array[end] = array[end], array[left_end + 1]
    return left_end + 1


def main():
    n = int(input())
    array = list(map(int, input().split(" ")))
    partition_idx = partition(array, 0, n - 1)
    array = list(map(str, array))
    print(" ".join(array[:partition_idx]) +
          " [{}] ".format(array[partition_idx]) +
          " ".join(array[partition_idx + 1:]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_6_B&lang=ja

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

n = int(input())
A = list(map(int, input().split()))
q = partition(A, 0, n - 1)

for j in range(n - 1):
    if j == q:
        print("[{}]".format(A[q]), end=' ')
    else:
        print(str(A[j]), end=' ')
print(A[-1])

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))

buf = i = j = 0
x = A[n-1]
for j in range(n-1):
    if A[j] <= x:
        buf = A[i]
        A[i] = A[j]
        A[j] = buf
        i += 1
A[n-1] = A[i]
A[i] = x
k = 0
[print(A[k],"",end="") if k != i else print("[",A[k],"]",sep="",end=" ") for k in range(n-1)]
print(A[n-1])

Submission status: Accepted

Solution code:


def partition(A, p, r):
    x = A[r - 1]
    i = p - 1
    for j in range(p, r - 1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[-1] = A[-1], A[i + 1]
    return i + 1
        
n = int(input())
A = list(map(int, input().split())) 

tmp = partition(A, 0, n)
for i in range(n - 1):
    if i == tmp:
        print("[" + str(A[tmp]) + "]", end = " ")
    else:
        print(A[i], end = " ")
print(A[-1])

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1


n, *A = map(int, open(0).read().split())
f = partition(A, 0, n-1)
ans = ''
for i in range(n):
    if i == f:
        ans += f'[{A[i]}] '
    else:
        ans += f'{A[i]} '
print(ans[:len(ans) - 1])

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
def partition(A,p,r):
	x=A[r]
	i=p-1
	for j in range(p,r):
		if A[j]<=x:
			i+=1
			A[i],A[j]=A[j],A[i]
	A[i+1],A[r]=A[r],A[i+1]
	return i+1
r=""
q=partition(a,0,n-1)
for i in range(n):
	if i:
		r+=(" ")
	if i==q:
		r+=("[")
	r+=str(a[i])
	if i==q:
		r+=("]")
print(r)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    key = A[r]
    i = p
    for j in range(p, r):
        # 把小的放在左边
        if A[j] <= key:
            A[i], A[j] = A[j], A[i]
            i += 1
    # 最后交换key值
    A[r], A[i] = A[i], A[r]
    return i


if __name__ == '__main__':
    n = int(input())
    numlist = [int(num) for num in input().split(' ')]
    index = partition(numlist, 0, len(numlist) - 1)
    out = str(numlist[0:index]).replace(',', '').replace('[', '').replace(']', '') \
        + ' [' + str(numlist[index]) + '] '\
        + str(numlist[index + 1:]).replace(',', '').replace('[', '').replace(']', '')
    print(out)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")

def Partition(aa,p,r):
    x=aa[r]
    i=p-1
    for j in range(p,r):
        if aa[j]<=x:
            i+=1
            aa[i],aa[j]=aa[j],aa[i]
    aa[i+1],aa[r]=aa[r],aa[i+1]
    return i+1

def main():
    n=int(input())
    aa=list(map(int, input().split()))
    idx=Partition(aa,0,n-1)
    aa[idx]="["+str(aa[idx])+"]"
    print(*aa)
main()

Submission status: Accepted

Solution code:
def partition(A, left, right):
    pivot = A[right]
    i = -1
    for j in range(left, right):
        if A[j] <= pivot:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[right] = A[right], A[i+1]
    return i + 1


if __name__ == "__main__":
    n = int(input())
    *A, = map(int, input().split())
    
    k = partition(A, 0, len(A)-1)

    A[k] = '[' + str(A[k]) + ']'
    print(*A)

Submission status: Accepted

Solution code:

def partition(p, r):
    global A

    x = A[r]
    i = p - 1

    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]

    A[i+1], A[r] = A[r], A[i+1]
    return i + 1


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

q = partition(0, N-1)

A_str = list(map(str, A))
A_str[q] = '[' + A_str[q] + ']'

print(' '.join(A_str))

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i +=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[r]=A[r],A[i+1]
    return i+1


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

P=partition(A,0,n-1)
A[P]="["+str(A[P])+"]"
print(*A)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]

x = A[-1]
i=0
for j in range(n-1):
    if A[j]<=x:
        A_j=A[j]
        A[j]=A[i]
        A[i]=A_j
        i+=1
A[-1]=A[i]
A[i]=[x]

print(*A)

Submission status: Accepted

Solution code:
# ALDS1_6_B
def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            w = A[i]
            A[i] = A[j]
            A[j] = w
    v = A[i+1]
    A[i+1] = A[r]
    A[r] = v
    return i + 1

n = int(input())
A = list(map(int, input().split()))
#n = 12
#A = [13,19,9,5,12,8,7,4,21,2,6,11]
#standard = A[-1]
p = partition(A, 0, n-1)
# for idx, item in enumerate(A):
#     if item == standard:
#         A[idx] = "["+str(standard)+"]"
for i in range(n):
    if i:
        print(" ", end = "")
    if i == p:
        print("[", end="")
    print(A[i], end="")
    if i == p:
        print("]", end="")
print()

Submission status: Accepted

Solution code:
n = int(input())
s = list(map(int, input().split()))
def partition(s, l, r):
    pivot = s[r]
    minVI = -1
    i = l
    while i < r:
        if s[i] <= pivot:
            minVI+=1
            s[minVI], s[i] = s[i], s[minVI]
        i+=1
    s[minVI+1], s[r] = s[r], s[minVI+1]
    return minVI+1
pivotI = partition(s, 0, len(s)-1)
answer = ''
for i in range(len(s)):
    if i!= 0:
        answer+=' '
    if i == pivotI:
        answer+='['+str(s[i])+']'
    else:
        answer+=str(s[i])
print(answer)

Submission status: Accepted

Solution code:
def partition(arr, p, r):
    x = arr[r]
    index = p - 1  # arr[p,index] <= x,arr[index+1,i)>x
    for i in range(p, r):
        if arr[i] <= x:
            arr[i], arr[index + 1] = arr[index + 1], arr[i]
            index += 1
    arr[index + 1], arr[r] = arr[r], arr[index + 1]
    return index + 1


if __name__ == '__main__':
    n = int(input())
    arr = list(map(int, input().split()))
    index = partition(arr, 0, n - 1)
    for i in range(n):
        if i != 0:
            print(' ', end='')
        if i == index:
            print('[', end='')
        print(arr[i], end='')
        if i == index:
            print(']', end='')
    print()

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x=A[r]
    i=p-1
    for j in range(p,r):
        if A[j]<=x:
            i+=1
            m=A[i]
            A[i]=A[j]
            A[j]=m
    m=A[i+1]
    A[i+1]="["+str(x)+"]"
    A[r]=m
n=int(input())
A=list(map(int,input().split()))
partition(A,0,n-1)
print(*A)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r-1]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    return i+1

n = int(input())
A = list(map(int,input().split()))
num = partition(A, 0, n)
A[num-1] = f"[{A[num-1]}]"
print(*A)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split(" ")))

def partition(A, p, r):
    x = A[r - 1]
    i = p -1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i

q = partition(A, 0, n)
A[q] = "[" + str(A[q]) + "]"
print(*A)

Submission status: Accepted

Solution code:
def partition(A, l, r):
    v = A[r-1]
    i = l - 1
    for j in range(l, r-1):
        if A[j] <= v:
            i += 1
            t = A[i]
            A[i] = A[j]
            A[j] = t
    q = i+1
    A[r-1] = A[q]
    A[q] = v
    return q

N = int(input())
A = list(map(int, input().split()))
q = partition(A, 0, N)
print(*['['+str(A[i])+']' if i == q else A[i] for i in range(N)])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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


def main():
    # print(A)
    partition(A, 1, len(A) - 1)


def partition(A, p, r):
    last = A[r]
    i = p - 1
    # print("last:{}".format(last))
    # print("i:{}".format(i))
    for j in range(i, r, 1):
        # print("A[j]:{}".format(A[j]))
        if A[j] <= last:
            # print("change")
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
            i += 1

        # print(A)
    tmp = A[i]
    A[i] = A[r]
    A[r] = tmp

    for k in range(len(A)):
        if k > 0:
            print(' ', end="")
        if k == i:
            strNum = "[" + str(A[k]) + "]"
        else:
            strNum = str(A[k])
        print(strNum, end="")
    print()
    # print(A)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int, input().split()))

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[j], A[i] = A[i], A[j]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

j = partition(A, 0, n - 1)
A = [str(i) for i in A]
A[j] = '[{}]'.format(A[j])
print(' '.join(A))

Submission status: Accepted

Solution code:
def partition(A, p, r):
	x = A[r]
	i = p - 1
	for j in range(p, r):
		if A[j] <= x:
			i += 1
			A[i], A[j] = A[j], A[i]
	A[i + 1], A[r] = A[r], A[i + 1]
	return i + 1


if __name__ == "__main__":
	n = int(input())
	A = list(map(int, input().split()))
	q = partition(A, 0, n-1)
	A[q] = '[' + str(A[q]) + ']'
	print(' '.join(map(str, A)))

Submission status: Accepted

Solution code:
# https: // onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_B
# クイックソートを理解するために必要な問題。まあやるだけ


def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= x:
            i = i+1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1


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

idx = partition(A, 0, len(A) - 1)
A[idx] = f'[{A[idx]}]'
print(*A)

Submission status: Accepted

Solution code:
"""
パーティション
ある基準の値を元に分類わけするアルゴリズム
12
13 19 9 5 12 8 7 4 21 2 6 11
"""

def partition(A, n):
    x = A[n-1]
    i = 0
    j = 0
    for k in range(n):
        if A[k] <= x:
            tmp = A[i]
            A[i] = A[k]
            A[k] = tmp
            i += 1
        j += 1
    return i-1
            



if __name__=="__main__":
    n = int(input())
    A = list(map(int, input().split()))
    reference_index  = partition(A, n)
    A_str = []
    for x, a in enumerate(A):
        if x == reference_index:
            A_str.append("["+str(a)+"]")
        else:
            A_str.append(str(a))
    print(" ".join(A_str))
    # print(count)

Submission status: Accepted

Solution code:
n = int(input())
S = list(map(int, input().split()))


def partition(A, p, r):
  x = A[r]
  i = p
  for j in range(p, r):
    if A[j] <= x:
      A[i], A[j] = A[j], A[i]
      i += 1
  A[i], A[r] = A[r], A[i]
  return i

r = partition(S, 0, n-1)

ans = [str(x) for x in S]
ans[r] = '[{}]'.format(ans[r])
print(' '.join(ans))

Submission status: Accepted

Solution code:
def Partition(NUM_LIST, left, right):
    NUM_LIST = NUM_LIST[left:right]
    v = NUM_LIST[-1]
    border = 0
    for i in range(len(NUM_LIST)-1):
        if v >= NUM_LIST[i]:
            NUM_LIST[border], NUM_LIST[i] = NUM_LIST[i], NUM_LIST[border]
            border+=1
    NUM_LIST[border], NUM_LIST[-1] = NUM_LIST[-1], NUM_LIST[border]
    return border, NUM_LIST

n = int(input())
NUM_LIST = list(map(int, input().split()))
border, NUM_LIST = Partition(NUM_LIST, 0, len(NUM_LIST))

print(" ".join(list(map(str, NUM_LIST[:border]))) + " ["+str(NUM_LIST[border])+"] "
+" ".join(list(map(str, NUM_LIST[border+1:]))))