//クイックソートシリーズ
////////////////////////////////////////
#include <iostream>
#include <algorithm> // next_permutation
#include <iomanip>
#include <cmath>
#include <vector>
#include <sstream>
#include <string>
#include <cstdio>
#include <stack>
#include <queue>
#include <list>
#include <numeric> //accumulate
//#include <unordered_map> //ハッシュ関数
#include <fstream> //ifstream, ofstream
#define NDEBUG //NDEBUGが#include <cassert>より前に定義されている場合assertは無効になる。提出時はNDEBUGを定義すること
#include <cassert> //assert
using namespace std;
//デバッグ時はTESTを定義する。本番時はこの行をコメントアウトする
#define TEST //*******************************************************************************************************************************************
//そうすることで、以下に定義する、デバッグ時にのみ標準出力する、doutコマンドが実現できる。本番時はダミーストリームに出力
//ただダミーストリームに出力する処理も結構CPU時間食うようなので、TLEを引き起こす原因になる可能性には注意 ・・・もしかしてcerrを使ったほうがいいのかな???
#ifdef TEST
#define dout cout
#else
stringstream dummy; //デバッグ時のdoutコマンドのダミー出力先
#define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummyを毎回リセットしておかないとメモリ溢れちゃう。
//どうせ表示しないからgoodbitしなくていいけど、表示する場合はこれしておかないとバグるらしいので、勉強のために。詳しくは http://d...content-available-to-author-only...e.jp/linden/20060427/p1
#endif
//標準出力先をテキストファイルにしたい場合はOUTPUT2TEXTFILEを定義する。本番時はこの行をコメントアウトする
//#define OUTPUT2TEXTFILE //*******************************************************************************************************************************************
#ifdef OUTPUT2TEXTFILE
#define dout outputfile //というのはTLE問題でどうせdoutを全部コメントアウトしなくちゃいけなくなるので上記方式は却下して、代わりに出力先を標準出力からファイルに切り替えできるようにする
//TESTが定義されていると、outputfileに出力するようになる
#define OUTPUTFILENAME "output.txt"
ofstream outputfile( OUTPUTFILENAME) ;
#define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
#endif
#define disp(A) dout << #A << " = " << (A) << endl
#define disP(A) dout << setw(3) << (A) << " " // << setw(3) をたまに入れるかも
#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
typedef pair< int ,int > pii;
typedef vector< int > vi;
typedef unsigned long long ll;
const int INF = 1e9 - 1 ;
int partition( pair< char ,int > A[ ] , int p, int r) { //A[p] ... A[r] という数列を、末尾データA[r]をピボットとして、pivot以下、pivotより大きい、の2つのグループに分割して並べ替えて、pivotのindexを返す
int pivot = A[ r] .second ;
int i = p- 1 ; //iまでがpivot以下のデータ。次にpivot以下のデータが見つかった場合、i+1の場所に配置すればよい
rep( j,p,r) {
if ( A[ j] .second <= pivot ) {
i++ ;
//swap A[i] and A[j]
auto tmp = A[ i] ;
A[ i] = A[ j] ;
A[ j] = tmp;
}
}
//swap A[i+1] and pivot=A[r]
auto tmp = A[ i+ 1 ] ;
A[ i+ 1 ] = A[ r] ;
A[ r] = tmp;
return i+ 1 ; //iまでがpivoit以下のデータ、i+1がpivot
}
void quickSort( pair< char ,int > A[ ] , int p, int r) {
if ( p< r) {
int q = partition( A, p, r) ;
quickSort( A, p, q- 1 ) ;
quickSort( A, q+ 1 , r) ;
}
}
int main( ) {
int N; cin >> N;
vector < pair< char ,int > > card, cardCopy;
char suit;
int number;
rep( i,0 ,N) {
cin >> suit >> number;
card.push_back ( make_pair( suit, number) ) ;
}
cardCopy = card;
//番号のみで安定ソート (second要素のnumberだけ比較するように比較関数オブジェクトを与える)
stable_sort( cardCopy.begin ( ) , cardCopy.end ( ) ,
[ ] ( const pair< char ,int > & x, const pair< char ,int > & y) { return x.second < y.second ; } ) ;
//test display
rep( i,0 ,N) {
disP( cardCopy[ i] .first ) ;
disP( cardCopy[ i] .second ) ;
dout << endl;
}
dout << "------------\n " ;
//番号のみでクイックソート
quickSort( & card[ 0 ] , 0 , N- 1 ) ;
//stable or unstable?
bool isStable = true ;
rep( i,0 ,N) {
if ( card[ i] .first ! = cardCopy[ i] .first ) {
isStable = false ;
break ;
}
}
cout << ( isStable ? "Stable" : "Not stable" ) << endl;
//display
rep( i,0 ,N) {
cout << card[ i] .first << " " << card[ i] .second << endl;
}
#ifdef OUTPUT2TEXTFILE
outputfile.close ( ) ;
cout << "\" " << OutputFilePath << "\" " << endl;
#endif
return 0 ;
}
Ly/jgq/jgqTjg4Pjgq/jgr3jg7zjg4jjgrfjg6rjg7zjgroKLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwoKI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPiAvLyBuZXh0X3Blcm11dGF0aW9uCiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPGxpc3Q+CiNpbmNsdWRlIDxudW1lcmljPiAvL2FjY3VtdWxhdGUKLy8jaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4gLy/jg4/jg4Pjgrfjg6XplqLmlbAKI2luY2x1ZGUgPGZzdHJlYW0+IC8vaWZzdHJlYW0sIG9mc3RyZWFtCgojZGVmaW5lIE5ERUJVRyAvL05ERUJVR+OBjCNpbmNsdWRlIDxjYXNzZXJ0PuOCiOOCiuWJjeOBq+Wumue+qeOBleOCjOOBpuOBhOOCi+WgtOWQiGFzc2VydOOBr+eEoeWKueOBq+OBquOCi+OAguaPkOWHuuaZguOBr05ERUJVR+OCkuWumue+qeOBmeOCi+OBk+OBqAojaW5jbHVkZSA8Y2Fzc2VydD4gLy9hc3NlcnQKCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKLy/jg4fjg5Djg4PjgrDmmYLjga9URVNU44KS5a6a576p44GZ44KL44CC5pys55Wq5pmC44Gv44GT44Gu6KGM44KS44Kz44Oh44Oz44OI44Ki44Km44OI44GZ44KLCiNkZWZpbmUgVEVTVCAvLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKLy/jgZ3jgYbjgZnjgovjgZPjgajjgafjgIHku6XkuIvjgavlrprnvqnjgZnjgovjgIHjg4fjg5Djg4PjgrDmmYLjgavjga7jgb/mqJnmupblh7rlipvjgZnjgovjgIFkb3V044Kz44Oe44Oz44OJ44GM5a6f54++44Gn44GN44KL44CC5pys55Wq5pmC44Gv44OA44Of44O844K544OI44Oq44O844Og44Gr5Ye65YqbCi8v44Gf44Gg44OA44Of44O844K544OI44Oq44O844Og44Gr5Ye65Yqb44GZ44KL5Yem55CG44KC57WQ5qeLQ1BV5pmC6ZaT6aOf44GG44KI44GG44Gq44Gu44Gn44CBVExF44KS5byV44GN6LW344GT44GZ5Y6f5Zug44Gr44Gq44KL5Y+v6IO95oCn44Gr44Gv5rOo5oSPICAgICAgICAgICAgICAgICAgICAgICAgICAg44O744O744O744KC44GX44GL44GX44GmY2VycuOCkuS9v+OBo+OBn+OBu+OBhuOBjOOBhOOBhOOBruOBi+OBqu+8n++8n++8nwojaWZkZWYgVEVTVAojZGVmaW5lIGRvdXQgY291dAojZWxzZQpzdHJpbmdzdHJlYW0gZHVtbXk7IC8v44OH44OQ44OD44Kw5pmC44GuZG91dOOCs+ODnuODs+ODieOBruODgOODn+ODvOWHuuWKm+WFiAojZGVmaW5lIGRvdXQgZHVtbXkuc3RyKCIiKTsgZHVtbXkuY2xlYXIoc3RyaW5nc3RyZWFtOjpnb29kYml0KTsgZHVtbXkgLy9kdW1teeOCkuavjuWbnuODquOCu+ODg+ODiOOBl+OBpuOBiuOBi+OBquOBhOOBqOODoeODouODqua6ouOCjOOBoeOCg+OBhuOAggovL+OBqeOBhuOBm+ihqOekuuOBl+OBquOBhOOBi+OCiWdvb2RiaXTjgZfjgarjgY/jgabjgYTjgYTjgZHjganjgIHooajnpLrjgZnjgovloLTlkIjjga/jgZPjgozjgZfjgabjgYrjgYvjgarjgYTjgajjg5DjgrDjgovjgonjgZfjgYTjga7jgafjgIHli4nlvLfjga7jgZ/jgoHjgavjgILoqbPjgZfjgY/jga8gaHR0cDovL2QuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuanAvbGluZGVuLzIwMDYwNDI3L3AxCiNlbmRpZgoKLy/mqJnmupblh7rlipvlhYjjgpLjg4bjgq3jgrnjg4jjg5XjgqHjgqTjg6vjgavjgZfjgZ/jgYTloLTlkIjjga9PVVRQVVQyVEVYVEZJTEXjgpLlrprnvqnjgZnjgovjgILmnKznlarmmYLjga/jgZPjga7ooYzjgpLjgrPjg6Hjg7Pjg4jjgqLjgqbjg4jjgZnjgosKLy8jZGVmaW5lIE9VVFBVVDJURVhURklMRSAvLyoqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioKI2lmZGVmIE9VVFBVVDJURVhURklMRQojZGVmaW5lIGRvdXQgb3V0cHV0ZmlsZSAvL+OBqOOBhOOBhuOBruOBr1RMReWVj+mhjOOBp+OBqeOBhuOBm2RvdXTjgpLlhajpg6jjgrPjg6Hjg7Pjg4jjgqLjgqbjg4jjgZfjgarjgY/jgaHjgoPjgYTjgZHjgarjgY/jgarjgovjga7jgafkuIroqJjmlrnlvI/jga/ljbTkuIvjgZfjgabjgIHku6Pjgo/jgorjgavlh7rlipvlhYjjgpLmqJnmupblh7rlipvjgYvjgonjg5XjgqHjgqTjg6vjgavliIfjgormm7/jgYjjgafjgY3jgovjgojjgYbjgavjgZnjgosKLy9URVNU44GM5a6a576p44GV44KM44Gm44GE44KL44Go44CBb3V0cHV0ZmlsZeOBq+WHuuWKm+OBmeOCi+OCiOOBhuOBq+OBquOCiwojZGVmaW5lIE9VVFBVVEZJTEVOQU1FICJvdXRwdXQudHh0IgpvZnN0cmVhbSBvdXRwdXRmaWxlKE9VVFBVVEZJTEVOQU1FKTsKI2RlZmluZSBPdXRwdXRGaWxlUGF0aCAiL1VzZXJzL05hZy9Eb2N1bWVudHMvUHJnbS9UZXN0L0Rlcml2ZWREYXRhL1Rlc3QvQnVpbGQvUHJvZHVjdHMvRGVidWcvb3V0cHV0LnR4dCIKI2VuZGlmCgojZGVmaW5lIGRpc3AoQSkgZG91dCA8PCAjQSA8PCAiID0gIiA8PCAoQSkgPDwgZW5kbAojZGVmaW5lIGRpc1AoQSkgZG91dCA8PCBzZXR3KDMpIDw8IChBKSA8PCAiICIgLy8gPDwgc2V0dygzKSDjgpLjgZ/jgb7jgavlhaXjgozjgovjgYvjgoIKI2RlZmluZSByZXAoaSxhLG4pIGZvcihpbnQgKGkpPShhKTsgKGkpPChuKTsgKGkpKyspCgojZGVmaW5lIGRpc3BBbGwoQSxuKSBkb3V0IDw8ICNBIDw8ICIgPSAiOyByZXAoaiwgMCwgKG4pKSB7ZGlzUChBW2pdKTt9IGRvdXQgPDwgZW5kbAoKdHlwZWRlZiBwYWlyPGludCxpbnQ+IHBpaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiB1bnNpZ25lZCBsb25nIGxvbmcgbGw7Cgpjb25zdCBpbnQgSU5GID0gMWU5LTE7CgoKCgoKCmludCBwYXJ0aXRpb24ocGFpcjxjaGFyLGludD4gQVtdLCBpbnQgcCwgaW50IHIpIHsgLy9BW3BdIC4uLiBBW3JdIOOBqOOBhOOBhuaVsOWIl+OCkuOAgeacq+WwvuODh+ODvOOCv0Fbcl3jgpLjg5Tjg5zjg4Pjg4jjgajjgZfjgabjgIFwaXZvdOS7peS4i+OAgXBpdm9044KI44KK5aSn44GN44GE44CB44GuMuOBpOOBruOCsOODq+ODvOODl+OBq+WIhuWJsuOBl+OBpuS4puOBueabv+OBiOOBpuOAgXBpdm9044GuaW5kZXjjgpLov5TjgZkKICAgIGludCBwaXZvdCA9IEFbcl0uc2Vjb25kOwogICAgCiAgICBpbnQgaSA9IHAtMTsgLy9p44G+44Gn44GMcGl2b3Tku6XkuIvjga7jg4fjg7zjgr/jgILmrKHjgatwaXZvdOS7peS4i+OBruODh+ODvOOCv+OBjOimi+OBpOOBi+OBo+OBn+WgtOWQiOOAgWkrMeOBruWgtOaJgOOBq+mFjee9ruOBmeOCjOOBsOOCiOOBhAogICAgCiAgICByZXAoaixwLHIpIHsKICAgICAgICBpZiggQVtqXS5zZWNvbmQgPD0gcGl2b3QgKSB7CiAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8vc3dhcCBBW2ldIGFuZCBBW2pdCiAgICAgICAgICAgIGF1dG8gdG1wID0gQVtpXTsKICAgICAgICAgICAgQVtpXSA9IEFbal07CiAgICAgICAgICAgIEFbal0gPSB0bXA7CiAgICAgICAgfQogICAgfQogICAgCiAgICAvL3N3YXAgQVtpKzFdIGFuZCBwaXZvdD1BW3JdCiAgICBhdXRvIHRtcCA9IEFbaSsxXTsKICAgIEFbaSsxXSA9IEFbcl07CiAgICBBW3JdID0gdG1wOwoKICAgIHJldHVybiBpKzE7IC8vaeOBvuOBp+OBjHBpdm9pdOS7peS4i+OBruODh+ODvOOCv+OAgWkrMeOBjHBpdm90Cn0KCgoKdm9pZCBxdWlja1NvcnQocGFpcjxjaGFyLGludD4gQVtdLCBpbnQgcCwgaW50IHIpIHsKICAgIGlmKHA8cikgewogICAgICAgIGludCBxID0gcGFydGl0aW9uKEEsIHAsIHIpOwogICAgICAgIAogICAgICAgIHF1aWNrU29ydChBLCBwLCBxLTEpOwogICAgICAgIHF1aWNrU29ydChBLCBxKzEsIHIpOwogICAgfQp9CgoKCmludCBtYWluKCl7CiAgICAKICAgIGludCBOOyBjaW4gPj4gTjsKICAgIAogICAgdmVjdG9yIDwgcGFpcjxjaGFyLGludD4gPiBjYXJkLCBjYXJkQ29weTsKICAgIGNoYXIgc3VpdDsKICAgIGludCBudW1iZXI7CiAgICByZXAoaSwwLE4pIHsKICAgICAgICBjaW4gPj4gc3VpdCA+PiBudW1iZXI7CiAgICAgICAgCiAgICAgICAgY2FyZC5wdXNoX2JhY2soIG1ha2VfcGFpcihzdWl0LCBudW1iZXIpICk7CiAgICB9CgogICAgY2FyZENvcHkgPSBjYXJkOwoKICAgIAogICAgLy/nlarlj7fjga7jgb/jgaflronlrprjgr3jg7zjg4ggKHNlY29uZOimgee0oOOBrm51bWJlcuOBoOOBkeavlOi8g+OBmeOCi+OCiOOBhuOBq+avlOi8g+mWouaVsOOCquODluOCuOOCp+OCr+ODiOOCkuS4juOBiOOCiykKICAgIHN0YWJsZV9zb3J0KGNhcmRDb3B5LmJlZ2luKCksIGNhcmRDb3B5LmVuZCgpLAogICAgICAgICBbXShjb25zdCBwYWlyPGNoYXIsaW50PiAmeCwgY29uc3QgcGFpcjxjaGFyLGludD4gJnkpIHtyZXR1cm4geC5zZWNvbmQgPCB5LnNlY29uZDt9ICAgKTsKICAgIAogICAgLy90ZXN0IGRpc3BsYXkKICAgIHJlcChpLDAsTikgewogICAgICAgIGRpc1AoY2FyZENvcHlbaV0uZmlyc3QpOwogICAgICAgIGRpc1AoY2FyZENvcHlbaV0uc2Vjb25kKTsKICAgICAgICBkb3V0IDw8IGVuZGw7CiAgICB9CiAgICBkb3V0IDw8ICItLS0tLS0tLS0tLS1cbiI7CgogICAgCiAgICAvL+eVquWPt+OBruOBv+OBp+OCr+OCpOODg+OCr+OCveODvOODiAogICAgcXVpY2tTb3J0KCZjYXJkWzBdLCAwLCBOLTEpOwogICAgCiAgICAKICAgIC8vc3RhYmxlIG9yIHVuc3RhYmxlPwogICAgYm9vbCBpc1N0YWJsZSA9IHRydWU7CiAgICByZXAoaSwwLE4pIHsKICAgICAgICBpZiggY2FyZFtpXS5maXJzdCAhPSBjYXJkQ29weVtpXS5maXJzdCApIHsKICAgICAgICAgICAgaXNTdGFibGUgPSBmYWxzZTsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgfQogICAgCiAgICBjb3V0IDw8IChpc1N0YWJsZSA/ICJTdGFibGUiIDogIk5vdCBzdGFibGUiICkgPDwgZW5kbDsKCiAgICAKICAgIC8vZGlzcGxheQogICAgcmVwKGksMCxOKSB7CiAgICAgICAgY291dCA8PCBjYXJkW2ldLmZpcnN0IDw8ICIgIiA8PCBjYXJkW2ldLnNlY29uZCA8PCBlbmRsOwogICAgfQogICAgCiAgICAKICAgIAogICAgCiAgICAKI2lmZGVmIE9VVFBVVDJURVhURklMRQogICAgb3V0cHV0ZmlsZS5jbG9zZSgpOwogICAgY291dCA8PCAiXCIiIDw8IE91dHB1dEZpbGVQYXRoIDw8ICJcIiIgPDwgZW5kbDsKI2VuZGlmCiAgICAKICAgIHJldHVybiAwOwp9