SHARE
TWEET

Untitled

a guest Oct 10th, 2019 81 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <fstream>
  2.  
  3. using namespace std;
  4.  
  5. int key(int arr[], int l, int r) {
  6.     int n = r - l + 1;
  7.     int pivot = rand() % n;
  8.     swap(arr[l + pivot], arr[r]);
  9.     int v = arr[r], i = l;
  10.     for (int j = l; j < r; j++)
  11.     {
  12.         if (arr[j] <= v)
  13.         {
  14.             swap(arr[i], arr[j]);
  15.             i++;
  16.         }
  17.     }
  18.     swap(arr[i], arr[r]);
  19.     return i;
  20. }
  21.  
  22. int stat(int arr[], int k, int n) {
  23.     int left = 0, right = n;
  24.     while (true) {
  25.         int mid = key(arr, left, right);
  26.  
  27.         if (mid == k) {
  28.             return arr[mid];
  29.         }
  30.         else if (k < mid) {
  31.             right = mid;
  32.         }
  33.         else {
  34.             left = mid + 1;
  35.         }
  36.     }
  37. }
  38.  
  39. int main() {
  40.     ifstream cin("kth.in");
  41.     ofstream cout("kth.out");
  42.     int n, k;
  43.     cin >> n >> k;
  44.     int A, B, C;
  45.     cin >> A >> B >> C;
  46.     int arr[n];
  47.     cin >> arr[0] >> arr [1];
  48.     for (int i = 2; i < n; i++) {
  49.         arr[i] = A * arr[i-2] + B * arr[i-1] + C;
  50.     }
  51.     cout << stat(arr, k - 1, n);
  52.     return 0;
  53. }
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
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top