Advertisement
Guest User

Untitled

a guest
May 22nd, 2019
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.05 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <ctime>
  5. using namespace std;
  6. int partition(vector<long> &arr, long l, long r);
  7. int qorder(vector<long> arr, long k);
  8.  
  9.  
  10. int main() {
  11.     long n, k;
  12.     ifstream input("input.txt");
  13.     ofstream output("output.txt");
  14.     input >> n >> k;
  15.     k--;
  16.     vector<long> arr(n);
  17.     for (long i = 0; i < n; i++) {
  18.         input >> arr[i];
  19.     }
  20.  
  21.     output << qorder(arr, k);
  22.  
  23.     output.close();
  24.     input.close();
  25.  
  26.     return 0;
  27. }
  28.  
  29. int partition(vector<long> &arr, long l, long r) {
  30.     if (l != r)
  31.         swap(arr[l + rand() % (r - l)], arr[r]);
  32.     long x = arr[r], i = l-1;
  33.     for (int j = l; j <= r; j++) {
  34.         if (arr[j] <= x)
  35.             swap(arr[++i], arr[j]);
  36.     }
  37.     return i;
  38. }
  39. int qorder(vector<long> arr, long k) {
  40.     long l = 0, r = arr.size() - 1;
  41.     while(true) {
  42.         long mid = partition(arr,l,r);
  43.         if (mid < k)
  44.             l = mid + 1;
  45.         else if (mid > k)
  46.             r = mid - 1;
  47.         else
  48.             return arr[k];
  49.     }
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement