fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. mt19937_64 rd(time(0));
  5. int rand(int L, int R){
  6.     return L + rd() % (R - L + 1);
  7. }
  8.  
  9. int n;
  10. vector<int> arr;
  11.  
  12. bool isSorted(vector<int>& arr, int length){
  13.     for(int i = 1; i < length; i++){
  14.         if(arr[i - 1] < arr[i]) return 0;
  15.     }
  16.  
  17.     return 1;
  18. }
  19.  
  20. vector<int> bitmask_sort(vector<int>& arr, int length){
  21.     if(length <= 1) return arr;
  22.     if(length == 2){
  23.         if(arr[0] < arr[1]) swap(arr[0], arr[1]);
  24.         return arr;
  25.     }
  26.  
  27.     const int numSegments = rand(2, 31);
  28.     const int range = (length - 1)/numSegments + 1;
  29.  
  30.     vector<int> newVector[numSegments];
  31.  
  32.     for(int i = 0; i < numSegments; i++){
  33.         for(int j = 0; j < range; j++){
  34.             if(i*range + j >= length) break;
  35.  
  36.             newVector[i].push_back(arr[i*range + j]);
  37.         }
  38.  
  39.         newVector[i] = bitmask_sort(newVector[i], newVector[i].size());
  40.     }
  41.  
  42.     for(int mask = 0; ; mask = rand(0, (1 << numSegments) - 1)){
  43.         if(__builtin_popcount(mask) <= 1) continue;
  44.         if(isSorted(arr, arr.size())) break;
  45.  
  46.         int cur_length = 0;
  47.         vector<int> get_bit;
  48.  
  49.         for(int i = 0; (mask >> i) > 0; i++){
  50.             if((mask >> i) & 1){
  51.                 get_bit.push_back(i);
  52.                 cur_length += newVector[i].size();
  53.             }
  54.         }
  55.  
  56.  
  57.  
  58.         int times[numSegments]; memset(times, 0, sizeof times);
  59.         vector<int> cur_vector;
  60.  
  61.         while(cur_vector.size() < cur_length){
  62.             int cur_index = 0;
  63.             int cur_value = (int) - 1e9;
  64.  
  65.             for(int i:get_bit){
  66.                 if(times[i] >= newVector[i].size()) continue;
  67.                 if(cur_value <= newVector[i][times[i]]){
  68.                     cur_index = i;
  69.                     cur_value = newVector[i][times[i]];
  70.                 }
  71.             }
  72.  
  73.             cur_vector.push_back(cur_value);
  74.             times[cur_index]++;
  75.         }
  76.  
  77.  
  78.  
  79.         int index = 0, countTime = 0;
  80.  
  81.         for(int i:get_bit){
  82.             while(index < newVector[i].size()){
  83.                 newVector[i][index] = cur_vector[countTime*range + index];
  84.                 arr[i*range + index] = cur_vector[countTime*range + index];
  85.                 index++;
  86.             }
  87.  
  88.             countTime++;
  89.             index = 0;
  90.         }
  91.     }
  92.  
  93.     return arr;
  94. }
  95.  
  96. int main(){
  97.     ios_base::sync_with_stdio(0);
  98.     cin.tie(0); cout.tie(0);
  99.  
  100.     cin >> n;
  101.     for(int i = 0; i < n; i++){
  102.         int value; cin >> value;
  103.         arr.push_back(value);
  104.     }
  105.  
  106.     while(!isSorted(arr, n)){
  107.         arr = bitmask_sort(arr, n);
  108.     }
  109.  
  110.     for(int i = 0; i < n; i++) cout << arr[i] << ' ';
  111.  
  112.     return 0;
  113. }
  114.  
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/KjtQqD
language:
C++14 (gcc 8.3)
created:
197 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!