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


def partition(a, left, right):
    standard = a[right]
    cnt = left
    for i in range(left, right+1):
        if i == right:
            if a[i] <= standard:
                a[i],a[cnt] = a[cnt], [a[i]] 
        elif a[i] <= standard:
            a[cnt],a[i] = a[i], a[cnt]
            cnt += 1
    print(*a)
    return cnt

partition(a, 0, len(a)-1)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    # print(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(A)
for i, a in enumerate(A):
    if i == q:
        print('[', end='')
    print(a, end='')
    if i == q:
        print(']', end='')
    if i < len(A)-1:
        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
			A[i],A[j] = A[j],A[i]

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

	return i+1

if __name__ == '__main__':

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

	end = len(A)
	p = 0
	r = end - 1
	cnt = partition(A,p,r)

	ans = []
	for i,j in enumerate(A):
		if i == cnt:
			ans.append("["+str(j)+"]")
		else:
			ans.append(str(j))

	print(" ".join(ans))

Submission status: Accepted

Solution code:
input()
a=raw_input().split()
b=a.pop()
i=0
for j in range(len(a)):
    if int(a[j])<=int(b):
        a[i],a[j]=a[j],a[i]
        i+=1
a[i],b="["+b+"]",a[i]
print " ".join(a+[b])

Submission status: Accepted

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

n = input()
a = list(map(int, input().split()))
q = partition(a, 0, len(a) - 1)
a[q] = '[{}]'.format(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
            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, len(a) - 1)
a[q] = '[{}]'.format(a[q])
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 i + 1

n = int(raw_input())
A = map(int, raw_input().split())
q = partition(A, 0, n-1)
s = ""
for i, x in enumerate(A):
    if i == q:
        s += "[" + str(x) + "]"
    else:
        s += str(x)
    s += " "
