Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define Gene template< class
- #define Rics printer& operator,
- Gene c> struct rge{c b, e;};
- Gene c> rge<c> range(c i, c j){ return {i, j};}
- struct printer{
- ~printer(){cerr<<endl;}
- Gene c >Rics(c x){ cerr<<boolalpha<<x; return *this;}
- Rics(string x){cerr<<x;return *this;}
- Gene c, class d >Rics(pair<c, d> x){ return *this,"(",x.first,", ",x.second,")";}
- Gene ... d, Gene ...> class c >Rics(c<d...> x){ return *this, range(begin(x), end(x));}
- Gene c >Rics(rge<c> x){
- *this,"["; for(auto it = x.b; it != x.e; ++it)
- *this,(it==x.b?"":", "),*it; return *this,"]";}
- };
- #define debug() cerr<<"LINE "<<__LINE__<<" >> ", printer()
- #define dbg(x) "[",#x,": ",(x),"] "
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- int my_rand(int l, int r) {
- return uniform_int_distribution<int>(l, r) (rng);
- }
- // merges v[l...m], v[m+1...r]
- void Merge(vector<int> &v, int l, int m, int r) {
- int ptr_l = l, ptr_r = m+1;
- vector<int> merged;
- while(ptr_l <= m or ptr_r <= r) {
- if(ptr_l > m) {
- merged.push_back(v[ptr_r]);
- ptr_r++;
- }
- else if(ptr_r > r or v[ptr_r] > v[ptr_l]) {
- merged.push_back(v[ptr_l]);
- ptr_l++;
- }
- else {
- merged.push_back(v[ptr_r]);
- ptr_r++;
- }
- }
- for(int i = l, j = 0; i <= r; i++, j++) {
- v[i] = merged[j];
- }
- }
- void Sort(vector<int> &v) {
- int n = v.size();
- for(int cur_size = 1; cur_size < n; cur_size *= 2) {
- for(int left_start = 0; left_start < n; left_start += 2 * cur_size) {
- int mid = min(left_start + cur_size - 1, n - 1);
- if(mid == n-1) continue;
- int right_end = min(left_start + 2 * cur_size - 1, n - 1);
- Merge(v, left_start, mid, right_end);
- }
- }
- }
- int main() {
- // freopen("in.txt", "r", stdin);
- ios::sync_with_stdio(0);
- cin.tie(0);
- for(int itr = 1; itr <= 10000; itr++) {
- int n = my_rand(1, 100);
- vector<int> v(n);
- for(int i = 0; i < n; i++) {
- v[i] = my_rand(-100000, 100000);
- }
- vector<int> tmp_v = v;
- sort(tmp_v.begin(), tmp_v.end());
- Sort(v);
- assert(v == tmp_v);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement