Cod sursa(job #1721988)

Utilizator elena.marinicaMarinica Elena-Georgiana elena.marinica Data 26 iunie 2016 22:59:18
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <bits/stdc++.h>
#include <fstream>

#define NMAX 3000004

using namespace std;

int v[NMAX];
int N;

void quick_sort(int v[], int lower, int upper, int k) {
	
	srand(time(NULL));
	
	if (lower < upper) {
		
		int pos = rand() % ((upper - lower) + lower);
		int piv = v[pos];
		
		std::swap(v[pos], v[upper]);
		
		int p = lower;
		
		for (int i = lower; i < upper; i++) {
			
			if(v[i] <= piv) {
				std::swap(v[i], v[p]);
				p++;
			}
		}
		
		std::swap(v[upper], v[p]);
		
		if (k < pos) {
			quick_sort(v, lower, p - 1, k);
		}
		else {
			quick_sort(v, p + 1, upper, k);
		}
	}
}

int main() {
	
	ifstream fin("sdo.in");
	ofstream fout("sdo.out");
	
	int k, x;
	
	fin >> N >> k;
	
	for (int i = 1; i <= N; i++) {
		fin >> x;
		v[i] = x;
	}
	
	quick_sort(v, 1, N, k);
	
	fout << v[k];
}