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 math
import copy

n = int(input())
A = [None for i in range(n)]
for i in range(n):
    a, b = input().split()
    A[i] = [a, int(b)]
inf = 10**9

def merge(A,left,mid,right):
	#global cnt
	L = A[left:mid] + [[inf,inf]]
	R = A[mid:right] + [[inf,inf]]
	i = 0
	j = 0

	for k in range(left,right):
		#cnt += 1
		if L[i][1] <= R[j][1]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[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)


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


B = copy.deepcopy(A)
mergeSort(A,0,n)
quickSort(B,0,n-1)

if A == B:
	print("Stable")
else:
	print("Not stable")

ans = [str(x[0]) +" "+str(x[1]) for x in B]
ans = '\n'.join(ans)
print(ans)

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 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 = [(t[0], int(t[1]), i) for t, i in [(input().split(), i) for i in range(n)]]
quicksort(A, 0, n-1)
notstable = any([True for i in range(1, n) if A[i][1] == A[i-1][1] and A[i][2] < A[i-1][2]])
print("Not stable" if notstable else "Stable")
for v in A:
    print(f"{v[0]} {v[1]}")

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 merge(A, left, right, mid):
    lstl = [[A[i][0], A[i][1]] for i in range(left, mid) ] + [[None, 1000000000]]
    lstr = [[A[i][0], A[i][1]] for i in range(mid, right)] + [[None, 1000000000]]
    pl = 0
    pr = 0
    for _ in range(left, right):
        if lstl[pl][1] <= lstr[pr][1]:
            A[left + pl + pr] = lstl[pl]
            pl += 1
        else:
            A[left + pr + pl] = lstr[pr]
            pr += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, right, mid)


import sys
input = sys.stdin.readline

n = int(input())
A_q = []
A_m = []
for _ in range(n):
    card = input().split()
    A_q.append([card[0], int(card[1])])
    A_m.append([card[0], int(card[1])])

quick_sort(A_q, 0, n-1)
merge_sort(A_m, 0, n)

if A_q == A_m:
    print("Stable")
else:
    print("Not stable")

for i in range(n):
    print(" ".join(map(str, A_q[i])))
    #print(" ".join(map(str, A_m[i])))

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][1] <= x[1]:
            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

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

N = int(input())
A = []
D = {}
for i in range(N):
    v, d = sys.stdin.readline().split()
    A.append((v, int(d)))
    D.setdefault(int(d), []).append(v)
    
out_A = quickSort(A,0,N-1)

D = {k: iter(v).__next__ for k, v in D.items()}

ok = 1
for v, d in A:
    if D[d]() != v:
        ok = 0
                
if ok:
    print("Stable")
else:
    print("Not stable")

for i in range(N):
    print(*out_A[i],sep=" ")

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)  



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

n = int(input())
card = []
tmpdic = {}
for i in range(n):
    suit, num = input().split()
    num = int(num)
    card.append((suit, num))
    if num in tmpdic:
        tmpdic[num] += suit
    else:
        tmpdic[num] = suit

order = ""
for i in sorted(tmpdic.keys()):
    order += tmpdic[i]

quick_sort(card, 0, n-1)

for i in range(n):
    if order[i] != card[i][0]:
        print("Not stable")
        break
    if i == n-1:
        print("Stable")

for suit, num in card:
    print(f"{suit} {num}")

Submission status: Accepted

