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: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
# AIZU ONLINE JUDGE
# Introduction to Algorithms and Data Structures
# ALDS1_6_C
# Sort II - Quick Sort

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

def quick_sort(A,B, p, r):
    # q??????????????????p??¨r????????????????????°??????????????§???
    # ?????????p?????????q-1???????????§???????????????????????????q+1???r????¶???????
    # ?????§??????????????§????????????????????¨?????????
    if p < r:
        # ???????????£?????§?????????????°??????°?????????
        q = partition(A,B,p,r)
        quick_sort(A,B,p,q-1)
        quick_sort(A,B,q+1,r)

# alds1_2_c??????
def stable_check(sorted_values,sorted_suits,default_values,default_suits,n):
    for i in xrange(1,10):
        check_ss = []
        check_ds = []
        if i in sorted_values:
            for x in xrange(n):
                if i == sorted_values[x]:
                    check_ss.append(sorted_suits[x])
                if i == default_values[x]:
                    check_ds.append(default_suits[x])
            for x in xrange(len(check_ss)):
                if check_ss[x]!=check_ds[x]:
                    return "Not stable"
    return "Stable"

def main():
    n = input()
    A = []
    B = []
    for i in xrange(n):
        b,a = raw_input().split()
        A.append(int(a))
        B.append(b)
    cpA=list(A)
    setA = set(A)
    cpB=list(B)
    quick_sort(A,B,0,n-1)

    # Stable Check
    print stable_check(A,B,cpA,cpB,n)
    for i in xrange(n):
        line = "%s %s"%(B[i],A[i])
        print line

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def mergesort(A, s, e):
    if s + 1 < e:
        m = (e + s) // 2
        mergesort(A, s, m)
        mergesort(A, m, e)
        merge(A, s, m, e)


def merge(A, s, m, e):
    L = A[s:m] + [('*', 1E10)]
    R = A[m:e] + [('*', 1E10)]
    ix_l = ix_r = 0
    for ix in range(s, e):
        if L[ix_l][1] < R[ix_r][1]:
            A[ix] = L[ix_l]
            ix_l += 1
        else:
            A[ix] = R[ix_r]
            ix_r += 1


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:
        i = partition(A, p, r)
        quicksort(A, p, i - 1)
        quicksort(A, i + 1, r)


if __name__ == '__main__':
    N = int(input().strip())
    AA = [0] * N
    for i in range(N):
        key, val = input().strip().split()
        val = int(val)
        AA[i] = (key, val)
    AA2 = AA
    quicksort(AA, 0, len(AA) - 1)
    mergesort(AA2, 0, len(AA2))
    if all([a == 2 for a, a2 in zip(AA, AA2)]):
        print('Stable')
    else:
        print('Not stable')
    for key, val in AA:
        print('{} {}'.format(key, val))

Submission status: Wrong Answer

Solution code:
def mergesort(A, s, e):
    if s + 1 < e:
        m = (e + s) // 2
        mergesort(A, s, m)
        mergesort(A, m, e)
        merge(A, s, m, e)


def merge(A, s, m, e):
    L = A[s:m] + [('*', 1E10)]
    R = A[m:e] + [('*', 1E10)]
    ix_l = ix_r = 0
    for ix in range(s, e):
        if L[ix_l][1] < R[ix_r][1]:
            A[ix] = L[ix_l]
            ix_l += 1
        else:
            A[ix] = R[ix_r]
            ix_r += 1


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:
        i = partition(A, p, r)
        quicksort(A, p, i - 1)
        quicksort(A, i + 1, r)



if __name__ == '__main__':
    N = int(input().strip())
    AA = [0] * N
    for i in range(N):
        key, val = input().strip().split()
        val = int(val)
        AA[i] = (key, val)
    AA2 = AA[:]
    quicksort(AA, 0, len(AA) - 1)
    mergesort(AA2, 0, len(AA2))
    if all([a == a2 for a, a2 in zip(AA, AA2)]):
        print('Stable')
    else:
        print('Not stable')
    for key, val in AA:
        print('{} {}'.format(key, val))

Submission status: Wrong Answer

Solution code:

def partition(a,b,c,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      b[i],b[j] = b[j],b[i]
      c[i],c[j] = c[j],c[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  b[i+1],b[r] = b[r],b[i+1]  
  c[i+1],c[r] = c[r],c[i+1]
  return i+1
  
def quickSort(a,b,c,p,r):
  if p < r:
    q = partition(a,b,c,p,r-1)
    quickSort(a,b,c,p,q-1)
    quickSort(a,b,c,q+1,r)
  
def checkStable(a,b):
  for i in range(1,len(a)):
    if a[i-1] == a[i]:
      if b[i-1] > b[i]:
        return "Not Stable"
  return "Stable"
  
n = int(input())
mark = [""]*n
num = [0]*n
count = [i for i in range(n)]
for i in range(n):
  mark[i],num[i] = input().split()
num = list(map(int,num))

quickSort(num,mark,count,0,n)
print(checkStable(num,count))
for i in range(n):
  print(mark[i],num[i])

Submission status: Wrong Answer

Solution code:

def partition(a,b,c,p,r):
  x = a[r]
  i = p - 1
  
  for j in range(p,r):
    if x >= a[j]:
      i += 1
      a[i],a[j] = a[j],a[i]
      b[i],b[j] = b[j],b[i]
      c[i],c[j] = c[j],c[i]
      
  a[i+1],a[r] = a[r],a[i+1]
  b[i+1],b[r] = b[r],b[i+1]  
  c[i+1],c[r] = c[r],c[i+1]
  return i+1
  
def quickSort(a,b,c,p,r):
  if p < r:
    q = partition(a,b,c,p,r-1)
    quickSort(a,b,c,p,q-1)
    quickSort(a,b,c,q+1,r)
  
def checkStable(a,b):
  for i in range(1,len(a)):
    if a[i-1] == a[i]:
      if b[i-1] > b[i]:
        return "Not stable"
  return "Stable"
  
n = int(input())
mark = [""]*n
num = [0]*n
count = [i for i in range(n)]
for i in range(n):
  mark[i],num[i] = input().split()
num = list(map(int,num))

quickSort(num,mark,count,0,n)
print(checkStable(num,count))
for i in range(n):
  print(mark[i],num[i])

Submission status: Wrong Answer

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)


def stableSort(input, output):
    n = len(input)
    for i in range(n):
        for j in range(i + 1, n):
            for a in range(n):
                for b in range(a + 1, n):
                    if input[i][1] == input[j][1] and input[i] == output[b] and input[j] == output[a]:
                        return print("Not stable")
    return print("Stable")


if __name__ == "__main__":
    n = int(input())
    card = []
    for i in range(n):
        card.append(input().split())
    input = card[:]
    quickSort(card, 0, n - 1)

    stableSort(input,card)
    for i in range(n):
        print(*card[i])

Submission status: Wrong Answer

Solution code:
def partition(A, p, r):
  x = A[r][0]
  i = p - 1
  for j in range(p, r):
    if A[j][0] <= 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 is_stable(A, B):
  ma = {}
  for suit, num in A:
    if num not in ma: ma[num] = []
    ma[num].append(suit)

  mb = {}
  for suit, num in B:
    if num not in mb: mb[num] = []
    mb[num].append(suit)

  for num in ma:
    if ma[num] != mb[num]: return False

  return True

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

B = A[:]
quick_sort(A, 0, len(A) - 1)
print("Stable" if is_stable(A, B) else "Not stable")
for suit, num in A: print("{} {}".format(num, suit))

Submission status: Wrong Answer

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

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

def check(A, s, e):
   for i in range(s,e-1):
      if A[i][1] == A[i+1][1]:
         if A[i][2] > A[i+1][2]:
            return "Not stable"
   return "Stable"

r = int(input())
a = []
for i in range(r):
   c = input().split()
   a.append((c[0],int(c[1]),i))
quickSort(a, 0, r-1)
print(check(a,0,r))
for s,r,d in a:
   print("{} {}".format(s,r))

Submission status: Wrong Answer

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

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, s, e):
   for i in range(s,e-1):
      if A[i][1] == A[i+1][1]:
         if A[i][2] > A[i+1][2]:
            return "Not stable"
   return "Stable"

r = int(input())
a = []
for i in range(r):
   c = input().split()
   a.append((c[0],int(c[1]),i))
quickSort(a, 0, r-1)
print(check(a,0,r))
for s,r,d in a:
   print("{} {}".format(s,r))

Submission status: Wrong Answer

Solution code:
# coding=utf-8

def partition(A, p, r):
    x = A[r][1]
    i = p-1
    for j in range(p, r):
        if A[j][1] <= x:
            A[i+1], A[j] = A[j], A[i+1]
            i += 1
    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())
input_card = [input().split() for k in range(n)]
for i in range(n):
    input_card[i][1] = int(input_card[i][1])
sorted_card = input_card.copy()

quick_sort(sorted_card, 0, n-1)
if input_card == sorted_card:
    print("Stable")
else:
    print("Not stable")

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

Submission status: Wrong Answer

Solution code:
import sys

MAX = 1000000001

