Problem:


Quick Sort

Let's arrange a deck of cards. Your task is to sort totally n cards. A card consists of a part of a suit (S, H, C or D) and an number. Write a program which sorts such cards 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 cards.

n cards are given in the following lines. Each card is given in a line and represented by a pair of a character and an integer separated by a single space.

Output

In the first line, print the stability ("Stable" or "Not stable") of this output.

In the following lines, print the arranged cards in the same manner of that of the input.

Constraints

1 ≤ n ≤ 100,000

1 ≤ the number of a card  ≤ 109

There are no identical card in the input

Sample Input 1

6
D 3
H 2
D 1
S 3
D 2
C 1

Sample Output 1

Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Sample Input 2

2
S 1
H 1

Sample Output 2

Stable
S 1
H 1



Sample input:
6
D 3
H 2
D 1
S 3
D 2
C 1


Sample output:
Not stable
D 1
C 1
D 2
H 2
D 3
S 3

Submission status: Accepted

Solution code:
import sys, os, math, bisect, itertools, collections, heapq, queue, copy, array
from typing import List

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


class Card:
    def __init__(self, suit: str, value: int):
        self.suit = suit
        self.value = value


def partition(cards: List[Card], p: int, r: int) -> int:
    x = cards[r].value
    i = p - 1
    for j in range(p, r):
        if cards[j].value <= x:
            i += 1
            cards[i], cards[j] = cards[j], cards[i]
    cards[i + 1], cards[r] = cards[r], cards[i + 1]
    return i + 1


def quick_sort(cards: List[Card], p: int, r: int):
    if p < r:
        q = partition(cards, p, r)
        quick_sort(cards, p, q - 1)
        quick_sort(cards, q + 1, r)


def merge(cards: List[Card], left: int, mid: int, right: int):
    n1 = mid - left
    n2 = right - mid
    L, R = [Card('Z', 0)] * (n1 + 1), [Card('Z', 0)] * (n2 + 1)
    for i in range(n1):
        L[i] = cards[left + i]
    for i in range(n2):
        R[i] = cards[mid + i]

    L[n1] = Card('Z', float('INF'))
    R[n2] = Card('Z', float('INF'))

    i, j = 0, 0
    for k in range(left, right):
        if L[i].value <= R[j].value:
            cards[k] = L[i]
            i += 1
        else:
            cards[k] = R[j]
            j += 1


def merge_sort(cards: List[Card], left: int, right: int):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(cards, left, mid)
        merge_sort(cards, mid, right)
        merge(cards, left, mid, right)


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

    N = ii()
    A, B = [], []
    for n in range(N):
        suit, value = sl()
        A.append(Card(suit, int(value)))
        B.append(Card(suit, int(value)))

    # ソート
    quick_sort(A, 0, N - 1)
    merge_sort(B, 0, N)

    # 回答
    for a, b in zip(A, B):
        if a.suit != b.suit or a.value != b.value:
            print('Not stable')
            break
    else:
        print('Stable')
    for a in A:
        print(a.suit, a.value)


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):
        if A[j][1] <= 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 quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q - 1)
        quick_sort(A, q + 1, r)


def main():
    n = int(input())
    A = []

    for i in range(n):
        mark, num = input().split()
        A.append([mark, int(num), i])

    quick_sort(A, 0, n - 1)

    flag = False
    for i in range(1, n):
        if A[i - 1][1] == A[i][1]:
            if A[i - 1][2] > A[i][2]:
                flag = True
                break

    if flag:
        print("Not stable")
    else:
        print("Stable")

    for i in range(n):
        print(A[i][0], A[i][1])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

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


def merge(A, left, mid, right):
    L, R = [], []
    for a in A[left:mid]:
        L.append(a)
    for a in A[mid:right]:
        R.append(a)
    L.append(Card("dummy 0"))
    R.append(Card("dummy 0"))
    L[-1].num = math.inf
    R[-1].num = math.inf
    i, j = 0, 0
    for k in range(left, right):
        if L[i].num <= R[j].num:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if right - left > 1:
        mid = (right + left) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

class Card(str):
    def __init__(self, input_card):
        super().__init__
        self.num = int(input_card.split(" ")[-1])

N = int(input().rstrip())
A = []
for _ in range(N):
    A.append(Card(input().rstrip()))

A_2 = A.copy()

quickSort(A, 0, len(A)-1)
mergeSort(A_2, 0, len(A))

stable = True
for a_1, a_2 in zip(A, A_2):
    if a_1 != a_2:
        stable = False
        break
print("Stable" if stable else "Not stable")
for a in A:
    print(a)

Submission status: Accepted

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

if __name__ == '__main__':
  N = int(input())
  A=[]
  B=[]
  for _ in range(N):
    s, n = input().split()
    A.append((s, int(n)))
    B.append((s, int(n)))

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

  def merge(B, left, middle, right):
    n1 = middle - left
    n2 = right - middle
    L1=[('a', 0)]*n1
    L2=[('a', 0)]*n2
    for i in range(n1):
      L1[i] = B[left + i]
    for j in range(n2):
      L2[j] = B[middle + j]
    L1.append(('z', 10**9+1))
    L2.append(('z', 10**9+1))
    #print(L1)
    #print(L2)
    i = 0
    j = 0
    for k in range(left, right):
      if L1[i][1] <= L2[j][1]:
        B[k] = L1[i]
        i += 1
      else:
        B[k] = L2[j]
        j += 1

  
  def mergeSort(B, left, right):
    if left + 1 < right:
      middle = (left + right) // 2
      mergeSort(B, left, middle)
      mergeSort(B, middle, right)
      merge(B, left, middle, right)

  
  quicksort(A, 0, N - 1)
  mergeSort(B, 0, N)
  print('Stable' if A==B else 'Not stable')
  for a in A:
    print(a[0] + ' ' + str(a[1]))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)


def partition(A, p, r):

    x = A[r][1]
    i = p - 1

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


def main():

    N = int(sys.stdin.readline().rstrip())

    A = []

    for i in range(N):
        m, n = sys.stdin.readline().rstrip().split()
        A.append((m, int(n), i))  # stable 確認用に index をつけておく

    quicksort(A, 0, N - 1)

    for i in range(1, N):
        if A[i][1] == A[i - 1][1]:
            if A[i][2] < A[i - 1][2]:
                print("Not stable")
                break
    else:
        print("Stable")

    for m, n, _ in A:
        print(m, n)


main()

Submission status: Accepted

Solution code:
from copy import deepcopy
 
def Partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= 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 Quicksort(A, p, r):
    if p < r:
        q = Partition(A, p, r)
        Quicksort(A, p, q-1)
        Quicksort(A, q+1, r)
 
 
n = int(input())
cards = []
for i in range(n):
    card = input().split()
    card[1] = int(card[1])
    cards.append(card)
prev_cards = deepcopy(cards)
prev_cards.sort(key=lambda card: card[1])
 
Quicksort(cards, 0, n-1)
 
if cards == prev_cards:
    print("Stable")
else:
    print("Not stable")
 
for card in cards:
    print(' '.join(map(str, card)))

Submission status: Accepted

Solution code:
n = int(input())
suits = [0] * n
ranks = [0] * n
orders = [0] * n
for i in range(n):
    suit, rank = input().split()
    suits[i] = suit
    ranks[i] = int(rank)
    orders[i] = i

def quicksort(p, r):
    if p < r:
        q = partition(p, r)
        quicksort(p, q-1)
        quicksort(q+1, r)

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

quicksort(0, n-1)

for i in range(1, n):
    if ranks[i] == ranks[i-1] and orders[i] < orders[i-1]:
        print('Not stable')
        break
else:
    print('Stable')