Solution code:
from sys import stdin
N=int(input())
num_list=[]
for i in range(N):
    line = list(stdin.readline().strip().split())
    num_list.append([line[0],int(line[1]),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 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 check(A):
    for i in range(N-1):
        if A[i][1]==A[i+1][1]:
            if A[i][2]>A[i+1][2]:
                return 0
    return 1
quicksort(num_list,0,N-1)
if check(num_list):
    print("Stable")
else:print("Not stable")
for i in num_list:
    del i[2]
    print(*i)

Submission status: Accepted

Solution code:
from collections import defaultdict

n=int(input())
cards=[0]*n
A=[0]*n
inds=[0]*n
d=defaultdict(lambda :[])
di=defaultdict(int)
for i in range(n):
    tmp=input().split()
    cards[i]=tmp[0],int(tmp[1])
    A[i]=int(tmp[1])
    inds[i]=i
    d[int(tmp[1])].append(tmp[0])

def partition(A,inds,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]
            inds[i],inds[j]=inds[j],inds[i]
    A[i+1],A[r]=A[r],A[i+1]
    inds[i+1],inds[r]=inds[r],inds[i+1]
    return i+1

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

quicksort(A,inds,0,n-1)

stable_flag=True
for i in range(n):
    num_i=cards[inds[i]][1]
    suit=cards[inds[i]][0]

    if d[num_i][di[num_i]] != suit:
        stable_flag=False
        break
    di[num_i]+=1

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

for i in range(n):
    print(*cards[inds[i]])

Submission status: Accepted

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

n = int(input())
arr = [input().split() + [i] for i in range(n)]
quick_sort(arr, 0, n - 1)
tag = True
for i in range(1, n):
    if arr[i][1] == arr[i - 1][1] and arr[i - 1][2] > arr[i][2]:
        tag = False
        break
print(['Not stable', 'Stable'][tag])
for s in arr:
    print(*s[:2])

Submission status: Accepted

Solution code:
N = int(input())
A1 = []
A2 = []
for _ in range(N):
    a = input().split()
    A1.append((a[0], int(a[1])))
    A2.append((a[0], int(a[1])))

snt = 10 ** 9 + 1

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


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 merge(A, left, mid, right):
    L = A[left:mid] + [('SNT', snt)]
    R = A[mid:right] + [('SNT', snt)]
    i, j = 0, 0
    for k in range(left, right):
        if L[i][1] <= R[j][1]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

quick_sort(A1, 0, N - 1)
merge_sort(A2, 0, N)

print('Stable' if A1 == A2 else 'Not stable')
for a1 in A1: print(*a1)

Submission status: Accepted

Solution code:
import copy


n = int(input())
M = []
for _ in range(n):
    m = input().split()
    M.append([m[0], int(m[1])])

_M = copy.deepcopy(M)


def group(arr):
    r = {}
    for a in arr:
        if r.get(a[1]):
            r[a[1]] += a[0]
        else:
            r[a[1]] = a[0]

    return r


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


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


quick_sort(0, n - 1)

if group(_M) == group(M):
    print('Stable')
else:
    print('Not stable')

for m in M:
    print(m[0], m[1])

Submission status: Accepted

Solution code:
import math

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 += 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):
    n1 = mid - left
    n2 = right - mid
    L = [None for _ in range(n1+1)]
    R = [None for _ in range(n2+1)]
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]

    L[n1] = math.inf
    R[n2] = math.inf

    i = 0
    j = 0

    for k in range(left, right):
        try:
            v1 = int(L[i][2:])
        except:
            v1 = L[i]

        try:
            v2 = int(R[j][2:])
        except:
            v2 = R[j]

        if v1 <= v2:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


def merge_sort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        merge_sort(A, left, mid)
        merge_sort(A, mid, right)
        merge(A, left, mid, right)

    return A


if __name__ == "__main__":
    n = int(input())
    cards = []
    for i in range(n):
        cards.append(input())

    reference = merge_sort(cards.copy(), 0, n)
    quicksort(cards, 0, n-1)

    if cards == reference:
        print('Stable')
    else:
        print('Not stable')

    for card in cards:
        print(card)

Submission status: Accepted

Solution code:
import math
n = int(input())
A = []

def partition(A,p,r):

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

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

    return i+1


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


def merge(A, left, mid, right):

  L = A[left:mid]
  L.append((1,math.inf))
  R = A[mid:right]
  R.append((1,math.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)



for i in range(n):
   color,number =input().split()
   A.append((color,int(number)))

A_merge = A.copy()
A_quick = A.copy()

mergeSort(A_merge,0,n)
QuickSort(A_quick,0,n)


if A_quick==A_merge: print("Stable")
else: print("Not stable")

for x in A_quick:
    print("%s %d" %(x[0],x[1]))

Submission status: Accepted

Solution code:
def partition(a,p,r)->int:
    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,l,r):
    if l<r:
        q = partition(a,l,r)
        quick_sort(a,l,q-1)
        quick_sort(a,q+1,r)

def check(a):
    for i in range(len(a)):
        j = i+1
        while j<len(a) and a[i][1]==a[j][1]:
            if a[j][2]<a[i][2]:return 'Not stable'
            j+=1
    return 'Stable'

def main():
    n = int(input())
    a = []
    for i in range(n):
        b,c = input().split()
        a.append([b,int(c),i])
    quick_sort(a,0,n-1)
    print (check(a))
    for b,c,_ in a:print (b,c)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

class Card():
  def __init__(self, suit, value):
    self.suit = suit
    self.value = int(value)
  
  def __str__(self):
    return " ".join([self.suit, str(self.value)])
  


