Cod sursa(job #1533206)

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


using namespace std;


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

const int NMAX = 3000000;

int k; int n;

int v[NMAX];

int quick(int st, int dr) {

	if(st >= dr)
		return v[st];

	int left = st; int right = dr;
	int p = 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 v[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 << quick(1, n);

	//for(int i = 1; i <= n; ++i)
	//	fout << v[i] << " ";
	return 0;
}