for i in range(n):
    print(suits[i], ranks[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
"""
ソートテク関連の基本的な関数の詰め合わせ (命名は C++ STL algorithm による)


stable_partition(seq, func):
    O(n)
    空間計算量も O(n)
    述語が True を返す全ての要素が、述語が False を返す全ての要素よりも前になるようにシーケンスを並び替える (破壊、安定)


nth_element(seq, k, begin, end):
    O(n)
    E = seq[k] とする
    特定の要素 E よりも小さい全ての要素が E よりも前になり、 E 以上の全ての要素がEよりも後になるように seq[begin:end] を並び替える (破壊、不安定)
    heapq の nlargest とは異なるので注意


ith_order_statistic(seq, i, begin, end):
    O(n)
    nth_element を用いて (seq[begin:end] に存在することがわかっている) i 番目の順序統計量を求める (i = 0, 1, ..., n-1)


simple_quick_sort(seq, begin, end):
    O(nlgn)
    nth_element を用いて seq[begin:end] をソートする (破壊、不安定)


modified_merge_sort(seq, begin, end):
    O(nlgn)
    _modified_merge を用いて seq[begin:end] をソートする (非破壊、安定)
    転倒数とソート済み配列を返す


count_inversion(seq):
    O(nlgn)
    modified_merge_sort を用いて seq の転倒数を求める
    (転倒数: seq[i] > seq[j] (i < j) なる (i, j) の組み合わせの数のこと)
"""


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], pivot_ind: int, 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)
    if not begin <= pivot_ind < end:
        raise RuntimeError(f"nth_element(): pivot_ind should be begin <= pivot_ind < end. got pivot_ind={pivot_ind}, begin={begin}, end={end}.")

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




def simple_quick_sort(L: List[Num], begin: int, end: int, key=lambda x: x) -> None:
    """
    nth_element 関数を用いて L[begin:end] を 破壊的に不安定でクイックソートする O(nlgn)

    Args:
        L (list)
        begin, end (int)
    
    Examples:
        >>> seq = [3, 5, 2, 1, 0, 3]
        >>> simple_quick_sort(seq, 0, 6)
        >>> seq
        [0, 1, 2, 3, 3, 5]
    """
    if end - begin > 1:
        # pivot_ind は begin ... end -1 から選ばれてほしい
        # mid = nth_element(L, random.randint(begin, end - 1), begin, end, key)
        mid = nth_element(L, end - 1, begin, end, key)
        simple_quick_sort(L, begin, mid, key)
        simple_quick_sort(L, mid+1, end, key)



def _modified_merge(left: List[Num], right: List[Num], key=lambda x: x) -> Tuple[int, List[Num]]:
    """
    ソート済み配列 left, right を受け取り、全体のソート済み配列を生成する (O(n))
    マージの過程で転倒数をメモして返す

    Args:
        left (list): ソート済み
        right (list): ソート済み

    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> _modified_merge([1, 5, 7], [2, 3, 3])
        (6, [1, 2, 3, 3, 5, 7])
    """
    sorted_list = []
    i, j, inv = 0, 0, 0
    buf_1 = left[:] + [[None, float('inf')]]
    buf_2 = right[:] + [[None, float('inf')]]
    for _ in range(len(left) + len(right)):
        if key(buf_1[i]) <= key(buf_2[j]):
            sorted_list.append(buf_1[i])
            i += 1
        else:
            sorted_list.append(buf_2[j])
            j += 1
        inv += 1
    return inv, sorted_list


# verified @AOJ ALDS1_5_B
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_5_B&lang=ja
def modified_merge_sort(L, begin, end, key=lambda x: x):
    """
    L[begin:end] を 非破壊的かつ安定にマージソートする (O(nlgn))
    マージソートの過程で転倒数をメモして返す

    Args:
        L (list)
        begin, end (int)
    
    Returns:
        inv (int): 転倒数
        sorted_list (list): ソート済み
    
    Examples:
        >>> modified_merge_sort([3, 5, 2, 1, 0], 0, 5)
        (9, [0, 1, 2, 3, 5])
    """
    if end - begin == 1:
        return 0, [L[begin]]
    mid = (begin + end) // 2
    left_inv_cnt, left = modified_merge_sort(L, begin, mid, key)
    right_inv_cnt, right = modified_merge_sort(L, mid, end, key)
    merge_inv_cnt, sorted_list = _modified_merge(left, right, key)
    return left_inv_cnt + right_inv_cnt + merge_inv_cnt, sorted_list





if __name__ == "__main__":
    n = int(input())
    L = []
    for _ in range(n):
        char, num = input().split()
        num = int(num)
        L.append([char, num])
    _, stable_seq = modified_merge_sort(L, 0, n, key=lambda x: x[1])
    simple_quick_sort(L, 0, n, lambda x: x[1])
    
    print('Stable') if stable_seq == L else print('Not stable')
    # for elm in stable_seq:
    #     print(*elm, sep=' ')
    for elm in L:
        print(*elm, sep=' ')