def merge(A, left, mid, right, idx):
    n1 = mid - left
    n2 = right - mid

    L = A[left:mid]
    R = A[mid:right]

    L.append(["X",MAX])
    R.append(["X",MAX])

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

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

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

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

def quickSort(A, p, r, i):
    if r - p > 1:
        q = partition(A, p, r, i)
#        print(A)
#        print("p:{} r:{} q:{} i:{}".format(p,r,q,i))
        quickSort(A, p, q - 1, i)
        quickSort(A, q + 1, r, i)

def main():
    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cards = list(istr.splitlines())
    
    A = [[0,0] for i in range(num)]
    B = [[0,0] for i in range(num)]
    
    for i in range(num):
        A[i][0] = cards[i][0]
        A[i][1] = int(cards[i][2:])
        B[i][0] = cards[i][0]
        B[i][1] = int(cards[i][2:])

    quickSort(A, 0, num-1,1)
    mergeSort(B, 0, num, 1)

    res = "Stable"
    for i in range(num):
        if A[i][0] != B[i][0] or A[i][1] != B[i][1]:
            res = "Not stable"
            break

    print(res)
    for x in A:
        print(" ".join(map(str, x)))
        
#    for x in B:
#        print(" ".join(map(str, x)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

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

def mid(a,b):
    x = int((b-a)/2)
    if x == 0:
        x = 1
    return x + a

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

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

def main():
    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cards = list(istr.splitlines())
    
    A = [[0,0] for i in range(num)]
    B = [[0,0] for i in range(num)]
    
    for i in range(num):
        A[i][0] = cards[i][0]
        A[i][1] = int(cards[i][2:])
        B[i][0] = cards[i][0]
        B[i][1] = int(cards[i][2:])

    quickSort(A, 0, num-1,1)
    B.sort(key = lambda d:d[1])
    res = "Stable"
    for i in range(num):
        if A[i][0] != B[i][0] or A[i][1] != B[i][1]:
            res = "Not stable"
            break
#        if A[i][1] != B[i][1]:
#            print("{:5} A:{} {} B:{} {}".format(i, A[i][0], A[i][1], B[i][0], B[i][1]))

    print(res)
    for x in A:
        print(" ".join(map(str, x)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys

def swap(A, i, j):
    print("\tswap {}:{} {}:{}".format(i,A[i],j,A[j]))
    x = A[i]
    A[i] = A[j]
    A[j] = x

def partition(A, p, r, idx):
    x = A[r][idx]
    i = p - 1
    for j in range(p, r):
        aj = A[j][idx]
        if aj < x:
            i += 1
            print(" x:{} j{}:{} i{}:{}".format(x,j,A[j],i,A[i]))
            if(i != j):
                swap(A, i, j)
    i += 1
    swap(A, i, r)
    return i

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

def main():
    """ ????????? """
    num = int(input().strip())
    istr = sys.stdin.read()
    cards = list(istr.splitlines())
    
    A = [[0,0] for i in range(num)]
    B = [[0,0] for i in range(num)]
    
    for i in range(num):
        A[i][0] = cards[i][0]
        A[i][1] = int(cards[i][2:])
        B[i][0] = cards[i][0]
        B[i][1] = int(cards[i][2:])

    quickSort(A, 0, num-1,1)
    B.sort(key = lambda d:d[1])
    res = "Stable"
    for i in range(num):
        if A[i][0] != B[i][0] or A[i][1] != B[i][1]:
            res = "Not stable"
            break

    print(res)
    for x in A:
        print(" ".join(map(str, x)))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n = int(input())
C = []

for i in range(n):
    a,b = input().split()
    C.append((a, b))

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, p + 1, r)

s = sorted(C, key=itemgetter(1) )

quicksort(C, 0, n - 1)

if s == C:
    print('Stable')
else:
    print('Not stable')
for c in C:
    print(' '.join(map(str, c)))

Submission status: Wrong Answer

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

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

def isStable(a, b):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            for x in range(length):
                for y in range(x+1,length-1) :
                    if a[i][2]==a[j][2] and a[i] == b[y] and a[j] == b[x]:
                        return False
                        break
    return True

if __name__ == '__main__':
    cnt = int(input())
    A = []
    for i in range(cnt):
        A.append(input())
    A2 = A[:]
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(A2,B):
        print("Stable")
    else:
        print("Not Stable")
    for i in B:
        print (i)

Submission status: Wrong Answer

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

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

def isStable(a, b):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            for x in range(length):
                for y in range(x+1,length-1) :
                    if a[i][2]==a[j][2] and a[i] == b[y] and a[j] == b[x]:
                        return False
                        break
    return True

if __name__ == '__main__':
    cnt = int(input())
    A = []
    for i in range(cnt):
        A.append(input())
    A2 = A[:]
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(A2,B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print (i)

Submission status: Wrong Answer

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

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

def isStable(a, b):
    length = int(len(a))
    for i in range(length):
        for j in range(i+1,length-1) :
            for x in range(length):
                for y in range(x+1,length-1) :
                    if a[i][1]==a[j][1] and a[i] == b[y] and a[j] == b[x]:
                        return False
                        break
    return True

if __name__ == '__main__':
    cnt = int(input())
    A = []
    for i in range(cnt):
        A.append(input().split())
    A2 = A[:]
    p = 0
    r = len(A)
    B = qsort(A,p,r)
    if isStable(A2,B):
        print("Stable")
    else:
        print("Not stable")
    for i in B:
        print (i)

Submission status: Wrong Answer

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

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

def quick(A,p=0,r=None):
    "16c"
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(input())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
        A.append([card[0], int(card[1]), i])
    quick(A)
    if isStable(A):
        print("Stable")
    else:
        print("Not Stable")
    for card in A:
        print(card[0], card[1])

Submission status: Wrong Answer

Solution code:
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

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

def quick(A,p=0,r=None):
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
        A.append([card[0], int(card[1]), i])
    quick(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for card in A:
        print(card[0], card[1])

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [(input() + " " + str(i)).split() for i in range(n)]
b = 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 checkStable(a):
    for i in range(len(a) - 1):
        if a[i][1] == a[i + 1][1] and a[i][2] > a[i + 1][2]:
            return "Not stable"
    return "Stable"

quickSort(a, 0, n - 1)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [(input() + " " + str(i)).split() for i in range(n)]
b = 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 checkStable(a):
    for i in range(len(a) - 1):
        if a[i][1] == a[i + 1][1] and int(a[i][2]) > int(a[i + 1][2]):
            return "Not stable"
    return "Stable"

quickSort(a, 0, n - 1)

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

Submission status: Wrong Answer

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, p-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: Wrong Answer

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: Wrong Answer

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

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

else:
    print "Stable"

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

Submission status: Wrong Answer

Solution code:
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

    base_cards = cards.copy()
    quickSort(cards, 0, len(cards) - 1)

    for c in cards:
        print(c.cha, c.num)

    print(check_stable(base_cards, cards))


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


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

    for j in range(p, r):
        if A[j].num <= x.num:
            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 check_stable(base, card):
    for i in range(0, len(card) - 1):
        if base.index(card[i]) > base.index(card[i + 1]):
            return 'Not stable'

    return 'Stable'


class Card:
    def __init__(self, imp):
        cha, num = imp.split(' ')
        self.cha = cha
        self.num = int(num)


main()

Submission status: Wrong Answer

Solution code:
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

    base_cards = cards.copy()
    quickSort(cards, 0, len(cards) - 1)

    print(check_stable(base_cards, cards))
    for c in cards:
        print(c.cha, c.num)


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


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

    for j in range(p, r):
        if A[j].num <= x.num:
            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 check_stable(base, card):
    for i in range(0, len(card) - 1):
        if base.index(card[i]) > base.index(card[i + 1]):
            return 'Not stable'

    return 'Stable'


class Card:
    def __init__(self, imp):
        cha, num = imp.split(' ')
        self.cha = cha
        self.num = int(num)


main()

Submission status: Wrong Answer

Solution code:
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

    base_cards = cards.copy()
    quickSort(cards, 0, len(cards) - 1)

    print(check_stable(base_cards, cards))
    for c in cards:
        print(c.cha, c.num)


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


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

    for j in range(p, r):
        if A[j].num <= x.num:
            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 check_stable(base, card):
    for i in range(0, len(card) - 1):
        if base.index(card[i]) > base.index(card[i + 1]):
            return 'Not stable'

    return 'Stable'


class Card:
    def __init__(self, imp):
        cha, num = imp.split(' ')
        self.cha = cha
        self.num = int(num)


main()

Submission status: Wrong Answer

Solution code:
def main():
    cards = []
    for _ in range(int(input())):
        cards.append(Card(input()))

    base_cards = cards.copy()
    quickSort(cards, 0, len(cards) - 1)

    print(check_stable(base_cards, cards))
    for c in cards:
        print(c.cha, c.num)


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


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

    for j in range(p, r):
        if A[j].num <= x.num:
            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 check_stable(base, card):
    for i in range(0, len(card) - 1):
        if base.index(card[i]) > base.index(card[i + 1]):
            return 'Not stable'

    return 'Stable'


class Card:
    def __init__(self, imp):
        cha, num = imp.split(' ')
        self.cha = cha
        self.num = int(num)


main()