konchin_shih

radix sort

Feb 25th, 2021 (edited)
106
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.72 KB | None | 0 0
  1. #include".\template\headers.hpp"
  2.  
  3. // #define MULTI_TASKCASE
  4. using namespace abb;
  5. using namespace output;
  6. using namespace rit;
  7. using namespace wit;
  8.  
  9. inline void init() {
  10.  
  11. }
  12.  
  13. constexpr int n = 9e5;
  14. constexpr int maxexp = 9;
  15.  
  16. void radix_sort(A<int, n>& arr, int exp) {
  17.     const int base = 1 << exp;
  18.     static A < A<int, n>, (1 << maxexp) > bucket;
  19.     static A < int, (1 << maxexp) > cnt;
  20.     auto find_maxt = [&arr, exp]() {
  21.         int maxn = *max_element(arr.begin(), arr.end()), cnt = 0;
  22.         while (maxn) cnt++, maxn >>= exp;
  23.         return cnt;
  24.     };
  25.     auto maxt = find_maxt();
  26.     for (int k = 0; k < maxt; k++) {
  27.         fill(cnt.begin(), cnt.end(), 0);
  28.         for (const auto& i : arr) {
  29.             int id = (i >> (k * exp)) & (base - 1);
  30.             bucket[id][cnt[id]++] = i;
  31.         }
  32.         auto ptr = arr.begin();
  33.         for (int i = 0; i < base; i++)
  34.             for (int j = 0; j < cnt[i]; j++)
  35.                 *ptr++ = bucket[i][j];
  36.     }
  37. }
  38.  
  39. inline void solve() {
  40.     static A<int, n> v;
  41.     A<A<double, 20>, maxexp> arr;
  42.     for (int j = 0; j != maxexp; j++) {
  43.         fstream filein("in.txt", ios::in);
  44.         cin.rdbuf(filein.rdbuf());
  45.         for (auto& k : arr[j]) {
  46.             cout << "poop" << ' ';
  47.             for (auto& i : v)
  48.                 cin >> i;
  49.             clock_t before = clock();
  50.             radix_sort(v, j + 1);
  51.             clock_t after = clock();
  52.             k = double(after - before) / CLOCKS_PER_SEC * 1000;
  53.         }
  54.         filein.close();
  55.         cout << endl << flush;
  56.     }
  57.     fstream fileout("out.txt", ios::out);
  58.     cout.rdbuf(fileout.rdbuf());
  59.     for (int i = 0; i != 20; i++) {
  60.         for (int j = 0; j < maxexp - 1; j++)
  61.             cout << arr[j][i] << '\t';
  62.         cout << arr[maxexp - 1][i] << endl;
  63.     }
  64.     fileout.close();
  65. }
  66.  
  67. main() {
  68.     ios::sync_with_stdio(false);
  69.     init();
  70.     int t = 1;
  71. #ifdef MULTI_TASKCASE
  72.     cin >> t; cin.ignore();
  73. #endif
  74.     while (t--) solve();
  75.     return 0;
  76. }
Add Comment
Please, Sign In to add comment