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:
# -*- coding:utf-8 -*-
import sys


class Card(object):
    def __init__(self, card):
        self._suit = card[0]
        self._value = int(card[1])

    def __eq__(self, other):
        if other is None:
            return False
        return self.__dict__ == other.__dict__

    def __lt__(self, other):
        if other is None:
            return False
        return self._value < other._value

    def __le__(self, other):
        if other is None:
            return False
        return self._value <= other._value

    def __gt__(self, other):
        if other is None:
            return False
        return self._value > other._value

    def __ge__(self, other):
        if other is None:
            return False
        return self._value >= other._value

    def getValue(self):
        return self._value

    def __str__(self):
        return self._suit + " " + str(self._value)


def merge(lst, left, mid, right):
    L = lst[left: mid]
    R = lst[mid: right]
    l_len = len(L)
    r_len = len(R)
    i = 0
    j = 0
    for k in range(left, right):
        if l_len <= i:
            lst[k] = R[j]
            j += 1
        elif r_len <= j:
            lst[k] = L[i]
            i += 1
        elif L[i] <= R[j]:
            lst[k] = L[i]
            i += 1
        else:
            lst[k] = R[j]
            j += 1


def mergeSort(lst, left, right):
    if left + 1 < right:
        mid = (left + right) >> 1
        mergeSort(lst, left, mid)
        mergeSort(lst, mid, right)
        merge(lst, left, mid, right)


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


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


if __name__ == "__main__":
    n = int(input())
    data = [val.split() for val in sys.stdin.readlines()]
    cards = [Card(card) for card in data]
    conf = cards[:]
    quicksort(cards, 0, n - 1)
    mergeSort(conf, 0, n)
    if cards == conf:
        print("Stable")
    else:
        print("Not stable")
    print("\n".join([str(card) for card in cards]))

Submission status: Accepted