Submission status: Accepted

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

for i in range(n):
    a,num = input().split()
    A.append([a,int(num),i])
    
def partition(A,p,r):
    #import random
    #rand = 1+int(p+(r-p)*random.random())
    #A[rand],A[r] = A[r],A[rand]    
    x = A[r][1]
    i = p-1
    for j in range(p,r):
        if A[j][1]<= 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 quickSort(A,p,r):
    if p<r:
        q = partition(A,p,r)
        quickSort(A,p,q-1)
        quickSort(A,q+1,r)
        
quickSort(A,0,n-1)

def check_stable(A):
    for i in range(n-1):
        if (A[i][1] == A[i+1][1]) & (A[i][2]>A[i+1][2]):
            return "Not stable"
    return "Stable"

print(check_stable(A))

for a,num,_ in A:
    print(*[a, num])

Submission status: Accepted

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


def resolve():
    from collections import defaultdict, deque
    n = int(input())
    A = []
    chk = defaultdict(deque)
    for _ in range(n):
        a, b = input().split()
        b = int(b)
        A.append([a, b])
        chk[b].append(a)
    quickSort(A, 0, len(A) - 1)
    for a, b in A:
        if chk[b].popleft() != a:
            print("Not stable")
            break
    else:
        print("Stable")
    for a in A:
        print(*a)


resolve()

Submission status: Accepted

Solution code:
def quickSort(A, p, r):
  if p < r:
    q = partition(A, p, r)
    quickSort(A, p, q-1)
    quickSort(A, q+1, r)


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

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


deck = []
n = int(input())
for index in range(n):
  mark, number = input().split()
  card = [mark, int(number), index]

  deck.append(card)

quickSort(deck, 0, n-1)

ans = 'Stable'
for i in range(1, n):
  if deck[i-1][1] == deck[i][1]:
    if deck[i-1][2] > deck[i][2]:
      ans = 'Not stable'
      break
print (ans)
for v in deck:
  print ('{mark} {number}'.format(mark=v[0], number=v[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][1] <= x[1]:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i+1

def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q-1)
        quickSort(A, q+1, r)

n = int(input())
A = []
for i in range(n):
    x, y = input().split()
    A.append([x, int(y)])
    
B = A[:]

quickSort(A, 0, n - 1)

for i in range(n - 1):
    if A[i][1] == A[i + 1][1]:
        if B.index(A[i]) > B.index(A[i + 1]):
            print("Not stable")
            break
else:
    print("Stable")
  
for i in A:
    print(*i)

Submission status: Accepted

Solution code:
import sys, copy
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 = []
    for _ in range(n):
        SN = LSS()
        A.append((SN[0], int(SN[1])))

    A_org = copy.deepcopy(A)

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

    def is_stable(A, A_org):
        # 数字をkey、スート列をvalueに持つ辞書を使って比較

        d_A = {}
        for i in A:
            if i[1] in d_A:
                d_A[i[1]].append(i[0])
            else:
                d_A[i[1]] = [i[0]]
        d_A_org = {}
        for i in A_org:
            if i[1] in d_A_org:
                d_A_org[i[1]].append(i[0])
            else:
                d_A_org[i[1]] = [i[0]]

        if d_A == d_A_org:
            return 'Stable'
        else:
            return 'Not stable'

    quickSort(A, 0, n-1)
    print(is_stable(A, A_org))
    for s, n in A:
        print(s, n)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
# coding: utf-8
# クイックソート
import copy


def partition(A, p, r):
    x = int(A[r].split()[1])

    i = p - 1
    tmp = 0

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

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


def quickSort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q - 1)
        quickSort(A, q + 1, r)
    return (A)


def checkStable(before_list, sorted_list):

    for val in sorted_list:
        same_list = [
            i for i in sorted_list
            if (int(val.split()[1]) == int(i.split()[1])) and val != i
        ]
        if len(same_list) == 0:
            continue

        for data in same_list:
            bef = before_list.index(val) - before_list.index(data)
            aft = sorted_list.index(val) - sorted_list.index(data)

            if (bef > 0 and aft < 0) or (bef < 0 and aft > 0):
                return 'Not stable'

    return 'Stable'


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

    A = []
    for _ in range(n):
        A.append(input())

    bef_A = copy.deepcopy(A)

    aft_A = quickSort(A, 0, n - 1)

    print(checkStable(bef_A, aft_A))

    for data in aft_A:
        print(data)

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

def QuickSort(A,p,r):
    if p<r:
        q = Partition(A,p,r)
        QuickSort(A,p,q-1)
        QuickSort(A,q+1,r)

if __name__ == "__main__":
    n = int(input())
    card = []
    for i in range(n):
        key,val = input().split()
        card.append([key,int(val)])
    card2 = copy.copy(card)
    card2.sort(key= lambda x:x[1])
    QuickSort(card,0,n-1)
    if card2 == card:
        print("Stable")
    else:
        print("Not stable")
    for i in range(n):
        print(card[i][0],card[i][1])

Submission status: Accepted

Solution code:
n=int(input())
nums=[input().split() for i in range(n)]
for j in range(n):
    nums[j][1]=int(nums[j][1])
    nums[j].append(int(j))


def quick_sort(nums,p,r):
    if p<r:
        q=partition(nums,p,r)
        quick_sort(nums,p,q-1)
        quick_sort(nums,q+1,r)

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

quick_sort(nums,0,n-1)

key=1

for i in range(n):
    if i!=n-1:
        if nums[i][1]==nums[i+1][1]:
            if nums[i][2]>nums[i+1][2]:
                key=0

if key:
    print("Stable")

else:
    print("Not stable")

for i in range(n):
    print(nums[i][0],nums[i][1])

Submission status: Accepted

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


    
n = int(input())
A = [input() for i in range(n)]
stable = sorted(A, key=lambda x:
int(x.split()[1]))
B = A[:]
quicksort(A,0,n-1)
print("Stable" if stable == A else "Not stable")

for c in A:
    print(c)

Submission status: Accepted

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

def quick_sort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quick_sort(a, p, q - 1)
        quick_sort(a, q + 1, r)

n = int(input())
cards = [input() for i in range(n)]
stable = sorted(cards, key=lambda x: int(x.split()[1]))
quick_sort(cards, 0, n - 1)

print("Stable" if stable == cards else "Not stable")

for card in cards:
    print(card)

Submission status: Accepted

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

def quick_sort(a, p, r):
    if p < r:
        q = partition(a, p, r)
        quick_sort(a, p, q - 1)
        quick_sort(a, q + 1, r)


n = int(input())
cards = [input() for i in range(n)]
stable = sorted(cards, key=lambda x: int(x.split()[1]))
quick_sort(cards, 0, n - 1)

print("Stable" if stable == cards else "Not stable")

for card in cards:
    print(card)

Submission status: Accepted

Solution code:
n = int(input())
A = []
for i in range(n):
    mark,number = map(str,input().split())
    A.append((mark, int(number), i))

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

A = quickSort(A, 0, n-1)

is_stable = True
for i in range(1, len(A)):
    if(A[i-1][1] == A[i][1]) and (A[i-1][2] > A[i][2]):
        is_stable = False
        break
print('Stable') if is_stable else print('Not stable')
for i in range(len(A)):
    print("{0} {1}".format(A[i][0], A[i][1]))

Submission status: Accepted

Solution code:
from operator import itemgetter 
def partition(A,p,r):
    x = A[r][1]
    i = p-1
    for j in range(p,r):
        if A[j][1] <= 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 quicksort(A,p,r):
    if p < r:
        q = partition(A,p,r)
        quicksort(A,p,q-1)
        quicksort(A,q+1,r)
A = []
n = int(input())
for i in range(n):
    a,b = map(str,input().split())
    A.append([a,int(b)])

B = [i for i in A]
quicksort(A,0,n-1)

B.sort(key=itemgetter(1))

if A == B:
    print("Stable")
else:
    print("Not stable")
for i in A:
    print(i[0],i[1])

Submission status: Accepted

Solution code:
def readinput():
    n=int(input())
    cards=[]
    nums=set()
    for _ in range(n):
        m,nn=input().split()
        nn=int(nn)
        cards.append((m,nn))
        nums.add(nn)
    return n,cards, nums

