# !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;
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