Run Code
|
API
|
Code Wall
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
Kth smallest element
#include <bits/stdc++.h> using namespace std; int median(int l, int r, vector<int>& v){ if((r - l + 1) <= 5){ sort(v.begin()+l, v.begin()+r+1); int mid = (r - l)/2 + l; if(((r - l + 1)&1) == 0) return v[mid+1]; return v[mid]; } int len = r - l + 1; int ind = l; vector<int> m; for(int j = l; j <= r; j += 5){ int st = j, ed = (j+5-1 <= r)? (j + 5-1) : r; sort(v.begin()+st, v.begin()+ed+1); int x = (j+5-1 <= r)? j+2 : (j + (ed - st)/2) + ((len&1)? 1 : 0); swap(v[ind ++], v[x]); // m.push_back(v[x]); } return median(l, ind - 1, v); // return median(0, (int)m.size()-1, m); } int foo(int l, int r, vector<int>& v, int k){ // cout << l << " " << r << " " << k << endl; if(l == r) return v[l]; if(r -l + 1 == 2){ if(v[l] > v[r]) swap(v[l], v[r]); return v[l+k]; } int m = median(l, r, v); int i = l, j = r; while(i <= j){ while(v[i] <= m) i ++; while(v[j] > m) j --; if(i > j) break; swap(v[i], v[j]); i ++, j --; } int cnt_less_m = j - l + 1; // PERFORMS VERY BADLY IF THE ARRY CONTAINS DUPLICATES if(cnt_less_m >= k) return foo(l, j, v, k); return foo(i, r, v, k-cnt_less_m); } bool check(int x, const vector<int>& A, const int B){ int cnt = 0; for(auto i : A) if(i <= x) cnt ++; return (cnt >= B); } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n = 1e7; set<int> s; vector<int> v(n); // PERFORMS BADLY IF ARRAY CONTAINS MANY DUPLICATES // IT WILL NOT CONVERGE EVEN AND RUNS IN INFINITE RECURSION /* while(s.size() < n) s.insert(rand()); auto it = s.begin(); for(int j = 0; j < n; j++) v[j] = *(it ++); */ for(int j = 0; j < n; j++) v[j] = rand(); int k = 6e5; // sort(v.begin(), v.end()); cout << v[k] << endl; cout << foo(0, n-1, v, k) << endl; return 0; }
run
|
edit
|
history
|
help
0
maximum_frequent_sum
srednie
Defining Class Members
Sangharsh vhawale
11aa11
12
FInd rows with maximum no of 1's
lambda capture
cppPyGuessTheNum2
Havel Hakimi UVA-12786 Friendship Networks