Problem 2669 --Sort II - Quick Sort

2669: Sort II - Quick Sort

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $18$ 正确数量 $2$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 STL

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] <= x 

5        then i = i+1 

6            exchange A[i] and A[j] 

7 exchange A[i+1] and A[r] 

8 return i+1 

    Quicksort(A, p, r) 

1   if p < r 

2      then q = Partition(A, p, r) 

3           run Quicksort(A, p, q-1) 

4           run Quicksort(A, q+1, r) 

Here, A is an array which represents a deck of cards and comparison operations are performed based on the numbers.

Your program should also report the stability of the output for the given input (instance). Here, 'stability of the output' means that: cards with the same value appear in the output in the same order as they do in the input (instance).

The first line contains an integer 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.

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.

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

1 ≤ n ≤ 100,000 

1 ≤ the number of a card ≤ 10^9 

There are no identical card in the input

推荐代码 查看2669 所有题解 上传题解视频得图灵币

本题记录 用 户(点击查看用户) 运行号(点击购买题解) 时 间
算法最快[$48 $ms] 囧囧JOJO 756670 2021-06-13 23:19:49
内存最少[$4312 $KB] 囧囧JOJO 756670 2021-06-13 23:19:49
第一AC 囧囧JOJO 756670 2021-06-13 23:19:49
第一挑战 计爱玲 360193 2019-01-15 19:24:07

赛题来源/所属竞赛 会津大学《挑战数据结构与算法》 挑战数据结构与算法

竞赛编号 竞赛名称 竞赛时间 访问比赛