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:
import sys
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j, n in enumerate(A[:-1]):
        if n <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1

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

Submission status: Accepted

Solution code:
def partition(arr, start, end):
    criteria = arr[end]
    idx1 = start
    for idx2 in range(start, end):
        if arr[idx2] <= criteria:
            arr[idx1],arr[idx2] = arr[idx2],arr[idx1]
            idx1 += 1
    arr[idx1],arr[end] = arr[end],arr[idx1]
    return idx1


num = int(input())
arr = list(map(int, input().split()))
criteria = partition(arr, 0, num-1)
arr[criteria] = "[" + str(arr[criteria]) + "]"
print(" ".join(map(str, arr)))

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue

# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall
# from decimal import Decimal
# from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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[R] = '[' + str(A[R]) + ']'  # 基準となる要素
    A[i + 1], A[R] = A[R], A[i + 1]
    return i + 1


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    partition(A, 0, N - 1)
    print(*A)


if __name__ == '__main__':
    main()

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

    

if __name__ == '__main__':
    n = int(input())
    A = list(map(int, input().rstrip().split()))
    A, index = partition(A, 0, len(A)-1)
    A_str = ''
    for i in range(len(A)):
        if i == index:
            A_str = A_str + ' [' + str(A[i]) + ']'
        else:
            A_str = A_str + ' '+ str(A[i])
    print(A_str.strip().rstrip())

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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


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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

x = A[-1]

i = 0
j = 0
while i < len(A) - 1:
    if A[i] <= x:
        A[j], A[i] = A[i], A[j]
        j += 1
    i += 1
A[-1], A[j] = A[j], A[-1]
A[j] = "[" + str(A[j]) + "]"

A = list(map(str, A))
print(" ".join(A))in(list(map(str, A)))

Submission status: Accepted

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

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


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

print(*A[:q], f"[{A[q]}]", *A[q + 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


def main():
    N = int(sys.stdin.readline().rstrip())
    A = [int(x) for x in sys.stdin.readline().split()]

    q = partition(A, 0, N - 1)
    new_A = list(str(x) for x in A)
    new_A[q] = "[" + new_A[q] + "]"
    print(" ".join(new_A))


main()

Submission status: Accepted

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

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

  def swap(a, b):
    tmp=A[a]
    A[a]=A[b]
    A[b]=tmp

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

  p=partition(A, 0, n - 1)
  for i in range(len(A)):
    if i==p:
      print('['+str(A[i])+']', end=' ')
    elif i==len(A)-1:
      print(A[i])
    else:
      print(A[i], end=' ')

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()))
MAXAI = 100000

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

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

for i in range(n):
    if i == r:
        print('[', a[i], ']', sep='', end='')
    else:
        print(a[i], end='')
    if i < n-1:
        print(' ', end='')
print()

Submission status: Accepted

Solution code:
import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]




import random
from typing import TypeVar, Callable, List, Tuple, Union
T = TypeVar('T')
Num = Union[int, float]



def nth_element(L: List[Num], begin: int=-1, end: int=-1, key=lambda x: x) -> int:
    """
    pivot = L[pivot_ind] とする。 'pivot 未満の要素 ... pivot ... pivot 以上の要素' となるよう L を破壊的に並び替える。(O(n))
    最後に基準値の pivot がおさまった場所のインデックスを返す。
    begin <= pivot_ind < end の要請はあるが、begin, end の指定により L[begin:end] に対象を絞り L[pivot_ind] 未満 / 以上に並べ替えることもできる。

    Args:
        L (list)
        pivot_ind (int)
        begin, end (int): L の [begin, end) 半開区間を考える。デフォルトでは L[0:n] となる

    Returns:
        int: 最後に基準値の pivot がおさまった場所のインデックス

    Examples:
        >>> seq = [1, 9, 2, 7, 5, 6, 4, 8, 3, 0]
        >>> nth_element(seq, 4)
        5
        >>> seq
        [1, 2, 0, 4, 3, 5, 7, 8, 9, 6]
        >>> nth_element(seq, 3, begin=3, end=9)
        4
        >>> seq
        [1, 2, 0, 3, 4, 5, 7, 8, 9, 6]
    """
    if begin == -1 and end == -1:
        begin, end = 0, len(L)
    pivot_ind = end-1

    # [begin]...[end] が対象範囲である
    end -= 1

    pivot = L[pivot_ind]
    L[pivot_ind], L[end] = L[end], L[pivot_ind]
    # i: 確定済みのバッファ先頭。ループ開始時点で pivot 未満であると判明しているところの先端を指す。
    i = begin - 1
    # j: 斥候。ループ開始時にここより前は検査済となっている。
    # begin ... end - 1 を動けば良い。(end は最初の swap の結果 pivot 自身がいるため探索しなくて良い)
    for j in range(begin, end):
        if key(L[j]) <= key(pivot):
            i += 1
            L[j], L[i] = L[i], L[j]
    L[i+1], L[end] = L[end], L[i+1]
    return i+1