MAXINT = 1000000000 + 1
def mergesort(X, l, r):
  if l + 1 < r:
    m = (l + r)//2
    mergesort(X,l,m)
    mergesort(X,m ,r)
    merge(X,l, m, r)

def merge(X, l, m, r):
  nl = m - l
  nr = r - m
  L = [X[i] for i in range(l, l + nl)]
  R = [X[i] for i in range(m, m + nr)]
  L.append(Card('', MAXINT))
  R.append(Card('', MAXINT))
  i = 0
  j = 0
  for k in range(l,r):
    if L[i].value <= R[j].value:
      X[k] = L[i]
      i += 1
    else:
      X[k] = R[j]
      j += 1

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

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

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

n = int(input())
A = list()
B = list()
for _ in range(n):
  s, v = input().split()
  A.append(Card(s, v))
  B.append(Card(s, v))

mergesort(A, 0, len(A))
quicksort(B, 0, len(B) - 1)

flag = True
for a,b in zip(A,B):
  if a.suit != b.suit:
    flag = False
    break

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

for x in B:
  print(x)

Submission status: Accepted

Solution code:
import copy

INF = 10 ** 10
def merge(A, left, mid, right):
	count = 0
	L = A[left:mid] + [(INF, INF)]
	R = A[mid:right] + [(INF, INF)]

	i, j = 0, 0
	for k in range(left, right):
		count += 1
		if L[i][1] <= R[j][1]:
			A[k] = L[i]
			i += 1
		else:
			A[k] = R[j]
			j += 1
	return count

def mergeSort(A, left, right):
	if left + 1 < right:
		mid = (left + right) // 2
		countL = mergeSort(A, left, mid)
		countR = mergeSort(A, mid, right)
		return merge(A, left, mid, right) + countL + countR
	return 0

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())
A = [None for _ in range(n)]
for i in range(n):
	a, b = input().split()
	A[i] = (a, int(b))

B = copy.deepcopy(A)
quickSort(A, 0, n - 1)
mergeSort(B, 0, n)

if A == B:
	print("Stable")
else:
	print("Not stable")

for i in range(n):
	print(" ".join(map(str, A[i])))

Submission status: Accepted

Solution code:
# Quick sort クイックソート


class Card():

    def __init__(self, suit, num):
        self.suit = suit
        self.num = num
    
    def __repr__(self):
        return str(self.suit) + " " + str(self.num)


def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j].num <= x.num:
            i += 1
            t = A[i]
            A[i] = A[j]
            A[j] = t
    A[r] = A[i + 1]
    A[i + 1] = x
    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 mergesort(A, left, right):
    if left + 1 < right:
        mid = int((left + right) / 2)
        mergesort(A, left, mid)
        mergesort(A, mid, right)
        merge(A, left, mid, right)


def merge(A, left, mid, right):
    i1, i2 = 0, 0
    L = A[left:mid] + [Card("X", 2000000000)]
    R = A[mid:right] + [Card("X", 2000000000)]
    for j in range(left, right):
        if L[i1].num <= R[i2].num:
            A[j] = L[i1]
            i1 += 1
        else:
            A[j] = R[i2]
            i2 += 1


def compareCards(c1, c2):
    return c1.suit == c2.suit and c1.num == c2.num


def compareStacks(A, B):
    for i in range(len(A)):
        if not compareCards(A[i], B[i]):
            return False
    return True


n = int(input())
A, B = [], []
for i in range(n):
    suit, num = input().split()
    A += [Card(suit, int(num))]
    B += [Card(suit, int(num))]
quicksort(A, 0, n - 1)
mergesort(B, 0, n)
if compareStacks(A, B):
    print("Stable")
else:
    print("Not stable")
for a in A:
    print(a)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

n = int(input())
arr = [input().split() for _ in range(n)]
stable_dict = defaultdict(list)
stable_list = []

for a in arr:
    stable_dict[int(a[1])].append(a[0])

stable_dict = sorted(stable_dict.items(), key = lambda x: x[0])

for key, values in stable_dict:
    for v in values:
        stable_list.append([v, str(key)])

quick_sort(arr, 0, n - 1)

is_stable = 'Stable'
for (a, s) in zip(arr, stable_list):
    if ''.join(a) != ''.join(s):
        is_stable = 'Not stable'
        break
print(is_stable)

for a in arr:
    print(*a)

Submission status: Accepted

