Cod sursa(job #2763643)

Utilizator ViAlexVisan Alexandru ViAlex Data 15 iulie 2021 17:40:07
Problema Statistici de ordine Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#include<map>
#include<algorithm>
#include<set>
#include<deque>
#include<queue>
using namespace std;
ifstream in("sdo.in");
ofstream out("sdo.out");

const int mx=3e6+10;

int a[mx],n,k;

int part(int*v,int l,int r){
	int pivot=v[r],cur=l;

	for(int i=l;i<r;i++){
		if(v[i]<pivot){
			swap(v[i],v[cur]);
			cur++;
		}
	}
	swap(v[r],v[cur]);
	return cur;
}

int nth(int*v,int k,int l,int r){

	if(l==r){
		return v[l];
	}
	else{
		int pivot=part(v,l,r);
		int count=pivot-l;

		if(k<=count){
			return nth(v,k,l,pivot-1);
		}
		else return nth(v,k-count,pivot,r);
	}
}


void read(){
	in>>n>>k;
	for(int i=0;i<n;i++){
		in>>a[i];
	}
}

void solve(){
	out<<nth(a,k,0,n-1);
}


int main(){
	read();
	solve();
	return 0;
}