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: Wrong Answer

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

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


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

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
last = l[-1]
half1 = []
half2 = []

j = 0
for i in range(n-1):
    if l[j] > last:
        half2.append(l[j])
    else:
        half1.append(l[j])
    l.pop(j)
print(*half1,end = ' ')
print(l,end = ' ')
print(*half2)

Submission status: Wrong Answer

Solution code:
n = int(input())
l = list(map(int,input().split()))
last = l[-1]

j = 0
for i in range(n-1):
    if l[i] >= last:
        for j in range(l[i+1],n-1):
            if l[j] < last:
                l[i] ,l[j] = l[j] ,l[i]
                flg = i
                break
l[-1] = '[%d]'%l[-1]
l[-1],l[flg]=l[flg],l[-1]
print(*l)

Submission status: Wrong Answer

Solution code:

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

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

n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(a[i], end='')
print()

Submission status: Wrong Answer

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_tmp = A[i]
            A[i] = A[j]
            A[j] = A_tmp
        t = A[i+1]
        A[i+1] = A[r]
        A[r] = t


n = int(input())
A = [int(_) for _ in input().split()]
q = partition(0, n-1)
for i in range(n):
    if i:
        print(" ")
    if i == q:
        print("[")
    print(A[i])
    if i == q:
        print("]")
print("\n")

Submission status: Wrong Answer

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

s = 0
last = a[-1]

for i in range(n-1):
    if a[i] <= last:
        tmp = a[i]
        a[i] = a[s]
        a[s] = tmp
        s += 1
tmp = a[-1]
a[-1] = a[s]
a[s] = tmp

for i in range(1, s):
    print(a[i], end=' ')
print('[' + str(a[s]) + '] ', end='')
for i in range(s+1, n-1):
    print(a[i], end=' ')
print(a[n-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_n = list(map(int,input().split()))
x = lst_n[n-1]
left  = []
right = []

for num in lst_n:
    if num < x:
        left.append(str(num))
    elif num > x:
        right.append(str(num))
print('{} [{}] {}'.format(' '.join(left),str(x),' '.join(right)))

Submission status: Wrong Answer

Solution code:
n = int(input())
lst_n = list(map(int,input().split()))
x = lst_n[n-1]
left  = []
right = []
i = -1
for j in range(0,n-1):
    if lst_n[j] <= x:
        i += 1
        lst_n[i],lst_n[j] = lst_n[j],lst_n[i]
i += 1
lst_n[i],lst_n[n-1] = lst_n[n-1],lst_n[i]

ans = ['['+str(k)+']' if k == x else str(k) for k in lst_n]
print(' '.join(ans))

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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
            A[i],A[j] = A[j],A[i]
            print("swap:",i,j)
    A[i+1],A[r] = A[r],A[i+1]
    print('swap:',i+1,r)
    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)-2):
    print(data[i],end=" ")
print(data[len(data)-1])

Submission status: Wrong Answer

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]
            print("swap:",i,j)
    A[i+1],A[r] = A[r],A[i+1]
    print('swap:',i+1,r)
    return i+1

n = int(input())
st = input()
data = list(map(int,st.split()))

mid = Partition(data,0,len(data)-1)
for i in data:
    print(i)
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: Wrong Answer

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 i in range(len(S)):
        if S[i] == x: print "["+str(S[i])+"]",
        else: print S[i],

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

Submission status: Wrong Answer

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: Wrong Answer

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]
            print(a)           
        # a[i + 1], a[-1] = a[-1], a[i + 1]
        print(a)
        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: Wrong Answer

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()))
i = partition(A, 0, A[len(A) - 1])
print(' '.join([str(a) if a != A[i] else '[{}]'.format(str(a)) for a in A]))

Submission status: Wrong Answer

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, A[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: Wrong Answer

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, 1, len(A) - 1)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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


    print(p)

    # ???????????¨???
    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: Wrong Answer

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: Wrong Answer

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

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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]
    return i + 1


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


main()

Submission status: Wrong Answer

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]
    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: Wrong Answer

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


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


