same, C++ (gcc) - rextester

same

#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;
#define mp make_pair
#define pb push_back
#define sz(v) (int)v.size()
#define pii pair<int, int>

// updated code: https://rextester.com/AEFLX76920
int median(vector<int> v){
    if(sz(v) < 3) return v[0];
    vector<int> medians;
    for(int j = 0; j < sz(v); j += 5){
        int cnt = 5;
        if(j+5 > sz(v)){
            sort(v.begin()+j, v.end());
            medians.pb(v[j + (sz(v) - j)/2]);
        }else{
            sort(v.begin()+j, v.begin()+j+5);
            medians.pb(v[j+2]);
        }
    }
    return median(medians);
}

int getKth(vector<int> v, int k){
    if(sz(v) == 1) return v[0];         //implicitly k = 0
    if(sz(v) == 2){
        if(v[0] > v[1]) swap(v[0], v[1]);
        return v[k-1];
    }
    int med = median(v);
    vector<int> lft, rgt;
    for(int j = 0; j < sz(v); j++)
        if(v[j] < med) lft.pb(v[j]);
        else rgt.pb(v[j]);
    if(k > sz(lft)+1) return getKth(rgt, k-sz(lft));
    if(k == sz(lft)+1) return med;
    return getKth(lft, k);
}

int main()
 {
	int t = 1;
	//cin >> t;
	while(t--){
	    int n = 10000001;
	    //cin >> n;
	    vector<int> v(n);
	    for(int j = 0; j < n; j++)
	        //cin >> v[j];
            v[j] = rand() % 100000001 + j + 1206;
	    int k;
	    cin >> k;
	    cout << getKth(v, k) << endl;
	    /*sort(v.begin(), v.end());
	    cout << v[k-1] << endl;*/
	}
	return 0;
}


run \| edit \| history \| help	0