if __name__ == "__main__":
    n = int(input())
    L = list(map(int, input().split()))
    ind = nth_element(L, 0, n)
    if L[:ind]:
        print(*L[:ind], sep=' ', end=' ')
    print('[{}]'.format(L[ind]), end='')
    if L[ind+1:]:
        print(' ', end='')
    print(*L[ind+1:], sep=' ')

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

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)

A[q] = [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 += 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 resolve():
    n = int(input())
    A = [int(i) for i in input().split()]
    ans = partition(A, 0, len(A) - 1)
    print(*A[:ans], "[{}]".format(A[ans]), *A[ans + 1:])


resolve()

Submission status: Accepted

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

  for j in range(p, len(A)):
    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()))
cnt = partition(A, 0, len(A)-1)

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:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**10
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    n = I()
    A = LI()

    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)
    A_str = [str(i) for i in A]
    A_str[q] = '[' + A_str[q] + ']'
    print(*A_str)

if __name__ == '__main__':
    resolve()

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

idx = partition(A, 0, len(A)-1)
A[idx] = [A[idx]]
print(*A)

Submission status: Accepted

Solution code:
# coding: utf-8
# パーティション


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

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


if __name__ == "__main__":
    n = int(input())

    A = [int(i) for i in input().split()]
    x = A[n - 1]
    p = partition(A, 0, n - 1)
    A = ['[' + str(v) + ']' if i == p else str(v) for i, v in enumerate(A)]
    print(' '.join(A))

Submission status: Accepted

Solution code:
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy

def Partition(A,p,r):
    x = A[r]
    i = p - 1
    for j in range(p,r):
        if A[j] <= x:
            i = i + 1
            tmp = A[i]
            A[i] = A[j]
            A[j] = tmp
    tmp2 = A[i+1]
    A[i+1] = A[r]
    A[r] = tmp2
    return i + 1
if __name__ == "__main__":
    n = int(input())
    A = list(map(int,input().split()))
    q = Partition(A,0,n-1)
    for i in range(n):
        if i:
            print(" ",end = "")
        if i == q:
            print("[",end = "")
        print(str(A[i]),end = "")
        if i == q:
            print("]",end = "")
    print()

Submission status: Accepted

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

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

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

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:
# coding: utf-8
# Your code here!

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(e) for e in input().split()]
b = partition(A,0,n-1)
A[b] = f"[{A[b]}]"
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 = [int(i) for i in input().split()]
q = partition(a, 0, n - 1)
a[q] = f"[{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
            esc = a[i]
            a[i] = a[j]
            a[j] = esc
    esc = a[i + 1]
    a[i + 1] = a[r]
    a[r] = esc
    return i + 1


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

index = partition(A, 0, n - 1)
left = A[:index]
center = A[index]
right = A[index + 1:]
print(*left, '[' + str(center) + ']', *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 = 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)
a[q] = f"[{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 += 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 = A[-1]
q = partition(A,0,n-1)
s = list(map(str,A))
print(" ".join(s[:q])+" [{}] ".format(s[q])+" ".join(s[q+1:]))

Submission status: Accepted

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

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

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

outputs = [ "["+str(A[i]) + "]" if i == x else str(A[i]) for i in range(len(A))]
print(" ".join(outputs))

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    a=list(map(int,input().split()))
    return n,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]
    a[i+1],a[r]=a[r],a[i+1]
    return i+1

def main(n,a):
    ans=partition(a,0,n-1)
    print(' '.join(map(str,a[:ans])),end='')
    print(' ['+str(a[ans])+'] ',end='')
    if(ans<n-1):
        print(' '.join(map(str,a[ans+1:])))

    return

if __name__=='__main__':
    n,a=readinput()
    main(n,a)

Submission status: Accepted

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

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

    return i + 1


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

    print(*A)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

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

def partition_l(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_l(A,0,len(A)-1)
for i,a in enumerate(A):
    if i == b:
        print('[{}] '.format(a),end='')
    elif i < len(A)-1:
        print('{} '.format(a),end='')
    else:
        print('{}'.format(a),end='')
print()

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j] <= x:
            i += 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]) + "]"
