Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <ctime>
- using namespace std;
- int partition(vector<long> &arr, long l, long r);
- int qorder(vector<long> arr, long k);
- int main() {
- long n, k;
- ifstream input("input.txt");
- ofstream output("output.txt");
- input >> n >> k;
- k--;
- vector<long> arr(n);
- for (long i = 0; i < n; i++) {
- input >> arr[i];
- }
- output << qorder(arr, k);
- output.close();
- input.close();
- return 0;
- }
- int partition(vector<long> &arr, long l, long r) {
- if (l != r)
- swap(arr[l + rand() % (r - l)], arr[r]);
- long x = arr[r], i = l-1;
- for (int j = l; j <= r; j++) {
- if (arr[j] <= x)
- swap(arr[++i], arr[j]);
- }
- return i;
- }
- int qorder(vector<long> arr, long k) {
- long l = 0, r = arr.size() - 1;
- while(true) {
- long mid = partition(arr,l,r);
- if (mid < k)
- l = mid + 1;
- else if (mid > k)
- r = mid - 1;
- else
- return arr[k];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement