fork download
  1. #include <iostream>
  2. #include <cassert>
  3. #include <cstdio>
  4.  
  5. using namespace std;
  6. const int N = 1e7 + 5;
  7. int Len, a[N];
  8. int B[N], C[N], res[N];
  9. /**
  10.   C[]: temparary storage array
  11.   res[]: store result array,
  12.  */
  13. int cntPos, pos[N], cntNeg, neg[N];
  14.  
  15. void input() {
  16. assert(freopen("CountingSort.inp", "r", stdin)); /// read your own input
  17. cin >> Len;
  18. for (int i = 1; i <= Len; i ++) {
  19. cin >> a[i];
  20. if (a[i] < 0) {
  21. ++ cntNeg;
  22. neg[cntNeg] = a[i];
  23. } else {
  24. ++ cntPos;
  25. pos[cntPos] = a[i];
  26. }
  27. }
  28. }
  29. void cntSort(int A[], int n) {
  30. int K = -1;
  31. for (int i = 1; i <= n; i ++)
  32. K = max(K, A[i]);
  33. for (int i = 0; i <= K; i ++)
  34. C[i] = 0;
  35. for (int i = 1; i <= n; i ++)
  36. ++ C[A[i]];
  37. for (int i = 1; i <= K; i ++)
  38. C[i] += C[i - 1];
  39. for (int j = n; j >= 1; j --) {
  40. B[C[A[j]]] = A[j];
  41. -- C[A[j]];
  42. }
  43. }
  44. void cntNegSort(int A[], int n) { /// case negative array
  45. for (int i = 1; i <= n; i ++)
  46. A[i] = -A[i];
  47. cntSort(A, n);
  48. for (int i = 1; i <= cntNeg; i ++) {
  49. res[i] = -B[cntNeg - i + 1];
  50. }
  51. }
  52. void cntPosSort(int A[], int n) { /// case Positive array
  53. cntSort(A, n);
  54. for (int i = 1; i <= cntPos; i ++)
  55. res[i + cntNeg] = B[i];
  56. }
  57. void output(int A[], int n) {
  58. cout << n << endl;
  59. for (int i = 1; i <= n; i ++)
  60. cout << A[i] << " ";
  61. }
  62. int main() {
  63. input();
  64. if (cntNeg != 0)
  65. cntNegSort(neg, cntNeg);
  66. if (cntPos != 0)
  67. cntPosSort(pos, cntPos);
  68. output(res, Len);
  69. return 0;
  70. }
  71.  
Runtime error #stdin #stdout #stderr 0s 237760KB
stdin
Standard input is empty
stdout
Standard output is empty
stderr
prog: prog.cpp:16: void input(): Assertion `freopen("CountingSort.inp", "r", stdin)' failed.