if __name__ == '__main__':
    n = int(input())
    ns = [int(e) for e in input().split()]
    idx, ns = partition(n, ns)
    ns = [str(n) for n in ns]
    ns[idx] = '[{}]'.format(ns[idx])
    print(" ".join(ns))

Submission status: Wrong Answer

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


def partition(n, ns):
    r = len(ns) - 1
    x = ns[r]
    i = -1
    for j in range(1, 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]
    idx, ns = partition(n, ns)
    ns = [str(n) for n in ns]
    ns[idx] = '[{}]'.format(ns[idx])
    print(" ".join(ns))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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(B)
    print(" ".join(map(str, B[:p])) + " [" + str(B[p]) + "] " + " ".join(map(str, B[p+1:])))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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-1):
        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: Wrong Answer

Solution code:
n = int(raw_input())
a = map(int, raw_input().split())
print a
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]
            print A
    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: Wrong Answer

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: Wrong Answer

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):
    flag = False
    for y in a[:-1]:
        if x != y:
            print(y, end=" ")
        else:
            print("[" + str(y) + "]", end=" ")
            flag = True
    if flag:
        print(a[-1])
    else:
        print("[" + str(a[-1]) + "]", end=" ")


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: Wrong Answer

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]
    return i+1

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

for a in array:
    if a == buff[-1]:
        print("[{0}]".format(a), end=" ")
    elif a == array[-1]:
        print(a)
    else:
        print(a, end=" ")

Submission status: Wrong Answer

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+1:]
    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: Wrong Answer

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(b)
print(' '.join(map(str, A)))

Submission status: Wrong Answer

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: Wrong Answer

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, data[-1])
print(*data[:pat], end=' ')
print('[{}]'.format(data[pat]), *data[pat+1:])

Submission status: Wrong Answer

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()]
print(data[-1])
pat = patition(data, 0, len(data)-1)
print(*data[:pat], end=' ')
print('[{}]'.format(data[pat]), *data[pat+1:])

Submission status: Accepted

Solution code:
def printAns( A, index ):
    n = len(A)
    for i in range(0, index):
        print( str( A[i] ), end=" ")
    print( "[" + str(A[index]), end="] ")
    for i in range(index+1, n-1):
        print( str( A[i] ), end=" ")
    print( str( A[n-1] ) )

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

def main():
    n = int( input() )
    A = [int(x) for x in input().split()]
    index = partition(A, 0, n-1)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys


def partition(A, p, r):
    # 要素の最後をxに代入
    x = A[r]
    i = p-1
    ans = ""

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

    tmpB = A[i+1]
    A[i+1] = A[r]
    A[r] = tmpB
    for j in range(n):
        if j > 0:
            ans += " "
        if j == i+1:
            ans += "["+str(A[j])+"]"
        else:
            ans += str(A[j])
    print(ans)


n = int(input())
A = list(map(int, input().split()))
r = len(A)-1
p = 0
partition(A, p, r)
# for i in range(n):
#     if A[i] == A[r]:
#         sys.stdout.write('[' + str(A[i])+']' + ' ')
#     else:
#         sys.stdout.write(str(A[i]) + ' ')
# 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())
l = list(map(int, input().split()))
i = partition(l, 0, n - 1)
l[i] = "[%d]"%l[i]
print(*l)

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:
			i += 1
			swap(a, i, j)
	swap(a, i + 1, r)
	return i + 1

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

n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(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
			swap(a, i, j)
	swap(a, i + 1, r)
	return i + 1

def swap(a, i, j):
	tmp = a[i]
	a[i] = a[j]
	a[j] = tmp
	
n = int(input())
a = list(map(int, input().split()))
idx = partition(a, 0, len(a) - 1)
if idx == 0:
	print('[' + str(a[0]) + ']', end='')
else:
	print(a[0], end='')
for i in range(1, n):
	print(' ', end='')
	if idx == i:
		print('[' + str(a[i]) + ']', end='')
	else:
		print(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 = i+1
            A[i],A[j] = A[j],A[i]
    A[i+1],A[r] = A[r],A[i+1]
    for j,k in enumerate(A):A[j] = str(k)
    A[i+1] = "["+A[i+1]+"]"
    return i+1

n = int(input())
A = [int(i) for i in input().split()]
ans = ""
partition(A,0,n-1)
for i in A:ans+=i+" "
print(ans[:-1])

Submission status: Accepted

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

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
        
r = partition(0, N-1)
print(" ".join(map(str, A[:r]))+" ["+str(A[r])+"] "+" ".join(map(str, A[r+1:N])))

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)

out = [str(a) for a in A]
out[q] = '[' + out[q] + ']'
print(' '.join(out))

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)
print(*A[:i], '[{}]'.format(A[i]), *A[i + 1:])

Submission status: Accepted

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


n = int(input())
A = [int(_) for _ in input().split()]
q = partition(0, n-1)
for i in range(n):
    if i:
        print(" ", end="")
    if i == q:
        print("[", end="")
    print(A[i], end="")
    if i == q:
        print("]", end="")
print("")

Submission status: Accepted

Solution code:
def swap(a,i,j):
	t=a[i]
	a[i]=a[j]
	a[j]=t

def partition(a,p,r):
	x=a[r]
	i=p-1
	for j in range(r):
		if a[j]<=x:
			i+=1
			swap(a,i,j)
	swap(a,i+1,r)
	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==p:print('[',end='')
	print(a[i],end='')
	if i==p:print(']',end='')
	if i!=n-1:print(' ',end='')
print()

Submission status: Accepted

Solution code:
def partition(array, first, end):
    criteria = array[end]
    i_ins = first
    for i_cur in range(first, end):
        if array[i_cur] <= criteria:
            array[i_ins], array[i_cur] = array[i_cur], array[i_ins]
            i_ins += 1
    array[i_ins], array[end] = array[end], array[i_ins]
    return i_ins


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    i_ins = partition(array, 0, n-1)
    outputtxt = ""
    if i_ins != 0:
        outputtxt += " ".join([str(x) for x in array[:i_ins]]) + " "
    outputtxt += "[{}]".format(array[i_ins])
    if i_ins < n-1:
        outputtxt += " " + " ".join([str(x) for x in array[i_ins + 1:]])
    print(outputtxt)
    return


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


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

    return i


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
  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()))
mid = partition(A,0,n-1)
print(' '.join(map(str,A[:mid])),'['+str(A[mid])+']',' '.join(map(str,A[mid+1:])))

Submission status: Accepted

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

s = 0
last = a[-1]

for i in range(n-1):
    if a[i] <= last:
        tmp = a[i]
        a[i] = a[s]
        a[s] = tmp
        s += 1
tmp = a[-1]
a[-1] = a[s]
a[s] = tmp

for i in range(0, s):
    print(a[i], end=' ')
print('[' + str(a[s]) + '] ', end='')
for i in range(s+1, n-1):
    print(a[i], end=' ')
print(a[n-1])

Submission status: Accepted

Solution code:
def InputData():
    
    sequence_len = int(input())
    sequence = list(map(int, input().split(" ")))

    return sequence_len, sequence

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

def PrintOut(sequence):
    print(' '.join( map(str, sequence)))

def main():
    [sequence_len, sequence] = InputData()
    q = partition(sequence, 0, sequence_len-1)
    sequence[q] = "[" + str(sequence[q]) + "]"
    PrintOut(sequence)

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
lst_n = list(map(int,input().split()))
x = lst_n[n-1]
left  = []
right = []
i = -1
for j in range(0,n-1):
    if lst_n[j] <= x:
        i += 1
        lst_n[i],lst_n[j] = lst_n[j],lst_n[i]
i += 1
lst_n[i],lst_n[n-1] = lst_n[n-1],lst_n[i]

ans = ['['+str(lst_n[k])+']' if k == i else str(lst_n[k])
        for k in range(len(lst_n))]
print(' '.join(ans))