Cod sursa(job #1105160)

Utilizator s1mpMihai Alexandru s1mp Data 11 februarie 2014 15:36:16
Problema Statistici de ordine Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.77 kb
#include<iostream>
#include<fstream>

#define Nmax 3000001

using namespace std;

long long M[Nmax];

long Position(long p, long u, long pivot) {
    int i=p, j=u;
	long X = M[pivot];
    while(i<j){
		if (M[i] == X) {
			swap(M[i],M[j]);
		}
		if (M[i] > X) {
			swap(M[i],M[j]);
			j--;
		} else {
			i ++;
		}
    }
    return i;
}

long long QuickSelect(long p, long u, long K) {
	long m;
	m = Position(p,u,u);
	if (m > K) {
		return QuickSelect(p,m-1,K);
	} else if (m < K) {
		return QuickSelect(m+1,u,K);
	} else {
		return M[m];
	}
}

int main() {
	ifstream f("sdo.in");
	ofstream g("sdo.out");
	long long N,K;
	f>>N;
	f>>K;
	for(int i = 0; i < N; i++) {
		f>>M[i];
	}
	g<<QuickSelect(0,N-1,K-1);
	f.close();
	g.close();
	return 0;
}