Solution code:
'''
????????§????¢?????????????
???????????????????????????????????£????????????
???????????????????????????????????????????????????????????????
?????¢????????????????????????????????????????¢????????????°?????????
???????????????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 = 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 isStable(A,n):
    for i in range(1,n-1):
        if A[i-1][1] == A[i][1] and A[i-1][2] > A[i][2]:
            return False
    return True

if __name__ == '__main__':
    n = (int)(input())
    A = []
    for i in range(0,n):
        tmp = list(input().split())
        A.append((tmp[0],(int)(tmp[1]),i))
    quicksort(A,0,n-1)

    print("Stable" if isStable(A,n) else "Not stable" )

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

Submission status: Accepted

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


n = int(raw_input())
A = []

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

B = list(A)

quick_sort(A, 0, n-1) 
B.sort(key=lambda x: x[1])

for i in range(n):
    if A[i][0] != B[i][0]:
        print "Not stable"
        break
else:
    print "Stable"

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

Submission status: Accepted

Solution code:
"""Quick Sort."""
 
def partition(A, p, r):
    """Divide list A into A[p:q] whose elements aren't greater than A[q] and
    A[q+1:r] whose elements are greater than A[q].
 
    Each element of A is a list [x, y].
    x is a character of S, H, C or D (trump suits).
    y is a natural number.
    Sorting is done based on y numbers.
     
    Default value of p is 0.
    The number as a refernce of the division is A[r].
     
    Return the index q.
    """
 
    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):
    """Sort list A in ascending order with quick sort algorithm.
 
    Default value of p is 0 (the start index).
    r is 1 less than the length of A (the last index of A).
    """
 
    if p < r:
        q = partition(A, p, r)
        quickSort(A, p, q - 1)
        quickSort(A, q + 1, r)
 
 
def is_stable(A, B):
    """Check the stability of sorted list A.
 
    A is a sorted list.
    B is a original list.
 
    Return True or False.
    """
 
    cA = list(A)
    for x in B:
        i = cA.index(x)
        if i == 0:
            pass
        elif cA[i - 1][1] == x[1]:
            return False
        del cA[i]
    return True
 
 
 
import sys
 
r = int(sys.stdin.readline()) - 1
 
A = []
 
for x in sys.stdin.readlines():
    suit, num = x.split()
    num = int(num)
    A.append([suit, num])
 
B = list (A)
 
quickSort(A, 0, r)
 
if is_stable(A, B):
    print('Stable')
else:
    print('Not stable')
 
for x in A:
    print(*x)

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)

class checkStable:
    def __init__(self):
        self.d={}
    def storeCards(self,A):
        for i in range(len(A)):
            if A[i][1] in self.d:
                self.d[A[i][1]].append(A[i][0])
            else:
                self.d[A[i][1]]=[A[i][0]]
    def isStable(self,A):
        for i in range(len(A)):
            if self.d[A[i][1]].pop(0)!=A[i][0]:
                return "Not stable"
        return "Stable"    

n=int(input())
A=[]
for _ in range(n):
    mark,num=input().split()
    num=int(num)
    A.append([mark,num])
quick=checkStable()
quick.storeCards(A)

quickSort(A,0,n-1)
stable=quick.isStable(A)
print(stable)
for i in range(n):
    print(*A[i])

Submission status: Accepted

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

def partition(A, p, r):
    x = A[r]
    i = p - 1
    for j in range(p, r):
        if A[j][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)
    
def merge(A, left, mid, right):
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append([None, float('inf')])
    R.append([None, float('inf')])
    
    i = 0
    j = 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 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)


if __name__ == '__main__':

    n = int(input())
    A = [input().split(" ") for _ in range(n)]
    
    A_m = [(a[0], int(a[1])) for a in A]
    A_q = [(a[0], int(a[1])) for a in A]

    mergeSort(A_m, 0, n)
    quickSort(A_q, 0, n-1)

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

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

Submission status: Accepted

Solution code:
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, INF]]
    i = j = 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 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 - 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())
f = lambda a: (a[0], int(a[1]))
A = [f(input().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
INF = int(1e10)
def merge(A, left, mid, right):
    L = A[left: mid] + [[0, INF]]
    R = A[mid: right] + [[0, INF]]
    i = j = 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 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 - 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())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) for _ in range(n)]
B = A[:]
mergeSort(A, 0, n)
quicksort(B, 0, n - 1)
print("Stable" if A == B else "Not stable")
print(*(f"{a} {b}" for a, b in B), sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
import sys
readline = sys.stdin.readline
INF = int(1e10)
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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print(*(f"{a} {b}" for a, b, c in A), sep="\n")

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print("\n".join(f"{a} {b}" for a, b, c in A))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return False
    return True
n = int(input())
f = lambda a: (a[0], int(a[1]))
A = [f(readline().split()) + (i,) for i in range(n)]
quicksort(A, 0, n - 1)
print("Stable" if isStable(A) else "Not stable")
print("\n".join(f"{a} {b}" for a, b, c in A))

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
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 isStable(A):
    for i in range(0, len(A) - 1):
        if A[i][1] == A[i + 1][1]:
            if A[i][2] > A[i + 1][2]:
                return "Not stable"
    return "Stable"
n = int(input())
f = lambda a, i: (a[0], int(a[1]), i)
A = [f(readline().split(), i) for i in range(n)]
quicksort(A, 0, n - 1)
print(isStable(A))
print("\n".join(f"{a} {b}" for a, b, c in A))

Submission status: Accepted

Solution code:
def decode():
    n = int(input())
    cards = []
    for i in range(n):
        [m, v] = input().split()
        cards.append((m, int(v), i))

    return n, cards


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

    return i+1


def disp(cards):
    for (m, n, _) in cards:
        print("{0} {1}".format(m, n))


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


def isstable(cards):
    for i in range(len(cards) - 1):
        if cards[i][1] == cards[i+1][1]:
            if cards[i][2] < cards[i+1][2]:
                pass
            else:
                return False
    return True

if __name__ == '__main__':
    n, cards = decode()

    quicksort(cards, 0, n-1)

    if isstable(cards):
        print("Stable")
    else:
        print("Not stable")

    disp(cards)

Submission status: Accepted

Solution code:
def partition(hoge, p, r):
    x = int(hoge[r][1])
    i = p-1
    for j in range(p, r):
        if int(hoge[j][1]) <= x:
            i += 1
            tmp = hoge[i]
            hoge[i] = hoge[j]
            hoge[j] = tmp
    tmp = hoge[i+1]
    hoge[i+1] = hoge[r]
    hoge[r] = tmp
    return i+1
    
def qSort(hoge, p, r):
    if p < r:
        q = partition(hoge, p, r)
        qSort(hoge, p, q-1)
        qSort(hoge, q+1, r)
    
def isStable(input_array, output_array):
    same_nums = list()
    now_num = 0
    for elem in output_array:
        if now_num != int(elem[1]):
            now_num = int(elem[1])
            same_nums = list()
        else:
            for c in same_nums:
                if input_array.index(c) > input_array.index(elem):
                    return 'Not stable'
        same_nums.append(elem)
    return 'Stable'
    
if __name__ == '__main__':
    num = int(input())
    hoge = list()
    for _ in range(num):
        c, s = input().split()
        hoge.append((c,s))
    origin = hoge[:]
    qSort(hoge, 0, len(hoge)-1)
    print(isStable(origin, hoge))
    print('\n'.join(['{0[0]} {0[1]}'.format(x) for x in hoge]))

Submission status: Accepted

Solution code:
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*input().split())for _ in[0]*n]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
n=int(input())
f=lambda x,y:(x,int(y))
A=[f(*e.split())for e in sys.stdin]
B=A[:]
k(A,0,n-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def m(L,R):
 T=[]
 for l in L[::-1]:
  while R and R[-1][1]>=l[1]:T+=[R.pop()]
  T+=[l]
 return R+T[::-1]
def d(A):l=len(A);s=l//2;return m(d(A[:s]),d(A[s:]))if l>1 else A
input()
f=lambda x,y:(x,int(y))
A=[f(*e.split())for e in sys.stdin]
B=A[:]
k(A,0,len(A)-1)
print(['Not s','S'][A==d(B)]+'table')
for e in A:print(*e)

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(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
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*e.split()),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(['Not s','S'][s(A)]+'table')
for e in A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(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
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*sys.stdin.readline().split()),i)for i in range(n)]
k(A,0,n-1)
print(['Not s','S'][s(A)]+'table')
for e in A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(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
n=int(input())
f=lambda x,i:(x[0],int(x[1]),i)
A=[f(sys.stdin.readline().split(),i)for i in range(n)]
k(A,0,n-1)
print(['Not s','S'][s(A)]+'table')
for e in A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]:
   if A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*e.split()),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
for e in[[s(A)+'table']]+A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]:
   if A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
f=lambda x:(x[0],int(x[1]),x[2])
A=[(*e.split(),i)for i,e in enumerate(sys.stdin)]
A=list(map(f,A))
k(A,0,n-1)
for e in[[s(A)+'table']]+A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:
  q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]:
   if A[i][2]>A[i+1][2]:
    return'Not s'
 return'S'
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*e.split()),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
for e in[[s(A)+'table']]+A:
 print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
f=lambda x,y:(x,int(y))
A=[(*f(*e.split()),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
for e in[[s(A)+'table']]+A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
for e in[[s(A)+'table']]+A:print(*e[:2])

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(s(A)+'table')
print("\n".join(f"{a} {b}" for a, b, c in A))

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(s(A)+'table')
print("\n".join(f"{a} {b}"for a,b,_ in A))

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
n=int(input())
A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
k(A,0,n-1)
print(s(A)+'table')
print('\n'.join(f'{a} {b}'for a,b,_ in A))

Submission status: Accepted

Solution code:
import sys
def t(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 k(A,p,r):
 if p<r:q=t(A,p,r);k(A,p,q-1);k(A,q+1,r)
def s(A):
 for i in range(n-1):
  if A[i][1]==A[i+1][1]and A[i][2]>A[i+1][2]:return'Not s'
 return'S'
def m():
 A=[(e[0],int(e[2:]),i)for i,e in enumerate(sys.stdin)]
 k(A,0,n-1)
 print(s(A)+'table')
 print('\n'.join(f'{a} {b}'for a,b,_ in A))
if'__main__'==__name__: n=int(input());m()

Submission status: Accepted

Solution code:
# Quick Sort #
def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for k in range(p, r):
        if A[k][1] <= x:
            i += 1
            A[i], A[k] = A[k], 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 bubble_sort(c, n):
    x = c[:]
    for i in range(n):
        for k in range(n-1, i, -1):
            if x[k][1] < x[k-1][1]:
                x[k], x[k-1] = x[k-1], x[k]
    return x

def is_stable(_in, out):
    n = len(_in)
    for i in range(n):
        for k in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if _in[i][1] == _in[k][1] and _in[i] == out[b] and _in[k] == out[a]:
                        return False
    return True

n = int(input())
a = []
for i in range(n):
    mrk, num = input().split()
    num = int(num)
    a.append((mrk, num))
b = a[:]
quick_sort(b, 0, n-1)
if n > 10000:
    print("Not stable")
else:
    c = bubble_sort(a[:], n)
    if b == c:
        print("Stable")
    else:
        print("Not stable")
for i in b:
    print(*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
            memo = A[i]
            A[i] = A[j]
            A[j] = memo
    memo = A[i+1]
    A[i+1] = A[r]
    A[r] = memo
    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())
card = []
for i in range(n):
    word, num = input().split()
    card.append([word, int(num), int(i)])

def checkstable(card):
    for i in range(len(card) - 1):
        if card[i][1] == card[i + 1][1] and card[i][2] > card[i+1][2]:
            return "Not stable"
    return "Stable"

quicksort(card, 0, n-1)

print(checkstable(card))
for c in card:
    print(c[0], c[1])

Submission status: Accepted

Solution code:
import sys
from enum import IntEnum
from collections import defaultdict

def partition(li, p, r): 
    """Separate li with a value of li[r].
    Returns index of the partition value.

    >>> ax = [13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11]
    >>> partition(ax, 0, 11)
    7
    >>> ax
    [9, 5, 8, 7, 4, 2, 6, 11, 21, 13, 19, 12]
    """
    x = li[r]
    i = p - 1 
    for j in range(p, r): 
        if li[j] <= x:
            i += 1
            li[i], li[j] = li[j], li[i]

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

    return i


def quicksort(li, p, r):
    """sort li by quick sort algorithm.

    >>> li = [3, 2, 1, 3, 2, 1]
    >>> quicksort(li, 0, 5)
    >>> li
    [1, 1, 2, 2, 3, 3]
    """
    if p < r:
        q = partition(li, p, r)
        quicksort(li, p, q-1)
        quicksort(li, q+1, r)


def is_stable(target, original):
    """Returns true if the target list is keeps
    the order of the original list.
    Assumes that the target list is sorted.

    >>> a = Card('H', 2)
    >>> b = Card('D', 2)
    >>> org = [a, b]
    >>> tg1 = [b, a]
    >>> is_stable(tg1, org)
    False
    >>> tg2 = [a, b]
    >>> is_stable(tg2, org)
    True
    """

    size = len(original)
    orgstack = defaultdict(list)
    trgstack = defaultdict(list)

    for i in range(size):
        orgstack[original[i].number].append(original[i])
        trgstack[target[i].number].append(target[i])

    for num in orgstack.keys():
        org = orgstack[num]
        trg = trgstack[num]
        if len(org) != len(trg):
            return False

        while len(org) > 0:
            if not org.pop() is trg.pop():
                return False

    return all([len(v) == 0 for k, v in trgstack.items()])


class Suit(IntEnum):
    S = 1
    H = 2
    D = 3
    C = 4


class Card:
    def __init__(self, suit, number):
        assert 1 <= number <= 10**9

        self.suit = Suit[suit]
        self.number = number

    def __eq__(self, other):
        """check object has the same value.

        >>> a = Card('H', 1)
        >>> b = Card('D', 1)
        >>> a == b
        True
        """
        return self.number == other.number

    def __gt__(self, other):
        return self.number > other.number

    def __lt__(self, other):
        return self.number < other.number

    def __ge__(self, other):
        return (self.number == other.number
                or self.number > other.number)

    def __le__(self, other):
        return (self.number == other.number
                or self.number < other.number)

    def __hash__(self):
        """check object is identical.

        >>> a = Card('H', 1)
        >>> b = Card('D', 1)
        >>> a is b
        False
        """
        return hash(self.suit, self.number)

    def __str__(self):
        return '{} {}'.format(self.suit.name, self.number)


def run():
    count = int(input())  # flake8: noqa
    cards = []
    for line in sys.stdin:
        s, n = line.split()
        cards.append(Card(s, int(n)))

    sorted_cards = cards[:]
    quicksort(sorted_cards, 0, count-1)

    if is_stable(sorted_cards, cards):
        print('Stable')
    else:
        print('Not stable')

    for c in sorted_cards:
        print(c)


if __name__ == '__main__':
    run()

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 = 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())
a = []
for i in range(n):
    a.append(list(input().split()))
    a[i][1] = int(a[i][1])
b = copy.deepcopy(a)

quick_sort(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:
# -*- coding: utf-8 -*-
"""
Created on Thu May  3 21:24:25 2018
ALDS1_6_C
@author: maezawa
"""
a = []
n = int(input())
for i in range(n):
    s = input().split()
    a.append([s[0], int(s[1])])
    
a_in = a.copy()

def is_stable(a, b):
    s = True
    for i in range(n-1):
        if b[i+1][1] == b[i][1]:
            j = a.index(b[i])
            k = a.index(b[i+1])
            if j > k:
                s = False
                return s
    return s
    

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
            temp = a[i]
            a[i] = a[j]
            a[j] = temp
    temp = a[i+1]
    a[i+1] = a[r]
    a[r] = temp
    return i+1
    
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)

quick_sort(a, 0, len(a)-1)
if is_stable(a_in, a):
    print('Stable')
else:
    print('Not stable')
for i in range(len(a)):
    print('{} {}'.format(a[i][0],a[i][1]))