SHARE
TWEET

Untitled

a guest Oct 17th, 2019 100 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using std::cin;
  4. using std::cout;
  5. using std::endl;
  6.  
  7. void swap(int &a, int &b) {
  8.     if (a == b) return;
  9.  
  10.     a = a ^  b;
  11.     b = a ^ b;
  12.     a = a ^ b;
  13.  
  14. }
  15. int lomutoPartition(int *a, int l, int r) {
  16.     int mid = l + (r - l) / 2;
  17.     if (a[mid] > a[r]) {
  18.         swap(a[mid], a[r]);
  19.     }
  20.     if (a[l] > a[r] ) {
  21.         swap(a[r],a[l]);
  22.     }
  23.     if (a[mid] < a[l]) {
  24.         swap(a[mid],a[l]);
  25.     }
  26.    int pivot = a[l];
  27.    int i = r;
  28.    for (int j = r; j > l; j--) {
  29.        if (a[j] >= pivot) {
  30.            swap(a[i],a[j]);
  31.            i--;
  32.        }
  33.    }
  34.    swap(a[i],a[l]);
  35.    return i;
  36. }
  37. int lomutoPartition2(int *a, int l, int r) {
  38.     int mid = l + (r - l) / 2;
  39.     if (a[mid] > a[l]) {
  40.         swap(a[mid], a[l]);
  41.     }
  42.     if (a[l] < a[r] ) {
  43.         swap(a[r],a[l]);
  44.     }
  45.     if (a[mid] < a[r]) {
  46.         swap(a[mid],a[r]);
  47.     }
  48.     int pivot = a[r];
  49.     int i = l;
  50.     for (int j = l; j < r; j++) {
  51.         if (a[j] <= pivot) {
  52.             swap(a[i],a[j]);
  53.             i++;
  54.         }
  55.     }
  56.     swap(a[i],a[r]);
  57.     return i;
  58. }
  59. int kStat(int *a, int l, int r,int k){
  60.     while(true) {
  61.             int p = lomutoPartition(a, l, r);
  62.             if (k == p)
  63.                 return a[k];
  64.             else if (k > p) {
  65.                 l = p + 1;
  66.             } else {
  67.                 r = p - 1;
  68.             }
  69.     }
  70. }
  71. void qsort(int *a, int l, int r) {
  72.     if (l < r) {
  73.         int p =lomutoPartition(a,l,r);
  74.         qsort(a, l, p-1);
  75.         qsort(a, p+1, r);
  76.     }
  77. }
  78. int main() {
  79.     std::ios_base::sync_with_stdio(0);
  80.     cin.tie(0);
  81.     int n, k;
  82.     cin >> n >> k;
  83.  
  84.     int *a = new int[n];
  85.     bool f = true;
  86.     cin>>a[0];
  87.     for (int i = 1; i < n; i++) {
  88.         if (a[i-1] > a[i])
  89.             f = false;
  90.         cin >> a[i];
  91.     }
  92.     if (!f)
  93.       cout<<kStat(a,0,n-1,k);
  94.     else cout<<a[k];
  95.    // qsort(a, 0, n - 1);
  96.    // for (int i = 0; i < k; i++)
  97.    //     cout<<a[i]<<" ";
  98.     delete []a;
  99.     return 0;
  100. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top