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 + 1):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    return i

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

index = partition(A, 0, N - 1)

for i in range(N):
    if i == index:
        print('[{0}]'.format(A[i]), end='')
    else:
        print(A[i], end='')
    if i < N - 1:
        print(' ', end='')

print()

Submission status: Accepted

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

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

p = Partition(A,0,N-1)

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

Submission status: Accepted

Solution code:
# ALDS_1_6_B Partition
import sys


def partition(A, p, r):
    x = A[r]
    i = p
    for j in range(p, r, 1):
        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 sys.stdin.readline().strip().split()]

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

Submission status: Accepted

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

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()))
    i = partition(A, 0, n-1)
    for j in range(n):
        if j:
            print(' ', end='')
        if j == i:
            print('[', end='')
        print(A[j], end='')
        if j == i:
            print(']', end='')
    print()
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
            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

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

ans=partition(a,0,n-1)
a=list(a)
a[ans]="["+str(a[ans])+"]"
print(*a)

Submission status: Accepted

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

p = partition(A, 0, n-1)
A = ["[" + str(A[i]) + "]" if i == p else str(A[i]) for i in range(n)]
print(*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
			A[i],A[j] = A[j],A[i]

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

	return i+1

def test():

	n = int(sys.stdin.readline())
	A = list(map(int,sys.stdin.readline().split()))
	Ptt = Partition(A,0,n-1)

	for i in range(n):

		if i == Ptt:
			print(f"[{A[i]}]",end='')
		else:
			print(f"{A[i]}",end='')

		if i != n-1:
			print(" ",end='')
		else:
			print()


if __name__ == "__main__":
	test()

Submission status: Accepted

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

i = -1

for j in range(n-1):
    if A[j] <= A[n-1]:
        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] = '[' + str(A[i+1]) + ']'

print(*A)

Submission status: Accepted

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

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

num = int(input())
num_list = [int(s) for s in input().split()]

idx = partition(num_list, 0, len(num_list) - 1)

print(*num_list[:idx], end="")
print(" [" + str(num_list[idx]) + "] ", end="")
print(*num_list[idx+1:])

Submission status: Accepted

Solution code:
#パーティション

N = int(input())
*A, = map(int, input().split())
 
def partition(A, p, r):
    x = A[r]
    i = p
    for j in range(p, r):
        if A[j] <= x:
            A[i], A[j] = A[j], A[i]
            i += 1
        
        
    A[i], A[r] = A[r], A[i]
    
    return i
 
j = partition(A, 0, N-1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(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

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

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

    left = A[:q+1]
    p = A[q+1]
    right = A[q+2:]
    print('{0} [{1}] {2}'.format(' '.join(map(str, left)), p, ' '.join(map(str, right))))
             
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
x=A[-1]
i=-1
for j in range(n-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]
print(*A[:i+1], end=' ')
print(f'[{A[i+1]}]', end=' ')
print(*A[i+2:])

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)
for i in range(n):
    if i != 0:
        print(" ", end="")
    if i == q:
        print("[", end="")
    print(A[i], end="")
    if i == q:
        print("]", end="")
print("")

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

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

Submission status: Accepted

Solution code:
def partition(A,p,r):
    x=int(A[r])
    i=p-1
    for j in range(p,r):
        if int(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=[str(i) for i in input().split()]
q=partition(A,0,n-1)
print(' '.join(A[:q]) , '['+A[q]+']',' '.join(A[q+1:]))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a_s = list(map(int, input().split(' ')))
    q = partition(a_s, 0, n-1)

    def display(index, a):
        if index == q:
            return '[{}]'.format(a)
        else:
            return str(a)

    print(' '.join([display(i, a) for i, a in enumerate(a_s)]))


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__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from typing import List


def partition(elements: List[int], start_idx: int, pivot_idx: int) -> int:
    pivot = elements[pivot_idx]
    i = start_idx - 1

    for j in range(start_idx, pivot_idx):
        if elements[j] <= pivot:
            i += 1
            elements[i], elements[j] = elements[j], elements[i]
    elements[i + 1], elements[pivot_idx] = elements[pivot_idx], elements[i + 1]

    return i + 1


if __name__ == "__main__":
    n = int(input())
    elements = list(map(lambda x: int(x), input().split()))

    # pivot_idx = random.randint(0, n - 1)

    pivot_idx = partition(elements, 0, n - 1)

    print(" ".join([f"{elem}" if pivot_idx != idx else f"{[elem]}"
                    for idx, elem in enumerate(elements)]))

Submission status: Accepted

Solution code:

def partition(arr, left, right):
    x = arr[right]
    i = left - 1
    for j in range(left, right):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[right] = arr[right], arr[i + 1]
    return i + 1

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

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

    for i in range(n):
        if i:
            print(' ', end='')
        if i == pos:
            print('[%d]'%(A[i]), end='')
        else:
            print(A[i], end='')

    print()

Submission status: Accepted

Solution code:
from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

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

j=partition(A,0,N-1)
print(*(x if i != j else "[%d]" % x for i, x in enumerate(A)))

Submission status: Accepted

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


if __name__ == '__main__':
    n = int(raw_input())
    A = map(int, raw_input().split())
    q = partition(A, 0, n - 1)
    for i in range(n):
        if i == q:
            print "[%d]" % (A[i]),
        else:
            print 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())
Astr=input().split( )
A=[int(Astr[i]) for i in range(n)]

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

print(*A[0:c],end=" ")
print(f"[{A[c]}]",end=" ")
print(*A[c+1:n])

Submission status: Accepted

Solution code:
N = int(input())
*A, = map(int, input().split())
 
def partition(A, p, r):
    x = A[r]
    i = p
    for j in range(p, r):
        if A[j] <= x:
            A[i], A[j] = A[j], A[i]
            i += 1
    A[i], A[r] = A[r], A[i]
    return i
 
j = partition(A, 0, N-1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(A)))

Submission status: Accepted

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

idx = partition(A, 0, len(A) - 1)

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

print(' '.join(B))

Submission status: Accepted

Solution code:
def partition(arr, p, r):
    x = arr[r]
    i = p - 1
    for j in range(p, r):
        if arr[j] <= x:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[r] = arr[r], arr[i + 1]
    print(" ".join(str(ele) if j != i + 1 else "[{}]".format(ele) for j, ele in enumerate(arr)))


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


def main():
    n = int(input())
    A = list(map(int, input().split()))
    q = partition(A, 0, len(A)-1)
    for i in range(q):
        print(A[i], end=" ")
    print("[{}]".format(A[q]), end=" ")
    for i in range(q+1, n):
        if i == n-1:
            print(A[i])
        else:
            print(A[i], end=" ")


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


pat = partition(A,0,len(A)-1)

for i in range(len(A)):
  if i == pat:
    print("[%d]" %(A[i]),end="")
  else:
    print(A[i],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]
    q = i + 1

    return q


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

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

Submission status: Accepted

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

def main():
    n = int(input())
    A = list(map(int, input().split()))
    A, i = partition(A, 0, len(A))
    for j, a in enumerate(A):
        if j == i:
            print(f"[{a}] ", end="")
        elif j == (len(A)-1):
            print(f"{a}")
        else:
            print(f"{a} ", end="")
        




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

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

print(' '.join(result))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    def swap(a, i, j):
        # list aのi番目の要素とj番目の要素を交換する関数
        k = a[j]
        a[j] = a[i]
        a[i] = k

    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


    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="")
        print(A[i], end="")
        if i==q:
            print("]", end="")
    print()

Submission status: Accepted

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

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

q, A = Partition(A, 0, n-1)
for ni in range(n-1):
    if ni == q:
        print("[" + str(A[ni]) + "]",end = " ")
    else:
        print(A[ni], end = " ")
print(A[n-1])

Submission status: Accepted

Solution code:
from sys import stdin

def partition(A):
    # パーティションの基準
    p = A[-1]

    # 分かれ目を決める
    p_idx = 0
    for i, num in enumerate(A[:-1]):
        if num <= p:
            A[p_idx], A[i] = A[i], A[p_idx]
            p_idx = p_idx + 1
    A[p_idx], A[len(A) - 1] = A[len(A) - 1], A[p_idx]
    return p_idx

