Advertisement
IISergeyII

Untitled

Nov 1st, 2019
156
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8.  
  9. vector<int> v;
  10. int k;
  11.  
  12.  
  13. int partition(int l, int r) {
  14.     r--;
  15.     int p = v[(l + r) / 2];
  16.     int i = l;
  17.     int j = r;
  18.     while (i <= j) {
  19.         while (v[i] < p)
  20.             i++;
  21.         while (v[j] > p)
  22.             j--;
  23.         if (i >= j)
  24.             break;
  25.         swap(v[i++], v[j--]);
  26.     }
  27.  
  28.     return j;
  29. }
  30.  
  31. int find_st(int k) {
  32.     int left, right;
  33.     left = 0;
  34.     right = v.size();
  35.  
  36.     while (true) {
  37.         int mid = partition(left, right);
  38.  
  39.         if (mid == k) {
  40.             return v[mid];
  41.         }
  42.         else if (k < mid) {
  43.             right = mid;
  44.         }
  45.         else {
  46.             left = mid + 1;
  47.         }
  48.     }
  49.  
  50. }
  51.  
  52.  
  53. int main() {
  54.  
  55.     //---------------------------------------------
  56.     freopen("kth.in", "r", stdin);
  57.     freopen("kth.out", "w", stdout);
  58.     //--------------------------------------------- /*/
  59.  
  60.     int n, A, B, C, a1, a2;
  61.     cin >> n >> k >> A >> B >> C >> a1 >> a2;
  62.  
  63.     v.push_back(a1);
  64.     v.push_back(a2);
  65.     for (int i = 2; i <= n; ++i) {
  66.         v.push_back(A*v[i - 2] + B*v[i - 1] + C);
  67.     }
  68.  
  69.  
  70.     k--;
  71.     cout << find_st(k);
  72.  
  73. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement