Cod sursa(job #1533216)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 22 noiembrie 2015 11:54:22
Problema Statistici de ordine Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>


using namespace std;


ifstream fin("sdo.in");
ofstream fout("sdo.out");

const int NMAX = 3000002;

int k; int n;

int v[NMAX];

int quick(int st, int dr) {

	if(st >= dr)
		return st;

	int left = st; int right = dr;
	int p = dr ;//st + (rand() % (dr - st + 1));

	//swap(v[p], v[dr]);
	//p = dr;

	while(st <= dr) {

		while(st <= dr && v[dr] >= v[p]) dr--;
		
		while(st <= dr && v[st] <= v[p]) st++;

		if(st <= dr)
			swap(v[st], v[dr]);


	}

	swap(v[st], v[p]);

	if(k == st)
		return st;

	if(left < st - 1 && k <= st - 1)
		return quick(left, st - 1);
	if(right > st + 1 && k >= st + 1)
		return quick(st + 1, right);

}


int main() {

	srand(time(NULL));

	fin >> n >> k;
	for(int i = 1 ; i <= n ; ++i)
		fin >> v[i];

	fout << v[quick(1, n)];

	return 0;
}