def main():
    lines = stdin.readlines()
    nums = [int(n) for n in lines[1].split(' ')]
    p_idx = partition(nums)
    res = [str(n) if i != p_idx else '['+str(n)+']' for i, n in enumerate(nums)];
    print(' '.join(res))

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


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

Submission status: Accepted

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

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

for i in range(n-1):
  if i != idx:
    print(A[i], end=" ")
  else:
    print("[%d]" %A[i], end=" ")
print(A[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


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

Submission status: Accepted

Solution code:
n =  int(input())
nums = list(map(int,input().split(" ")))
ref = nums[-1]

def partition(A,p,refValue):
    i = p
    for j in range(p,len(A)):
        if A[j] <= refValue:
            tmp = A[j]
            A[j] = A[i]
            A[i] = tmp
            i += 1

partition(nums,0,ref)
indexes = [i for i, x in enumerate(nums) if x == ref]

ans = ""
for i in range(n):
    if i == indexes[-1]:
        ans += "[" + str(nums[i]) + "] "
    else:
        ans += str(nums[i]) + " "

print(ans[0:-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#! python3
# partition.py - 配列を特定の値で、分割するアルゴリズム

def partition(array, p, len_array):
    X = array[len_array]
    i = 0 - 1
    for j in range(p, len_array):
        if array[j] <= X:
            i += 1
            tmp = array[i]
            array[i] = array[j]
            array[j] = tmp
    tmp = array[i + 1]
    array[i + 1] = array[len_array]
    array[len_array] = tmp
    
    return i + 1, array
    
len_array = int(input()) - 1
array = [int(i) for i in input().split()]
p = 0 # 配列のスタート位置、今後別の関数で使うことも想定して、変数で渡しておく

index, array = partition(array, p, len_array)
# print(index)
# print(array)
str_array = list(map(str, array))
# print(str_array)
str_array[index] = '[{}]'.format(str_array[index])
print(' '.join(str_array))

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

c = partition(s, 0, n - 1)
for i in range(n):
    s[i] = f"[{s[i]}]" if i == c else s[i]
print(" ".join([str(v) for v in s]))

Submission status: Accepted

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


# l = [3, 9, 1, 5, 10, 0, 2]
# print(partition(l, 0, len(l) - 1))
# print(l)

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

for i in range(n - 1):
    if i == x:
        char = "[" + str(l[i]) + "]"
    else:
        char = str(l[i])
    print(char, end=" ")
print(l[-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 = [int(num) for num in input().split()]
p = 0
r = len(A)-1
q = partition(A, p, r)
A_str = [str(a) for a in A]
A_str[q] = "[" + A_str[q] + "]"
print(" ".join(A_str))

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 printA(A, pos):
    for i in range(len(A)):
        if i == pos:
            print("["+str(A[i])+"]",end="")
        else:
            print(str(A[i]),end="")
        if i == len(A)-1:
            print()
        else:
            print(" ",end="")

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

Submission status: Accepted

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

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

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

S = [str(x) for x in S]

print('{} [{}] {}'.format(' '.join(S[:r]), S[r], ' '.join(S[r+1:])))

Submission status: Accepted

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

n = int(input())
A = list(map(int,input().split()))
pos = partition(A, 0, n - 1)
val = A[pos]
A.pop(pos)
A.insert(pos, [val])
print(*A)

Submission status: Accepted

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


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

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

    return i


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

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

Submission status: Accepted

Solution code:
from sys import stdin

def partition(A, p, r):
    val = A[r]
    i = p-1
    for j in range(p, r):
        if A[j] <= val:
            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().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
res = partition(A, 0, len(A)-1)
A[res] = [A[res]]
print(*A)

Submission status: Accepted

Solution code:
def partition(lst,start,last):
    x = lst[last]
    i = start
    for j in range(start,last):
        if lst[j] <= x:
            lst[i],lst[j] = lst[j],lst[i]
            i += 1
    lst[i],lst[last] = lst[last],lst[i]
    return i

n = int(input())
n_lst = list(map(int,input().split()))
p = partition(n_lst,0,n-1)
str_lst = list(map(str,n_lst))
str_lst[p] = '['+str_lst[p]+']'
print(' '.join(str_lst))

Submission status: Accepted

Solution code:
from typing import List


def partition(A: List[int], p: int, r: int) -> int:
    """パーティション

    A[p, ..., r]を、A[p, ..., q-1]とA[q+1, ..., r]二分割する。
    A[p, ..., q-1]の各要素は A[q]以下とする。
    A[q+1, ..., r]の各要素は A[q]より大きくする。

    Args:
        A (List[int]): 分割対象のリスト
        p (int): 分割対象のリストの先頭のインデックス
        r (int): 分割対象のリストの最後のインデックス

    Returns:
        int: q
    """
    tmp = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= tmp:
            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(A, 0, n - 1)
result = [str(A[i]) if i != q else '[' + str(A[i]) + ']' for i in range(len(A))]
print(' '.join(result))

Submission status: Accepted

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

"""
パーティション
"""

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

def partition(p, r):
    x = aN[r]
    i = p-1
    for j in range(p, r):
        if aN[j] <= x:
            i = i+1
            aN[i], aN[j] = aN[j], aN[i]
    aN[i+1], aN[r] = aN[r], aN[i+1]
    # 基準となった末尾要素のindex
    return i+1

idx = partition(0, N-1)
aN[idx] = '[' + str(aN[idx]) + ']'
print(*aN)

Submission status: Accepted

Solution code:
# coding: utf-8

def partition(A, p, r):
    r = r - 1
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    # A = list(map(str, A))
    # A[i + 1], A[r] = '[{}]'.format(A[r]), A[i + 1]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

if __name__ == "__main__":
    # n = 12
    # A = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]

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


n = int(sys.stdin.readline())
a = [int(v) for v in sys.stdin.readline().split()]
index = partition(a, 0, n - 1)
print(' '.join(f'[{v}]' if i == index else v
               for i, v in enumerate(map(str, 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):
		# 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 - 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)
first = ' '.join(str(a) for a in A[0:p])
second = ' '.join(str(a) for a in A[p+1:n])
print(first + " [" + str(A[p]) + "] " + second)

Submission status: Accepted

Solution code:
def partition(A, p, r):
    i = p - 1
    x = A[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 i
    
n = int(input())
A = list(map(int, input().split()))

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

str_A = list(map(str,A))

str_A[i+1] = "[" + str_A[i+1] + "]"

print(" ".join(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

#input
n=int(input())
data=list(map(int, input().split()))
q=partition(data,0,n-1)
data[q]="["+str(data[q])+"]"
print(*data)

Submission status: Accepted

Solution code:
def partition(li, m, length):
    ini_i = 0
    target = li[length - 1]
    for i, n in enumerate(li[:length - 1]):
        if n <= target:
            li[ini_i], li[i] = li[i], li[ini_i]
            ini_i += 1
    li[ini_i], li[-1] = [li[-1]], li[ini_i]
    print(*li)
length = int(input())
li = [int(n) for n in input().split(" ")]
partition(li, 0, len(li))

Submission status: Accepted

Solution code:
def partition(A,p,r):#A[p]〜A[r-1]までのリストをpartitionする
    x=A[r-1]
    i=p-1
    for j in range(p,r-1):
        if(A[j] <= x):
            i+=1
            A[j],A[i]=A[i],A[j]
    A[i+1],A[r-1]=A[r-1],A[i+1]
    return i+1


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

partition_ind=partition(data,0,n)


data=list(map(str,data))
data[partition_ind]="["+data[partition_ind]+"]"
print(" ".join(data))

Submission status: Accepted

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

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

j = partition(A, 0, N-1)
print(*(str(x) if i != j else "[%d]" % x for i, x in enumerate(A)))

Submission status: Accepted

Solution code:
def partition(n_list, p, r):
    x = n_list[r-1]
    i = p - 1
    for j in range(p, r-1):
        if n_list[j] <= x:
            i += 1
            y = n_list[i]
            n_list[i] = n_list[j]
            n_list[j] = y
    y = n_list[i]
    n_list[r-1] = n_list[i+1]
    n_list[i+1] = f'[{x}]'

    
n = int(input())
n_list = list(map(int, input().split()))
partition(n_list, 0, n)
print(' '.join(list(map(str, n_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

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

i, b=Partition(a, 0, n-1)
print(' '.join(map(str, b[0:i])),'['+str(b[i])+']',' '.join(map(str, b[i+1:])))