print s[:len(s)-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 = input()
a = map(int, raw_input().split())
r = partition(a,0,n-1)
print " ".join(map(str,a[:r])) + " [" + str(a[r]) + "] " + " ".join(map(str,a[r+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
      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 = sys.stdin.readline()
  for line in sys.stdin:
    items = line.strip().split()
    items = [ int(item) for item in items ]
    target = partition(items, 0, len(items) - 1)
    items[target] = "[%s]" % (items[target])
    print " ".join([ str(item) for item in items ])

Submission status: Accepted

Solution code:
import sys

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 = sys.stdin.readline()
n = int(n)

data = sys.stdin.readline()
data_list = data.split(" ")

data_list = map(int, data_list)

co = partition(data_list, 0, n-1)

data_list = map(str, data_list)

data_list[co] = "[{0}]". format(data_list[co])

print " ".join(data_list)

Submission status: Accepted

Solution code:
import sys


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, A



if __name__ == "__main__":
    lines = sys.stdin.readlines()
    N = int(lines[0])
    nums = map(int, lines[1].split(" "))
    (i, A) = partition(nums, 0, N-1)
    A = map(str, A)
    A[i] = "[{0}]".format(A[i])
    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

n=int(input())
s=input()
a=list(map(int,s.split()))
m=partition(a,0,n-1)
a=list(map(str,a))
a[m]="[%s]"%(a[m])
print(" ".join(a))

Submission status: Accepted

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

def main():
    num = raw_input()
    num_list = raw_input().split()
    num_list = map(int, num_list)

    index = partition(num_list, 0, len(num_list)-1)
    num_list = map(str, num_list)
    num_list[index] = "[" + num_list[index] + "]"
    print " ".join(num_list)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(raw_input())

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

i = 0
r = A[-1]
for j in range(N):
    if A[j] <= r:
        A[i], A[j] = A[j], A[i]
        i += 1

print "%s [%d] %s" % (' '.join(map(str, A[:i-1])), A[i-1], ' '.join(map(str, A[i:])))

Submission status: Accepted

Solution code:
n = int(raw_input())
A_str = raw_input().split(" ")
A = map(int, A_str)

i = 0

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

print "%s [%d] %s" % (" ".join(map(str, A[:i-1])), A[i-1], " ".join(map(str, A[i:])))

Submission status: Accepted

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

    
    
if __name__ == "__main__":
    num = int(raw_input())
    num_list = raw_input().strip().split()
    num_list = map(int, num_list)
    i = partition(num_list, 0, len(num_list))
    num_list = map(str, num_list)
    data = ""
    for j in range(len(num_list)):
        if j == i:
            data += "[" + num_list[j] + "] "
        else:
            data += num_list[j] + " "
    print data[:-1]

Submission status: Accepted

Solution code:
def pertition(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(raw_input())
a = raw_input()
l = []
l = a.split(" ")
for i in range(len(l)):
	l[i] = int(l[i])
i = pertition(l, 0, n - 1)
l[i] = "[" + str(l[i]) + "]"
print " ".join(map(str, l))

Submission status: Accepted

Solution code:
#!/usr/bin/python
#_*_coding:utf-8_*_


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

    return i + 1, array


def main():
    n = raw_input()
    num = raw_input()
    array = num.strip().split(" ")
    array = map(int, array)
    index, new_array = partition(array, 0, len(array) - 1)
    new_array = map(str, new_array)
    new_array[index] = "[" + new_array[index] + "]"
    print " ".join(new_array)

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

mid = Partition(data,0,len(data)-1)
for i in range(0,mid):
    print(data[i],end=" ")
print("[{0}] ".format(data[mid]),end="")
for i in range(mid+1,len(data)-1):
    print(data[i],end=" ")
print(data[len(data)-1])

Submission status: Accepted

Solution code:
n = int(raw_input())
S = map(int,raw_input().strip().split(' '))

def partition(S,p,r):
    x = S[r]
    i = p-1
    for j in range(p,r):
        if S[j] <= x:
            i += 1
            S[j],S[i]=S[i],S[j]
    S[i+1],S[r]=S[r],S[i+1]
    for j in range(len(S)):
        if j == i+1: print "["+str(S[j])+"]",
        else: print S[j],

partition(S,0,len(S)-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
            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(" ".join(a))

Submission status: Accepted

Solution code:
"""Partition."""

def partition(A, p, r):
    """Divide list A into A[p:q-1] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].

    Default value of p is 0.
    The number as a refernce of the division is A[r].
    
    Return the index q.
    """

    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 = int(input()) - 1

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

q = partition(A, 0, r)

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

Submission status: Accepted

Solution code:
#coding:utf-8
#1_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
            A[i], A[j] = A[j], A[i]
    A[i + 1], A[r] = A[r], A[i + 1]
    return i + 1

n = int(input())
numbers = list(map(int, input().split()))
x = partition(numbers, 0, n - 1)
numbers[x] = "[{}]".format(numbers[x])
print(*numbers)

Submission status: Accepted

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

r = n - 1
x, i = a[r], -1
for j in range(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]

a[i] = '[' + str(a[i]) + ']'
print(*a)

Submission status: Accepted

Solution code:
class Partition:
    def partion(self, 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]
        # a[i + 1], a[-1] = a[-1], a[i + 1]
        return((a, i))

if __name__ == '__main__':
    n = int(input().rstrip())
    a = [int(x) for x in input().rstrip().split(" ")]
    x = Partition()
    a, i = x.partion(a, 0, n)
    res = []
    for j in range(len(a)):
        if j == i:
            res.append("[{}]".format(a[j]))
        else:
            res.append(str(a[j]))
    print(" ".join(res))

Submission status: Accepted

Solution code:
class Partition:
    def partion(self, 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().rstrip())
    a = [int(x) for x in input().rstrip().split(" ")]
    x = Partition()
    i = x.partion(a, 0, n-1)
    a = [str(i) for i in a]
    a[i] = "[{}]".format(a[i])
    print(" ".join(a))

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 xrange(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

def main():
    i = partition(A, 0, n-1)
    print ' '.join(map(str, A[:i])), '[{}]'.format(A[i]), ' '.join(map(str,A[i+1:]))
    return 0

main()

Submission status: Accepted

Solution code:
N = input()
A = map(int,raw_input().split())
temp = 0
q = 0
r = N-1

for i in range(N-1):
    if A[i] <= A[r] and q < i:
        A[q],A[i] = A[i],A[q]
        q += 1
    elif A[i] <= A[r]:
        q += 1


A[r],A[q] = A[q],A[r]
i = 0
for elem in A:
    if i == q:
        print("["+str(elem)+"]"),
    else:
        print(elem),
    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

input()
A = list(map(int, input().split()))
index = partition(A, 0, len(A) - 1)
for i in range(len(A)):
    if i == index:
        A[i] = '[{}]'.format(A[i])
    else:
        A[i] = str(A[i])
print(' '.join(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 i+1

n=input()
A=map(int,raw_input().split())
base_i=partition(A,0,n-1)
base="["+str(A[base_i])+"]"
A[base_i]=base
A=map(str,A)
print(" ".join(A))

Submission status: Accepted

Solution code:
import sys

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)
    swap(A, i + 1, r)

    return i + 1

def swap(array, i, j):
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

if __name__ == "__main__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    q = partition(A, 0, len(A) - 1)

    pre = ""
    suf = ""
    for i in range(len(A) - 1):
        if i == q:
            pre = "["
            suf = "]"
        print pre + str(A[i]) + suf,
        pre = ""
        suf = ""
    print A[i + 1]

Submission status: Accepted

Solution code:
import sys

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__":
    lines = sys.stdin.readlines()
    A = map(int, lines[1].split())
    q = partition(A, 0, len(A) - 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 += 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, len(A) - 1)

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

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

n = int(raw_input())
A = map(int, raw_input().split())
q = partition(A, 0, n-1)
print " ".join(map(str, A[:q])) + " [%d] " %(A[q]) + " ".join(map(str, A[q+1:]))

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):
		# A[j] > x???????????????????????????j????¢???????????????????
		if A[j] <= x:
			# A[j] <= x(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

if __name__ == '__main__':
	#MAX = 100000
	#A = [0] * MAX

	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] 
    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

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

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 = list(map(int, input().split()))
idx = partition(0, n-1)
a[idx] = [a[idx]]
print(*a)

Submission status: Accepted

Solution code:
import sys

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
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
    tmp = x
    A[r - 1] = A[i + 1]
    A[i + 1] = '[{}]'.format(tmp)

n = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))

partition(A, 0, n)

print(*A)

Submission status: Accepted

Solution code:
#coding:UTF-8

def Partition(A,n):
    x=A[n-1]
    i=0
    ans=""
    for j in range(n-1):
        if A[j]<=x:
            swap=A[j]
            A[j]=A[i]
            A[i]=swap
            i+=1
    swap=A[n-1]
    A[n-1]=A[i]
    A[i]=swap
    for j in range(n):
        if j>0:
            ans+=" "
        if j==i:
            ans+="["+str(A[j])+"]"
        else:
            ans+=str(A[j])
    print(ans)
            
 
    
if __name__=="__main__":
    n=int(input())
    A=input().split(" ")
    for i in range(n):
        A[i]=int(A[i])
    Partition(A,n)

Submission status: Accepted

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

def partition(target_list):
    x = target_list[-1]
    i = -1

    for j in range(len(target_list))[:-1]:
        if target_list[j] <= x:
            i = i+1
            tmp = target_list[i]
            target_list[i] = target_list[j]
            target_list[j] = tmp
    tmp = target_list[-1]
    target_list[-1] = target_list[i + 1]
    target_list[i + 1] = tmp
    
    return  i + 1

def convert(l):
    return " ".join([str(n) for n in l])

if __name__ == "__main__":
    n_list = int(input())
    target_list = [int(n) for n in input().split()]

    center_index = partition(target_list)
    print(convert(target_list[:center_index]) + " ["+ str(target_list[center_index]) + "] " + convert(target_list[center_index + 1:]))

Submission status: Accepted

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


import sys


def partition(A, p, r):
    x = A[r]
    i = p - 1
    assert p <= r
    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 dict(array=A, cursor=i + 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    raw_result = partition(A=array, p=0, r=array_length - 1)
    array_result = raw_result['array']
    cursor = raw_result['cursor']
    array_result[cursor] = '[' + str(array_result[cursor]) + ']'
    print(*array_result)

Submission status: Accepted

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


import sys


def partition(A, p, r):
    x = A[r]
    i = p - 1
    assert p <= r
    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 dict(array=A, cursor=i + 1)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    array_length = int(_input[0])
    array = list(map(int, _input[1].split()))
    assert len(array) == array_length
    raw_result = partition(A=array, p=0, r=array_length - 1)
    array_result, cursor = raw_result['array'], raw_result['cursor']
    array_result[cursor] = '[' + str(array_result[cursor]) + ']'
    print(*array_result)

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




if __name__ == '__main__':
    # ??????????????\???
    # A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

    # ???????????????
    p = partition(A, 0, len(A))

    # ???????????¨???
    left = A[:p+1]
    partition = A[p+1]
    right = A[p+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))

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




if __name__ == '__main__':
    # ??????????????\???
    # A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

    # ???????????????
    p = partition(A, 0, len(A)-1)

    # ???????????¨???
    left = A[:p+1]
    partition = A[p+1]
    right = A[p+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))

Submission status: Accepted

Solution code:
def partition(A, p, r):
    """
    ???????????????????????????????????????A[r]?????°?????????????????????????????????????????????A[r-1]??¨?´??????????????????§??¨???
    """
    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__':
    # ??????????????\???
    # A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    num_of_data = int(input())
    A = [int(x) for x in input().split(' ')]

    # ???????????????
    p = partition(A, 0, len(A)-1)  # ????????????????????????????????????len(A)??§?????????-1???????????????????????????

    # ???????????¨???
    left = A[:p]
    partition = A[p]
    right = A[p+1:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), partition, ' '.join(map(str, right))))

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
            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 = input()
    A = map(int,raw_input().split())
    pos = partition(A,0,n-1)
    A = map(str,A)
    A[pos] = "["+A[pos]+"]"
    print " ".join(A)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

n = int(input())
A = [int(x) for x in input().split()]
standard = partition(A)
for i in range(len(A)):
    if i == standard:
        print("[{}]".format(A[i]), end=' ')
    elif i != standard and i != len(A)-1:
        print(A[i], end=' ')
    else:
        print(A[i])

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

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

    return i + 1

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

for (i, a) in enumerate(A):
    if i == edge:
        print("[" + str(a) + "]", end = "")
    else:
        print(a, end = "")

    if i != n - 1:
        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
            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().strip())
    AA = [int(a) for a in input().strip().split()]
    i = partition(AA, 0, N - 1)
    _str = ' '.join([str(a) for a in AA[:i]]) + \
           ' [{}] '.format(AA[i]) + \
            ' '.join([str(a) for a in AA[i+1:]])
    print(_str)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x, i = A[r], 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()))
s = partition(A,0,n-1)
print(*A[:s],end = ' ')
print([A[s]],end = ' ')
print(*A[s+1:])

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p 
    j = p+1
    while i < r:
        if A[i] <= x:
            i += 1
            if i == j:
                j += 1
        else:
            while j <= r:
                if A[j] <= x:
                    if j == r:
                        temp = A[j]
                        A[j] = A[i]
                        A[i] = "[{}]".format(temp)
                        i += 1
                        break 
                    temp = A[j]
                    A[j] = A[i]
                    A[i] = temp
                    i += 1
                    break
                else:
                    j += 1
            else:
                i+=1
                break
    return A
    
    
n = int(input())
A = list(map(int,input().split()))
print(*partition(A,0,n-1))

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x = A[r]
    i = p 
    j = p+1
    while i < r:
        if A[i] <= x:
            i += 1
            if i == j:
                j += 1
        else:
            while j <= r:
                if A[j] <= x:
                    if j == r:
                        temp = A[j]
                        A[j] = A[i]
                        A[i] = "[{}]".format(temp)
                        i += 1
                        i = r
                        break 
                    temp = A[j]
                    A[j] = A[i]
                    A[i] = temp
                    i += 1
                    break
                else:
                    j += 1
    return A
    
    
n = int(input())
A = list(map(int,input().split()))
print(*partition(A,0,n-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[j],A[i] = A[i],A[j]
            i += 1
    A[r],A[i] = A[i],A[r]
    return i

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

Submission status: Accepted

Solution code:
def partition(n,a,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  
  for k in range(i+1):
    print(a[k],end=" ")
    
  print("[{}]".format(x),end=" ")
  
  for k in range(i+2,r):
    print(a[k],end=" ")
    
  print(a[r])

n = int(input())
a = list(map(int,input().split()))
partition(n,a,0,len(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 = int(input())
A = list(map(int, input().split()))

q = partition(A, 0, len(A) - 1)
result = []
for i in range(len(A)):
  s = "[" + str(A[i]) + "]" if i == q else str(A[i])
  result.append(s)
print(" ".join(result))

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


def main():
    n = int(input())
    A = [int(e) for e in input().split()]
    p = 0
    idx = partition(A, p, n - 1)
    A = [str(e) for e in A]
    A[idx] = "[{}]".format(A[idx])
    return " ".join(A)


print(main())

Submission status: Accepted

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


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


if __name__ == '__main__':
    n = int(input())
    ns = [int(e) for e in input().split()]
    # n = 12
    # ns = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    r = len(ns) - 1
    idx, ns = partition(ns, 0, r)
    ns = [str(n) for n in ns]
    ns[idx] = '[{}]'.format(ns[idx])
    print(" ".join(ns))

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()))
#print(partition(A, 0, len(A)-1), A)
k = partition(A, 0, len(A)-1)
#print(k)
#print(A)
for i in range(len(A)):
    if i == k:
        print('['+str(A[i])+']', end=' ')
    elif i == n-1:
        print(A[i])
    else:
        print(A[i], end=' ')

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()))
i = partition(A, 0, n-1)
A[i] = "["+str(A[i])+"]"
print(*A)