Advertisement
Korotkodul

Kst_OK

Oct 2nd, 2023 (edited)
623
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include <cmath>
  2. #include <iostream>
  3. #include <vector>
  4.  
  5. using std::cin;
  6. using std::cout;
  7. using std::max;
  8. using std::min;
  9. using std::string;
  10. using std::vector;
  11.  
  12. bool sh = false;
  13.  
  14. void Swap(int* p1, int* p2) {
  15.   int tt = *p1;
  16.   *p1 = *p2;
  17.   *p2 = tt;
  18. }
  19.  
  20. vector<int> ar;
  21.  
  22. void Partition(int low, int high, int xnum) {
  23.   // делим на < и >=
  24.   int lft = low - 1;
  25.   for (int id = low; id <= high; ++id) {
  26.     if (ar[id] < xnum) {
  27.       int* p1 = &ar[id];
  28.       int* p2 = &ar[lft + 1];
  29.       Swap(p1, p2);
  30.       lft++;
  31.     }
  32.   }
  33.   // делим на = и >
  34.   for (int id = lft + 1; id <= high; ++id) {
  35.     if (ar[id] == xnum) {
  36.       int* p1 = &ar[id];
  37.       int* p2 = &ar[lft + 1];
  38.       Swap(p1, p2);
  39.       lft++;
  40.     }
  41.   }
  42. }
  43.  
  44. int Kst(int low, int high, int knum) {
  45.   if (low == high) {
  46.     return ar[low];
  47.   }
  48.   int piv = ar[low];
  49.   Partition(low, high, piv);
  50.   if (sh) {
  51.     cout << "low high" << low << ' ' << high << "\n";
  52.     cout << "piv = " << piv << "\n";
  53.     cout << "Partition\n";
  54.     for (int el : ar) {
  55.       cout << el << ' ';
  56.     }
  57.     cout << "\n\n";
  58.   }
  59.   int lft = low;
  60.   while (ar[lft] != piv) {
  61.     lft++;
  62.   }
  63.   int rgt = high;
  64.   while (ar[rgt] != piv) {
  65.     rgt--;
  66.   }
  67.   // lft - самый левый piv
  68.   // rgt - самый правый piv
  69.   if (sh) {
  70.     cout << "knum = " << knum << "\n";
  71.     cout << "lft rgt " << lft << ' ' << rgt << "\n";
  72.   }
  73.   if (knum < lft - low) {
  74.     if (sh) {
  75.       cout << "A\n";
  76.     }
  77.     return Kst(low, lft - 1, knum);
  78.   }
  79.   if (lft - low <= knum && knum <= rgt - low) {
  80.     if (sh) {
  81.       cout << "B\n";
  82.     }
  83.     return piv;
  84.   }
  85.   if (knum > rgt - low) {
  86.     if (sh) {
  87.       cout << "C\n";
  88.     }
  89.     return Kst(rgt + 1, high, knum - (rgt - low + 1));
  90.   }
  91.   return 0;
  92. }
  93.  
  94. int main() {
  95.   std::ios::sync_with_stdio(false);
  96.   std::cin.tie(0);
  97.   std::cout.tie(0);
  98.   /*int len;
  99.   int knum;
  100.   cin >> len;
  101.   ar.resize(len);
  102.   for (int& el : ar) {
  103.     cin >> el;
  104.   }
  105.   cin >> knum;
  106.   knum--;
  107.   cout << Kst(0, len - 1, knum);*/
  108.   int len;
  109.   int knum;
  110.   cin >> len >> knum;
  111.   ar.resize(len);
  112.   cin >> ar[0] >> ar[1];
  113.   const int k10 = 10;
  114.   const int k7 = 7;
  115.   const int k4321 = 4321;
  116.   const int k123 = 123;
  117.   const int k45 = 45;
  118.   int mod = pow(k10, k7) + k4321;
  119.   for (int id = 2; id < len; ++id) {
  120.     ar[id] = (ar[id - 1] * k123 + ar[id - 2] * k45) % mod;
  121.   }
  122.   int res = Kst(0, len - 1, knum - 1);
  123.   cout << res;
  124. }
  125. /*
  126. 16
  127. 7 10 3 4 5 11 2 1 2 3 1 5 4 6 7 1
  128. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  129. 1 1 1 2 2 3 3 4 4 5 5 6 7 7 10 11
  130.  
  131. 17
  132. 2 2 0 2 1 2 0 2 1 0 2 1 2 2 0 0 2
  133.  
  134. 16
  135. 7 10 3 4 5 11 2 1 2 3 1 5 4 6 7 1
  136. >= 8 - mist
  137. */
  138.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement