# Kst_OK

Oct 2nd, 2023 (edited)
730
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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.