Solution code:
class TRAMP:
    def __init__(self,arg_mark,arg_number,arg_input_index):
        self.mark = arg_mark
        self.number = arg_number
        self.input_index = arg_input_index

N = int(input())
table = []
for input_index in range(N):
    mark,number = map(str,input().split())
    table.append(TRAMP(mark,int(number),input_index))

def Partition(left,right):
    global table
    i = left-1
    pivot = table[right].number
    for start in range(left,right):
        if table[start].number <= pivot:
            i += 1
            table[i],table[start] = table[start],table[i]
    table[i+1],table[right] = table[right],table[i+1]
    return i+1

def quickSort(left,right):
        if left < right:
            q = Partition(left,right)
            quickSort(left,q-1)
            quickSort(q+1,right)

quickSort(0,N-1)
stable_FLG = True

for i in range(1,N):
    if table[i].number == table[i-1].number and table[i].input_index < table[i-1].input_index:
        stable_FLG=False
        break

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

for i in range(N):
    print("%s %d"%(table[i].mark,table[i].number))

Submission status: Accepted

Solution code:
# Quick Sort

N = int(input())
A = []
for _ in range(N):
    s, a = input().split()
    A.append((s, int(a)))

B = [a for a in A]


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

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


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


INF = float('inf')


def merge(left, mid, right):
    L = B[left:mid]+[('sentinel', INF)]
    R = B[mid:right]+[('sentinel', INF)]
    l = 0
    r = 0

    for i in range(left, right):
        if L[l][1] <= R[r][1]:
            B[i] = L[l]
            l += 1
        else:
            B[i] = R[r]
            r += 1


def merge_sort(left, right):
    if left+1 < right:
        mid = (left+right)//2
        merge_sort(left, mid)
        merge_sort(mid, right)
        merge(left, mid, right)


quick_sort(0, N-1)
merge_sort(0, N)

print('Stable' if A == B else 'Not stable')
for s, v in A:
    print(s, v)


# print('Merge')
# for s, v in B:
#     print(s, v)

Submission status: Accepted

Solution code:
class Card:
    def __init__(self, num, suit, input_index):
        self.num = num
        self.suit = suit
        self.input_index = input_index


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


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


n = int(input())
li = [None] * n
for i in range(n):
    temp_list = list(map(str, input().split()))
    li[i] = Card(int(temp_list[1]), temp_list[0], i)

quick_sort(li, 0, n)

for i in range(n):
    if i < n - 1 and li[i].num == li[i + 1].num and li[i].input_index > li[i + 1].input_index:
        print('Not stable')
        break
    if i == n - 1:
        print('Stable')

for card in li:
    print(card.suit + ' {}'.format(card.num))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000000)

N = int(input())
origin_list = [input().split() for _ in range(N)]
card_list = origin_list[:]
card_list2 = sorted(card_list[:], key=lambda x:x[1])

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

    for j in range(p, r):
        if int(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(card_list, 0, len(card_list)-1)


if card_list == card_list2:
    print('Stable')
else:
    print('Not stable')

for item in card_list:
    print(*item)

Submission status: Accepted

Solution code:
import sys,collections
n = int(sys.stdin.readline())
#A = list(map(int,sys.stdin.readline().split()))
A = [[x,int(y)] for x,y in [line.split() for line in sys.stdin.readlines()]]
d = {}
for i,p in enumerate(A):
  d[str(p)]=i
def partition(A,p,r):
  x = A[r][1] #pivod
  i = p    #high-start
  for j in range(p,r): #high-end
    if A[j][1] <= x:
      A[i],A[j] = A[j],A[i]
      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)
quicksort(A,0,len(A)-1)
for i in range(1,n):
  if A[i-1][1]==A[i][1] and d[str(A[i-1])] > d[str(A[i])]:
    print("Not stable")
    print("\n".join([p[0]+" "+str(p[1]) for p in A]))
    exit(0)
print("Stable")
print("\n".join([p[0]+" "+str(p[1]) for p in A]))

Submission status: Accepted

Solution code:
class card():
    def __init__(self, suit, number):
        self.s = suit
        self.n = number

def Partition(A, p, r):
    x = int(A[r].n)
    i = p - 1

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

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(input())
    cards = list()
    
    for i in range(n):
        S, N = input().split()
        c = card(S, N)
        cards.append(c)

    reference = sorted(cards, key=lambda x: int(x.n))
    QuickSort(cards, 0, len(cards) - 1)

    flag = 1

    for i in range(len(cards)):
        if cards[i].s != reference[i].s or cards[i].n != reference[i].n :
            flag = 0
            break;
    
    if flag:
        print("Stable")
    else:
        print("Not stable")

    for i in range(len(cards)):
        print("{0} {1}".format(cards[i].s, cards[i].n))
        
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 = 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 stable(A, B):
    for i in range(len(A)):
        if A[i] != B[i]:
            return "Not stable"
    return "Stable"

def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = []
    R = []

    for i in range(n1):
        L.append(A[left+i])
    for i in range(n2):
        R.append(A[mid+i])

    L.append([0, 10**9])
    R.append([0, 10**9])

    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())
X = []
for i in range(n):
    a = input().split()
    X.append([a[0], int(a[1])])
    
Y = X[:]
quicksort(X, 0, n-1)
mergeSort(Y, 0, n)
print(stable(X, Y))
for elem in X:
    print(" ".join(map(str, elem)))

Submission status: Accepted

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


def quick_sort(A, l, r):
    if r - l > 1:
        q = partition(A, l, r)
        quick_sort(A, l, q)
        quick_sort(A, q, r)


n = int(input())
A = []
for i in range(n):
    a, b = input().split()
    A.append((a, int(b)))
dct0 = {}
for a in A:
    dct0[a[1]] = []
for a in A:
    dct0[a[1]].append(a[0])
quick_sort(A, 0, n)
dct1 = {}
for a in A:
    dct1[a[1]] = []
for a in A:
    dct1[a[1]].append(a[0])
if dct0 == dct1:
    print('Stable')
else:
    print('Not stable')
for a in A:
    print(*a)

Submission status: Accepted

Solution code:
import heapq
from collections import deque
from enum import Enum
import sys
import math
from _heapq import heappush, heappop
import copy

BIG_NUM = 2000000000
HUGE_NUM = 99999999999999999
MOD = 1000000007
EPS = 0.000000001
#sys.setrecursionlimit(3**12)


class TRAMP:
    def __init__(self,arg_mark,arg_number,arg_input_index):
        self.mark = arg_mark
        self.number = arg_number
        self.input_index = arg_input_index

N = int(input())
table = []
for input_index in range(N):
    mark,number = map(str,input().split())
    table.append(TRAMP(mark,int(number),input_index))

def Partition(left,right):
    global table
    i = left-1
    pivot = table[right].number
    for start in range(left,right):
        if table[start].number <= pivot:
            i += 1
            table[i],table[start] = table[start],table[i]
    table[i+1],table[right] = table[right],table[i+1]
    return i+1

def quickSort(left,right):
        if left < right:
            q = Partition(left,right)
            quickSort(left,q-1)
            quickSort(q+1,right)

quickSort(0, N-1)
stable_FLG = True

for i in range(1,N):
    if table[i].number == table[i-1].number and table[i].input_index < table[i-1].input_index:
        stable_FLG = False
        break

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

for i in range(N):
    print("%s %d"%(table[i].mark,table[i].number))

Submission status: Accepted

Solution code:
# import sys
# sys.stdin = open('input.txt', 'r')

class Card:
    def __init__(self):
        self.suit = ''
        self.num = 0
    def __str__(self):
        return self.suit + ' ' + str(self.num)

def merge(A, left, mid, right):
    """
    right: 最後の添字 + 1
    """
    SENTINEL = Card()
    SENTINEL.num = 2 * 10**9

    n1 = mid - left;
    n2 = right - mid;
    L = A[left:left+n1]
    R = A[mid:mid+n2]

    L.append(SENTINEL)
    R.append(SENTINEL)
    i = 0
    j = 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 left + 1 < right:
        mid = (left + right) // 2;
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)

def partition(A, p, r):
    """
    r: 最後の添字
    """
    x = A[r].num # last item
    i = p - 1
    for j in range(p, r):
        if A[j].num <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    A[i+1], A[r] = A[r], A[i+1]
    return i + 1 # index of the initial A[r]

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 = Card()
    x.suit, x.num = input().split()
    x.num = int(x.num)
    A.append(x)

A_mergeSort = A[:]
mergeSort(A_mergeSort, 0, n)
quickSort(A, 0, n-1)
isStable = True

for i in range(n):
    if A[i].suit == A_mergeSort[i].suit and A[i].num == A_mergeSort[i].num:
        pass
    else:
        isStable = False

print('Stable') if isStable else print('Not stable')

for i in A:
    print(i)