A = map(str, A)
print(" ".join(A))

Submission status: Accepted

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

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

A_out, pos = partition(A, 0, n-1)
*A_out, = map(str,A_out)


print(" ".join(A_out[:pos]) + " [" + str(A_out[pos]) + "] " + " ".join(A_out[pos+1:]))

Submission status: Accepted

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

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

p = partition(A, 0, n-1)
for i in range(n):
    if i != 0:
        print(" ", end="")
    if i == p:
        print(f"[{A[i]}]", end="")
    else:
        print(A[i], end="")
print()

Submission status: Accepted

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

Submission status: Accepted

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

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


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

Submission status: Accepted

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

Submission status: Accepted

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

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

for j, a in enumerate(A):
    if j == 0:
        print(a, end='')
    elif j == i:
        print(' [{}]'.format(a), end='')
    else:
        print(' {}'.format(a), end='')
print()

Submission status: Accepted

Solution code:
# Partition
# https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/6/ALDS1_6_B

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

def partiton(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

idx = partiton(A, 0, n - 1)

for i in range(n):
	if i == idx:
		A[i] = '[' + str(A[idx]) + ']'

print(*A)

Submission status: Accepted

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


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


i = partition(0, n - 1)
S[i] = '[' + str(S[i]) + ']'

print(*S)

Submission status: Accepted

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


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

print(" ".join(map(str, A[:idx])) + ' [' + str(A[idx]) + '] ' + " ".join(map(str, A[idx+1:])))

Submission status: Accepted

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

    return i+1


if __name__ == "__main__":
    import sys
    input = sys.stdin.readline # faster input

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

    q = partition(A, 0, n-1)
    A[q] = '[{}]'.format(A[q])

    print(' '.join(map(str, A)))

Submission status: Accepted

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

def partition(A,p,r):

    x = A[r]

    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] = x
    A[r] = tmp

    return i+1


y = partition(A,0,n-1)
A = list(map(str,A))
A[y] = "["+A[y]+"]"

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

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

for i in range(n):
    if i == r and i == n-1:
        print("["+str(A[i])+"]",end="")
    elif i == r:
        print("["+str(A[i])+"]",end=" ")
    elif i == n-1:
        print(A[i],end="")
    else:
        print(A[i],end=" ")
print()

Submission status: Accepted

Solution code:
def partition(a,p,r)->int:
    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()))
    index = partition(a,0,n-1)
    print (' '.join(map(str,a[:index])),end=' ')
    print ('[%d]'%a[index],end=' ')
    print (' '.join(map(str,a[index+1:])))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N=input()
L=input()

L=list(map(int,L.split()))

i=0
j=0

x=L[-1]

while j < len(L):
    if L[j] > x:
        j += 1
        
    else:
        L_i = L[i]
        L_j = L[j]
        if j == len(L)-1:
            L_j='['+str(L_j)+']'
        L[i] = L_j
        L[j] = L_i
        i += 1
        j += 1
         
print(' '.join(map(str,L)))

Submission status: Accepted

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


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

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  
  
idx = partition(A, 0, n-1)

def tostr(x,i):
  if i == idx :
    return "[{}]".format(x)
  return str(x)

print(" ".join([tostr(x,i) 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 + 1

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

idx = partition(A, 0, n - 1)
S = " ".join(map(str, A[:idx]))
S += " [" + str(A[idx]) + "] "
S += " ".join(map(str, A[idx + 1:]))
print(S)

Submission status: Accepted

Solution code:
# Partition パーティション


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


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

Submission status: Accepted

Solution code:
def partition(arr, p: int, r: int):
    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()))
index = partition(a, 0, n - 1)
ans = []
for i in range(n):
    ans.append('[' + str(a[i]) + ']' if i == index else str(a[i]))
print(*ans)

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:
# Partition
N = int(input())
A = list(map(int, input().split()))

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

A[-1] = A[i+1]
A[i+1] = '[' + str(x) + ']'

print(*A)

Submission status: Accepted

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


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


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys,collections
n = int(sys.stdin.readline())
A = list(map(int,sys.stdin.readline().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
q = partition(A,0,len(A)-1)
print(" ".join([str(e) if i != q else "["+str(e)+"]" for i,e 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 + 1

def Main():
    n = int(input())
    A = [int(a) for a in input().split()]

    idx = Partition(A, 0, n - 1)
    s_A = [str(a) for a in A]
    
    res = " ".join(s_A[:idx]) + " [" + s_A[idx] + "] " + " ".join(s_A[idx + 1:])
    print(res)

Main()