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, 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()))
x = A[n-1]
q = partition(A, 0, n-1)
print(" ".join(map(str,A[0:q])) + " [" + str(x) + "] " + " ".join(map(str,A[q+1: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 += 1
      A[i], A[j] = A[j], A[i]
  A[i+1], A[r] = A[r], A[i+1]
  return i+1

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

  A[q] = "[%d]"%A[q]
  print(" ".join(map(str, A)))

if __name__ == "__main__":
  main()

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

r = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, r-1)
A = list(map(str, A))
A[p] = "[%s]"%(A[p])
print(" ".join(A))

Submission status: Accepted

Solution code:
# coding=utf-8

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 = list(map(int, input().split()))
m = partition(A, 0, n-1)
A = list(map(str, A))
A[m] = "[%s]"%(A[m])
print(*A)

Submission status: Accepted

Solution code:
def main():
    n = input()
    A = map(int,raw_input().split())

    q = partition(A,0,n-1)
    for i in range(n-1):
        if i == q:
            print "[{}]".format(A[q]),
        else:
            print A[i],
    print A[-1]

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

if __name__ == "__main__":
    main()

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]
    return i + 1
n = int(input())
A = [int(i) for i in input().split()]
q = partition(0, n - 1)
A[q] = "[%d]"%A[q]
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
            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())
    B = list(map(int, input().split()))
    p = partition(B, 0, n-1)
    print(" ".join(map(str, B[:p])) + " [" + str(B[p]) + "] " + " ".join(map(str, B[p+1:])))

Submission status: Accepted

Solution code:
def swap(A, i, j):
#    print("\tswap Aj:{} Ai:{}\n".format(A[j], A[i]))
    x = A[i]
    A[i] = A[j]
    A[j] = x

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            swap(A, i, j)
#        print("j:{} Aj:{} i:{} Ai:{} Ar:{}".format(j, i, A[j], A[i], A[r]))
#        print(A)
#        print(" ")
    A[r] = "[{}]".format(A[r])
    swap(A,i+1, r)
    i += 1
    return i

def main():
    """ ????????? """
    num = int(input().strip())
    A = list(map(int,input().split()))
    partition(A, 0, num-1)
    print(" ".join(map(str,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[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

i = partition(A, 0, n-1)
print(' '.join(map(str, A[:i])) + ' [' + str(A[i]) + '] ' + ' '.join(map(str, A[i+1:])))

Submission status: Accepted

Solution code:
n = int(raw_input())
a = map(int, raw_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

x = partition(a, 0, n-1)
for i in range(n):
    if i == x:
        print '[%d]' % a[i],
    elif i == n-1:
        print a[i]
    else:
        print a[i],

Submission status: Accepted

Solution code:
def partition(A,p,n):
    x=A[n-1]
    i=p-1
    for j in range(n-1):
        if A[j]<=x:
            i+=1
            A[i],A[j]=A[j],A[i]
    A[i+1],A[n-1]=A[n-1],A[i+1]
    
    A[i+1]="[{}]".format(A[i+1])
    
    print(*A)
    

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

partition(A,0,n)

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 = i + 1
            A[i],A[j] = A[j],A[i]

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

    print("{0} [{1}] {2}".format(" ".join(map(str,A[:i+1])),str(A[i+1])," ".join(map(str,A[i+2:]))))

    return



if __name__ == '__main__':
    cnt = int(input())
    A = list(map(int,input().split()))
    p = 0
    r = len(A)
    partition(A,p,r)

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()))
q = partition(A, 0, n - 1)
print(" ".join(map(str, A[:q])), "[{0}]".format(A[q]),
      " ".join(map(str, A[q + 1:])))

Submission status: Accepted

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def partition(A,p=0, r=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
            swap(A,i,j)
    swap(A,i+1,r)
    return i+1

if __name__ == "__main__":
    input()
    A = list(map(int, input().strip().split()))
    k = partition(A)
    B = list(map(str, A))
    B[k] = "[{}]".format(B[k])
    print(" ".join(B))

Submission status: Accepted

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

x = a[-1]
i = -1

for j in range(len(a)-1):
    if a[j] <= x:
        i += 1
        a[i], a[j] = a[j], a[i]

a[i + 1], a[n - 1] = "[" + str(a[n - 1]) + "]", a[i + 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]
    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

q = partition(A,0,n-1)
print(*A[:q],end=' ')
print('[{0}]'.format(A[q]),end=' ')
print(*A[q+1:])

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
import sys


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


if __name__ == "__main__":
    data = [val.split() for val in sys.stdin.readlines()]
    n = int(data[0][0])
    progression = [int(val) for val in data[1]]
    i = partition(progression, 0, n - 1)
    result = [str(val) for val in progression]
    result[i] = "[" + result[i] + "]"
    print(" ".join(result))

Submission status: Accepted

Solution code:
length = int(input())
target = [int(n) for n in input().split(" ")]
splitter = target[-1]
border = 0
for i, n in enumerate(target):
    if n <= splitter:
        target[i], target[border] = target[border], target[i]
        border += 1
target[border - 1] = [splitter]
print(*target)

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



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

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

Submission status: Accepted

Solution code:
def partition(A, p, r):
	x = A[r]
	i = p - 1
	for j in xrange(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

n = int(raw_input())
A = map(int, raw_input().split())

newA, q = partition(A, 0, len(A)-1)

for i in range(n-1):
	if i == q:
		print("[{:}]".format(newA[i])),
	else:
		print(newA[i]),
print newA[-1]

Submission status: Accepted

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

    return i


n = int(raw_input())
A = map(int, raw_input().split())

q = partition(A, 0, n-1);

A = map(str, A)
A[q] = "[" + A[q] + "]"

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 = 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 i+1


def main():
    n = int(input())
    Array = list(map(int,input().split()))
    q = partition(Array,0,n-1)
    Array[q] = "[%d]"%Array[q]
    print(" ".join(map(str,Array))) # " ".join???????????§????????£??????????????£???
  

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def partiton(A, p, r):
    x = A[-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]

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


_ = int(input())
li = [int(x) for x in input().split(' ')]
q = partiton(li, 0, len(li) - 1)


li[q] = "[%s]" % (li[q])
print(" ".join([str(i) for i in li]))

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()))
k=partition(A,0,len(A)-1)
front=" ".join(map(str,A[:k]))
back=" ".join(map(str,A[k+1:]))
ans=front+" ["+str(A[k])+"] "+back
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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 = [int(a) for a in input().split()]

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

    A[q] = "[" + str(A[q]) + "]"
    print(" ".join(map(str, 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
n = int(input())
A = list(map(int, input().split()))
p = partition(A, 0, n - 1)
A[p] = f"[{A[p]}]"
print(*A)

Submission status: Accepted

Solution code:
def partition(hoge):
    x = hoge[-1]
    i = -1
    for j in range(len(hoge)):
        if hoge[j] <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    """        
    tmp = hoge[i+1]
    hoge[i+1] = hoge[-1]
    hoge[-1] = tmp
    """
    return i
    
if __name__ == '__main__':
    _ = input()
    hoge = [int(x) for x in input().split()]
    part = partition(hoge)
    ans = list()
    for num, elem in enumerate(hoge):
        if num == part:
            ans.append('[{}]'.format(elem))
        else:
            ans.append(str(elem))
    print (' '.join(ans))

Submission status: Accepted

Solution code:
def p(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()))
k=p(A,0,n-1)
A[k]='['+str(A[k])+']'
print(*A)

Submission status: Accepted

Solution code:
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]='['+str(A[n])+']',A[i]
print(*A)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())-1
A=list(map(int,input().split()))
i=0
for j in range(n):
 if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
A[i],A[n]=A[n],A[i]
print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))

Submission status: Accepted

Solution code:
def s():
 n=int(input())-1
 A=list(map(int,input().split()))
 i=0
 for j in range(n):
  if A[j]<=A[-1]:A[i],A[j]=A[j],A[i];i+=1
 A[i],A[n]=A[n],A[i]
 print(" ".join(map(str,A[:i]))+" ["+str(A[i])+"] "+" ".join(map(str,A[i+1:])))
if'__main__'==__name__:s()

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
            memo = A[i]
            A[i] = A[j]
            A[j] = memo
    memo = A[i+1]
    A[i+1] = x
    A[r] = memo
    return i+1, A

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

index, aList = partition(a, 0, len(a)-1)
aList[index] = "[" + str(aList[index]) + "]"

print(*aList)

Submission status: Accepted

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

n = int(input())
a = list(map(int, input().split()))
std = partition(a, 0, n-1)
for idx, i in enumerate(a):
    if idx == std:
        print("[{0:}]".format(i), end = "")
    else:
        print(i, end = "")
    if idx != n-1:
        print(" ", end = "")
print("")

Submission status: Accepted

Solution code:
def partition(li, p, r):
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1
    for j in range(p, r):
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

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

    return i


def run():
    c = int(input())
    ax = [int(n) for n in input().split()]

    p = partition(ax, 0, c-1)
    for (i, a) in enumerate(ax):
        if i == p:
            val = '[{}]'.format(a)
        else:
            val = str(a)

        if i < c-1:
            print(val, end=" ")
        else:
            print(val)


if __name__ == '__main__':
    run()

Submission status: Accepted

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

N = int(input())
X = list(map(int, input().split()))
N = [0]
N.extend(X)
partition(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
            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()))

i = partition(a, 0, n - 1)
a[i] = "[" + str(a[i]) + "]"
print(" ".join(map(str, a)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 21:24:25 2018
ALDS1_6_B
@author: maezawa
"""

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
            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
    
mid = partition(a, 0, len(a)-1)
print(a[0], end='')
for i in range(1, mid):
    print(' {}'.format(a[i]), end='')
print(' [{}]'.format(a[mid]), end='')
for i in range(mid+1,len(a)):
    print(' {}'.format(a[i]), 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
            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(' ')))
pi = partition(A, 0, len(A)-1)

A = ['[' + str(A[i]) + ']' if i == pi else str(A[i]) for i in range(len(A))]
print(' '.join(A))

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# Aizu Online Judge. Partition
import sys

def partition(A, p, r):
    x = A[r]
    i = p-1
    for n in range (p,r):
        if A[n] <= x:
            i += 1
            A[i], A[n] = A[n], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    print(' '.join(map(str,A[:i+1])), end= ' ')
    print('[', A[i+1], ']', sep='', end='')
    if i+1 != r:
        print(' ', end='')
    print(' '.join(map(str,A[i+2:])))


n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))
partition(A, 0, n-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

if __name__ == "__main__":
    n=int(input())
    A=list(map(int,input().split()))
    j=partition(A,0,n-1)
    for i in range(n):
        if i == n-1:
            print(A[i])
        elif i==j:
            print("[{}]".format(A[i]),end=" ")
        else:
            print(A[i],end=" ")

Submission status: Accepted

Solution code:
def partition(a_list):
    # 仕切り位置をi-1とiの間、比較している値の位置をjとする
    i = 0
    for j in range(len(a_list) - 1):
        if a_list[j] > a_list[len(a_list) - 1]:
            continue
        else:
            a_list[i], a_list[j] = a_list[j], a_list[i]
            i += 1
    a_list[len(a_list) - 1] = '[' + str(a_list[len(a_list) - 1]) + ']'
    a_list[i], a_list[len(a_list) - 1] = a_list[len(a_list) - 1], a_list[i]

n = int(input())
A = list(map(int, input().split()))
partition(A)
print(' '.join(map(str, 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-1):
        if a[j] <= x:
            i = 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
pivot = partition(a, 0, n)
l = [str(a[i]) for i in range(pivot)]
r = [str(a[i]) for i in range(pivot+1, n)]
print(' '.join(l) +' [' + str(a[pivot]) + '] ' + ' '.join(r))

Submission status: Accepted

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

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

    return i + 1


n = int(input())
ary = [int(_) for _ in input().split()]
q = partition(ary, 0, n - 1)
print(*ary[:q], '[{}]'.format(ary[q]), *ary[q + 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())
input_list = list(map(int, input().split(' ')))

q = Partition(input_list, 0, n - 1)

print(*input_list[:q], "[{}]".format(input_list[q]), *input_list[q + 1:])

Submission status: Accepted

Solution code:
def partition(num_list, start, end):
    split = start -1
    x = num_list[end]
    for i in range(start, end):
        if num_list[i] <= x:
            split += 1
            num_list[split], num_list[i] = num_list[i], num_list[split]
    num_list[split+1], num_list[end] = num_list[end], num_list[split+1]
    num_list = [str(i) for i in num_list]
    num_list[split+1] = '[{}]'.format(num_list[split+1])
    print(' '.join(num_list))

n = int(input())
input_line = [int(i) for i in input().split()]
partition(input_line, 0, n-1)

Submission status: Accepted

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

def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    print(' '.join(map(str, a)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#coding:utf-8
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
a = partition(A, 0, n)
A[a] = [A[a]]
A = " ".join([str(num) for num in A])
print(A)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(n - 1):
        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 i + 1

def print_list(A, r):
    for i, e in enumerate(A):
        if i == n - 1:
            print(e)
        elif i == r:
            print([e], end=' ')
        else:
            print(e, end=" ")

n = int(input())
A = [int(e) for e in input().split()]
r = partition(A, 0, -1)
print_list(A, r)

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 i + 1, x


def print_list_split_whitespace(a, x):
    ind = 0
    for i, y in enumerate(a):
        if x == y:
            ind = i
    for i in range(len(a) - 1):
        if i == ind:
            print("[" + str(a[i]) + "]", end=" ")
        else:
            print(a[i], end=" ")
    if ind == len(a) - 1:
        print("[" + str(a[-1]) + "]")
    else:
        print(a[-1])


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

q, x = partition(a, 0, n - 1)

print_list_split_whitespace(a, x)

Submission status: Accepted

Solution code:
def partition(a, left, right):
    pivot = a[right-1]
    i = left - 1
    for j in range(left, right-1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[right-1] = a[right-1], a[i+1]
    return i + 1
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    print(' '.join(map(str, a)))
 
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def partition(array, p, r):
    x = array[r]
    i = p-1
    for j in range(p, r):
        if array[j] <= x:
            i += 1
            array[i], array[j] = array[j], array[i]
    array[i+1], array[r] = array[r], array[i+1]
    a1 = array[:i+1]
    a2 = "[" + str(array[i+1]) +  "]"
    a3 = array[i+2:]
    array = a1[:]
    array.append(a2)
    array += a3
    print(*array)
    return i+1

n = int(input())
array = [int(a) for a in input().split()]
p = partition(array, 0, n-1)

Submission status: Accepted

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

def main() :
    x = numbers[n - 1]
    i = 0
    for j in range(n) :
        if numbers[j] <= x :
            numbers[i], numbers[j] = numbers[j], numbers[i]
            i += 1

    [print(numbers[j] if j != i - 1 else '['+str(numbers[j])+']', end = ' ' if j != n - 1 else '\n') for j in range(n)]

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[i], A[j] = A[j], A[i]

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

b = partition(A, 0, n-1)
A[b] = '[{0}]'.format(A[b])
print(' '.join(map(str, A)))

Submission status: Accepted

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

c = partition(x, 0, n-1)

for i, e in enumerate(x):
    if i == c:
        print '[{0}]'.format(e),
    else:
        print e,

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin


def patition(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(stdin.readline())
data = [int(s) for s in stdin.readline().split()]
pat = patition(data, 0, len(data)-1)
print(*data[:pat], end=' ')
print('[{}]'.format(data[pat]), *data[pat+1:])

Submission status: Accepted

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

if __name__ == "__main__":
    import sys
    N = int(sys.stdin.readline().strip())
    A = [int(e) for e in sys.stdin.readline().strip().split()]
    pivIdx = partition(A, 0, N-1)
    strA = map(str, A)
    strA[pivIdx] = "[{0}]".format(strA[pivIdx])
    print " ".join(strA)

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())
lst = list(map(int, input().split()))

s = partition(lst, 0, n-1)
lst[s] = [lst[s]]
print(*lst)

Submission status: Accepted

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

def Partition(A, p, r):
    i = p - 1
    for j in range(p, r):
        if A[j] <= A[r]:
            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()]
m = Partition(A, 0, n-1)
print(*A[:m], end=' ')
print('[{}]'.format(A[m]), end=' ')
print(*A[m+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(i) for i in input().split()]
r = partition(A, 0, n - 1)

ans = [str(a) for a in A]
ans[r] = "[{}]".format(ans[r])

print(" ".join(ans))

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p-1
    for j in range(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()))

p = 1
r = len(A)-1
par = partition(A,p,r)
for i in range(n):
    if i<par or par<i<n-1:
        print(A[i],end=' ')
    elif i==par:
        print('[',end='')
        print(A[i],end='')
        print(']',end=' ')
    else:
        print(A[i])

Submission status: Accepted

Solution code:
input()
A = [int(x) for x in list(input().split())]
# 数列の最後の値を基準値にする
x = A[-1]
i = -1

r = len(A)
# 数列の一番最後の一個手前まで繰り返す
for j in range(r):
    # print(f"{A=}")
    # print(f"{i=}")
    # print(f"{j=}")
    # print(f"{A[j]=}")
    # 各値がxより大きいか小さいかで振り分ける
    if A[j] <= x:
        i += 1
        # A[i]とA[j]を交換
        A[i], A[j] = A[j], A[i]
    # print(f"{A=}")
    # print()

# 最後尾の基準値を基準値を変更
# A[i+1], A[-1] = A[-1], A[i+1]

# 基準値の前後に[ ]を追加
A[i] = "[" + str(A[i]) + "]"
print(*A)

Submission status: Accepted

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

n = int(input())
S = [*map(int, input().split())]

key = partition(S, 1, n-1)
print(*S[:key],'[{}]'.format(S[key]), *S[key+1:])

Submission status: Accepted

Solution code:
#input: int list A, start p, end r
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]
    output = ""
    for idx, num in enumerate(A):
        if idx == i+1:
            output += "[" + str(num) + "]"
        else:
            output += str(num)
        output += " "
    print(output[:-1])

n = int(input())
list1 = list(map(int, input().split(' ')))
partition(list1, 0, len(list1)-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(i)for i in input().split()]
b=partition(a,0,n-1)
A=[str(i)for i in a]
A[b]="["+A[b]+"]"
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,1):
        if A[j] <= x:
            i += 1
            temp = A[i]
            A[i] = A[j]
            A[j] = temp

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

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

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

    #A = map(str,A)
    A[q] = '[' + str(A[q]) + ']'
    A = map(str,A)
    print(' '.join(A))


main()