Repository navigation
Expand file tree
/
Copy pathB.cpp
More file actions
70 lines (65 loc) · 1.49 KB
/
Copy pathB.cpp
File metadata and controls
70 lines (65 loc) · 1.49 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <algorithm>
#include <iostream>
#include <random>
#include <vector>
const int c1 = 123;
const int c2 = 45;
const int cMod = 1e7 + 4321;
const int cRofl = 1488;
std::mt19937 rnd(cRofl);
void Partition(std::vector<int>& a, int pivot, std::vector<int>& l,
std::vector<int>& r, int& cnt) {
for (int i = 0; i < (int)a.size(); ++i) {
if (a[i] < pivot) {
l.push_back(a[i]);
} else if (a[i] == pivot) {
cnt++;
} else {
r.push_back(a[i]);
}
}
}
int QuickSelect(std::vector<int>& a, int k) {
size_t a_size = a.size();
if (a_size <= 5) {
sort(a.begin(), a.end());
return a[k - 1];
}
std::vector<int> mid_v((a_size + 4) / 5);
int mid_v_size = 0;
for (size_t i = 0; i < a_size; i += 5) {
sort(a.begin() + i, a.begin() + std::min(i + 5, a_size));
mid_v[mid_v_size] = a[std::min(i + 2, a_size - 1)];
mid_v_size++;
}
int pivot = QuickSelect(mid_v, mid_v_size / 2);
std::vector<int> l;
std::vector<int> r;
int cnt = 0;
Partition(a, pivot, l, r, cnt);
if (k <= (int)l.size()) {
return QuickSelect(l, k);
}
if (k <= (int)l.size() + cnt) {
return pivot;
}
return QuickSelect(r, k - cnt - (int)l.size());
}
int main() {
int n;
int k;
int a0;
int a1;
std::cin >> n >> k >> a0 >> a1;
std::vector<int> a(n);
a[0] = a0;
if (n == 1) {
std::cout << a0;
return 0;
}
a[1] = a1;
for (int i = 2; i < n; ++i) {
a[i] = (a[i - 1] * c1 + a[i - 2] * c2) % cMod;
}
std::cout << QuickSelect(a, k);
}