peltorator

!Kirk-patrick sort (works only for int32 why??)

Apr 12th, 2019 (edited)
152
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifdef ONPC
  2.     # define _GLIBCXX_DEBUG
  3.     #define deb(a) cerr << "========" << #a << " = " << a << endl;
  4. #else
  5.     #define deb(a)
  6. #endif
  7. #define sz(a) (int)(a).size()
  8.  
  9.  
  10. #include <bits/stdc++.h>
  11.  
  12. using namespace std;
  13. //mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
  14. mt19937 rnd(time(0));
  15.  
  16. typedef long long ll;
  17.  
  18. template<typename T>
  19. vector<T> count_sort(vector<T> &x)
  20. {
  21.     int pos = max_element(x.begin(), x.end()) - x.begin();
  22.     T mx = x[pos];
  23.     vector<int> cnt(mx + 1, 0);
  24.     for (T it : x)
  25.         cnt[it]++;
  26.     vector<T> ans;
  27.     for (int i = 0; i <= mx; i++)
  28.         for (int j = 0; j < cnt[i]; j++)
  29.             ans.push_back(i);
  30.     return ans;
  31. }
  32.  
  33. template<typename T>
  34. vector<T> my_sort(int k, vector<T> &x)
  35. {
  36.     T one = 1;
  37.     int n = sz(x);
  38.     if (n <= 1)
  39.         return x;
  40.     if (k <= 1 || n >= (one << (1 << k)))
  41.         return count_sort(x);
  42.     vector<T> a(n), b(n), as, result;
  43.     unordered_map<T, vector<T> > q;
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         b[i] = (x[i] & ((one << (one << (k - 1))) - 1));
  47.         a[i] = (x[i] >> (one << (k - 1)));
  48.         q[a[i]].push_back(b[i]);
  49.     }
  50.     for (auto &p : q)
  51.         as.push_back(p.first);
  52.     as = my_sort(k - 1, as);
  53.     for (T val : as)
  54.     {
  55.         vector<T> &bs = q[val];
  56.         int i = max_element(bs.begin(), bs.end()) - bs.begin();
  57.         T mx = bs[i];
  58.         swap(bs[i], bs.back());
  59.         bs.pop_back();
  60.         bs = my_sort(k - 1, bs);
  61.         bs.push_back(mx);
  62.         for (T j : bs)
  63.             result.push_back((val << (one << (k - 1))) | j);
  64.     }
  65.     return result;
  66. }
  67.  
  68. int gen()
  69. {
  70.     return abs((int)rnd());
  71. }
  72.  
  73. const ll INF = 1e9 + 7;
  74.  
  75. int solve()
  76. {
  77.     int n;
  78.     if (!(cin >> n))
  79.         return 1;
  80.    /* while (true)
  81.     {
  82.         n = gen() % 100 + 1;*/
  83.         vector<ll> v(n);
  84.         for (ll &i : v)
  85.             cin >> i, i += INF;
  86.         vector<ll> u = my_sort(5, v);
  87.         //sort(v.begin(), v.end());
  88.         /*if (v != u)
  89.         {
  90.             cout << "mem\n";
  91.             return 1;
  92.         }*/
  93.         for (ll i : u)
  94.             cout << i - INF << ' ';
  95.         cout << '\n';
  96.     //}
  97.     return 1;
  98. }
  99. int32_t main()
  100. {
  101.     ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  102.     int TET = 1e9;
  103.     //cin >> TET;
  104.     while (TET--)
  105.     {
  106.         if (solve())
  107.             break;
  108.         #ifdef ONPC
  109.             cout << "\n__________________________" << endl;
  110.         #endif
  111.     }
  112.     #ifdef ONPC
  113.         cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
  114.     #endif
  115.     return 0;
  116. }
RAW Paste Data