fork download
copy 
  1. //クイックソートシリーズ
  2. ////////////////////////////////////////
  3.  
  4. #include <iostream>
  5. #include <algorithm> // next_permutation
  6. #include <iomanip>
  7. #include <cmath>
  8. #include <vector>
  9. #include <sstream>
  10. #include <string>
  11. #include <cstdio>
  12. #include <stack>
  13. #include <queue>
  14. #include <list>
  15. #include <numeric> //accumulate
  16. //#include <unordered_map> //ハッシュ関数
  17. #include <fstream> //ifstream, ofstream
  18.  
  19. #define NDEBUG //NDEBUGが#include <cassert>より前に定義されている場合assertは無効になる。提出時はNDEBUGを定義すること
  20. #include <cassert> //assert
  21.  
  22.  
  23. using namespace std;
  24.  
  25. //デバッグ時はTESTを定義する。本番時はこの行をコメントアウトする
  26. #define TEST //*******************************************************************************************************************************************
  27. //そうすることで、以下に定義する、デバッグ時にのみ標準出力する、doutコマンドが実現できる。本番時はダミーストリームに出力
  28. //ただダミーストリームに出力する処理も結構CPU時間食うようなので、TLEを引き起こす原因になる可能性には注意                           ・・・もしかしてcerrを使ったほうがいいのかな？？？
  29. #ifdef TEST
  30. #define dout cout
  31. #else
  32. stringstream dummy; //デバッグ時のdoutコマンドのダミー出力先
  33. #define dout dummy.str(""); dummy.clear(stringstream::goodbit); dummy //dummyを毎回リセットしておかないとメモリ溢れちゃう。
  34. //どうせ表示しないからgoodbitしなくていいけど、表示する場合はこれしておかないとバグるらしいので、勉強のために。詳しくは http://d...content-available-to-author-only...e.jp/linden/20060427/p1
  35. #endif
  36.  
  37. //標準出力先をテキストファイルにしたい場合はOUTPUT2TEXTFILEを定義する。本番時はこの行をコメントアウトする
  38. //#define OUTPUT2TEXTFILE //*******************************************************************************************************************************************
  39. #ifdef OUTPUT2TEXTFILE
  40. #define dout outputfile //というのはTLE問題でどうせdoutを全部コメントアウトしなくちゃいけなくなるので上記方式は却下して、代わりに出力先を標準出力からファイルに切り替えできるようにする
  41. //TESTが定義されていると、outputfileに出力するようになる
  42. #define OUTPUTFILENAME "output.txt"
  43. ofstream outputfile(OUTPUTFILENAME);
  44. #define OutputFilePath "/Users/Nag/Documents/Prgm/Test/DerivedData/Test/Build/Products/Debug/output.txt"
  45. #endif
  46.  
  47. #define disp(A) dout << #A << " = " << (A) << endl
  48. #define disP(A) dout << setw(3) << (A) << " " // << setw(3) をたまに入れるかも
  49. #define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
  50.  
  51. #define dispAll(A,n) dout << #A << " = "; rep(j, 0, (n)) {disP(A[j]);} dout << endl
  52.  
  53. typedef pair<int,int> pii;
  54. typedef vector<int> vi;
  55. typedef unsigned long long ll;
  56.  
  57. const int INF = 1e9-1;
  58.  
  59.  
  60.  
  61.  
  62.  
  63.  
  64. int partition(pair<char,int> A[], int p, int r) { //A[p] ... A[r] という数列を、末尾データA[r]をピボットとして、pivot以下、pivotより大きい、の2つのグループに分割して並べ替えて、pivotのindexを返す
  65.     int pivot = A[r].second;
  66.  
  67.     int i = p-1; //iまでがpivot以下のデータ。次にpivot以下のデータが見つかった場合、i+1の場所に配置すればよい
  68.  
  69.     rep(j,p,r) {
  70.         if( A[j].second <= pivot ) {
  71.             i++;
  72.  
  73.             //swap A[i] and A[j]
  74.             auto tmp = A[i];
  75.             A[i] = A[j];
  76.             A[j] = tmp;
  77.         }
  78.     }
  79.  
  80.     //swap A[i+1] and pivot=A[r]
  81.     auto tmp = A[i+1];
  82.     A[i+1] = A[r];
  83.     A[r] = tmp;
  84.  
  85.     return i+1; //iまでがpivoit以下のデータ、i+1がpivot
  86. }
  87.  
  88.  
  89.  
  90. void quickSort(pair<char,int> A[], int p, int r) {
  91.     if(p<r) {
  92.         int q = partition(A, p, r);
  93.  
  94.         quickSort(A, p, q-1);
  95.         quickSort(A, q+1, r);
  96.     }
  97. }
  98.  
  99.  
  100.  
  101. int main(){
  102.  
  103.     int N; cin >> N;
  104.  
  105.     vector < pair<char,int> > card, cardCopy;
  106.     char suit;
  107.     int number;
  108.     rep(i,0,N) {
  109.         cin >> suit >> number;
  110.  
  111.         card.push_back( make_pair(suit, number) );
  112.     }
  113.  
  114.     cardCopy = card;
  115.  
  116.  
  117.     //番号のみで安定ソート (second要素のnumberだけ比較するように比較関数オブジェクトを与える)
  118.     stable_sort(cardCopy.begin(), cardCopy.end(),
  119.          [](const pair<char,int> &x, const pair<char,int> &y) {return x.second < y.second;}   );
  120.  
  121.     //test display
  122.     rep(i,0,N) {
  123.         disP(cardCopy[i].first);
  124.         disP(cardCopy[i].second);
  125.         dout << endl;
  126.     }
  127.     dout << "------------\n";
  128.  
  129.  
  130.     //番号のみでクイックソート
  131.     quickSort(&card[0], 0, N-1);
  132.  
  133.  
  134.     //stable or unstable?
  135.     bool isStable = true;
  136.     rep(i,0,N) {
  137.         if( card[i].first != cardCopy[i].first ) {
  138.             isStable = false;
  139.             break;
  140.         }
  141.     }
  142.  
  143.     cout << (isStable ? "Stable" : "Not stable" ) << endl;
  144.  
  145.  
  146.     //display
  147.     rep(i,0,N) {
  148.         cout << card[i].first << " " << card[i].second << endl;
  149.     }
  150.  
  151.  
  152.  
  153.  
  154.  
  155. #ifdef OUTPUT2TEXTFILE
  156.     outputfile.close();
  157.     cout << "\"" << OutputFilePath << "\"" << endl;
  158. #endif
  159.  
  160.     return 0;
  161. }
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
20
H 1
D 1
S 1
C 1
H 2
D 2
S 2
C 2
H 3
D 3
S 3
C 3
H 4
D 4
S 4
C 4
H 5
D 5
S 5
C 5
stdout
copy 
  H   1 
  D   1 
  S   1 
  C   1 
  H   2 
  D   2 
  S   2 
  C   2 
  H   3 
  D   3 
  S   3 
  C   3 
  H   4 
  D   4 
  S   4 
  C   4 
  H   5 
  D   5 
  S   5 
  C   5 
------------
Stable
H 1
D 1
S 1
C 1
H 2
D 2
S 2
C 2
H 3
D 3
S 3
C 3
H 4
D 4
S 4
C 4
H 5
D 5
S 5
C 5
https://ideone.com/rtYaxX
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!