def partition(cards,p,r):
    #print('before:',end='');print(cards[p:r+1])
    x=cards[r][1]
    i=p-1
    for j in range(p,r):
        if (cards[j][1] <= x):
            i+=1
            cards[j],cards[i]=cards[i],cards[j]
            #print(cards[p:r+1])
    cards[i+1],cards[r]=cards[r],cards[i+1]
    #print('after:',end='');print(cards[p:r+1])
    return i+1

def quickSort(cards,p,r):
    if (p<r):
        q=partition(cards,p,r)
        quickSort(cards,p,q-1)
        quickSort(cards,q+1,r)

def getMarks(cards,n):
    marks=[]
    for card in cards:
        if(card[1]==n):
            marks.append(card[0])
    return marks

def isStable(cards0, cards1, nums):
    for n in nums:
        marks0=getMarks(cards0,n)
        marks1=getMarks(cards1,n)
        if(marks0!=marks1):
            return False
    return True

def main(n,cards,nums):
    original = cards.copy()
    quickSort(cards,0,n-1)
    ans=isStable(original, cards, nums)
    if(ans==True):
        print('Stable')
    else:
        print('Not stable')
    for card in cards:
        print(card[0]+' '+str(card[1]))
    return

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

Submission status: Accepted

Solution code:
from collections import deque, defaultdict


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

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

    return i + 1


def quick_sort(A, p, r):
    if p < r:
        q = partition(A, p, r)
        quick_sort(A, p, q-1)
        quick_sort(A, q+1, r)


def main():
    n = int(input())
    A = []
    d = defaultdict(deque)
    stable = True
    for i in range(n):
        inp = input().replace(" ", "")
        A.append(inp)
        d[int(inp[1:])].append(inp[0])
    quick_sort(A, 0, n-1)

    # stableかどうかを確認
    for a in A:
        tmp = d[int(a[1:])].popleft()
        if a[0] != tmp:
            stable = False

    if stable:
        print("Stable")

    else:
        print("Not stable")

    for a in A:
        print(a[0], a[1:])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def quickSort(a, p, r):
    if p<r:
        q = partition(a, p, r)
        quickSort(a, p, q - 1)
        quickSort(a, q+1, r)  


    #รับ input
n = int(input())
a = []
for i in range(n):
    a.append(list(input().split()))
    a[i][1]=int(a[i][1])
b = copy.deepcopy(a)

quickSort(a, 0, n-1)

for i in range(n-1):
    if a[i][1] == a[i+1][1]:
        if b.index(a[i]) > b.index(a[i+1]):
            print("Not stable")
            break
else:
    print("Stable")

for i in a:
    print(" ".join(map(str,i)))

Submission status: Accepted

Solution code:
# INF = 10*10

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

def quicksort(A, p, r):
   if p < r:
     q = partition(A, p, r)
     quicksort(A, p, q-1)
     quicksort(A, q+1, r)
#
# def merge(A, left, mid,  right):
#   global cnt
#   L = A[left:mid]
#   L.append([0,INF])
#   R = A[mid:right]
#   R.append([0,INF])
#   i = 0
#   j = 0
#   for k  in range(left , right):
#     if L[i][1] <= R[j][1]:
#       A[k] = L[i]
#       i = i + 1
#     else:
#       A[k] = R[j]
#       j = j + 1
#
# def mergeSort(A, left, right):
#   if left+1 < right:
#     mid = (left + right)//2
#     mergeSort(A, left, mid)
#     mergeSort(A, mid, right)
#     merge(A, left, mid, right)
#
n = int(input())
A = [[0 for j in range(3)] for i in range(n)]
# B = [[0 for j in range(2)] for i in range(n)]
for i in range(n):
    A[i][0],A[i][1] = input().split()
    A[i][1] = int(A[i][1])
    A[i][2] = i
    # B[i][1] = int(B[i][1])

quicksort(A, 0, n-1)
# mergeSort(B, 0, n)
#
# if A == B:
#     print("Stable")
# else:
#     print("Not stable")

stable_FLG = True
for i in range(1,n):
    if A[i][1] == A[i-1][1] and A[i][2] < A[i-1][2]:
        stable_FLG = False
        break

if stable_FLG:
    print("Stable")
else:
    print("Not stable")


for i in range(n):
    print(A[i][0],A[i][1])