Cod sursa(job #612984)

Utilizator cristian9Cristian Zloteanu cristian9 Data 14 septembrie 2011 09:50:44
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.68 kb
#include<stdio.h>
#include<ctime>
#include <cstdio>
#include<iostream>
using namespace std;

int v[3000001];
int partitie(int st, int dr){
	int poz, i;
	poz=st+rand()%(dr-st+1);
	swap(v[dr], v[poz]);
	for(i=poz=st; i<dr; i++)
		if(v[i]<v[dr])
			swap(v[i], v[poz++]);
	swap(v[poz],v[dr]);
	return poz;
} 

int bin(int st, int dr, int k){
	int r;
	while((r=partitie(st, dr))!=k)
		if(k<r)
			dr=r-1;
		else
			st=r+1;
	return v[k];
}

int main(){
	freopen ("sdo.in", "r", stdin);
	freopen ("sdo.out", "w", stdout);
	
	int n, k, i;
	scanf("%d %d ", &n, &k);
	for(i=1; i<=n; i++)
		scanf("%d ", &v[i]);
	printf("");
	printf("%d ", bin(1, n, k));
	
	return 0;
}