Cod sursa(job #736542)

Utilizator gener.omerGener Omer gener.omer Data 18 aprilie 2012 21:55:45
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define NMAX 3000000
int A[NMAX], N, K;

int find(int K){
    int left = 0, right = N - 1, mid;
    while(left <= right){
        mid = left + (right - left) / 2;
        swap(A[mid], A[right]);
		
		int pos = left;
        for(int i = left; i < right; ++i){
            if(A[i] < A[right])
                swap(A[i], A[pos++]);
        }
        
		swap(A[right], A[pos]);
        mid = pos;
		
		if((mid - left + 1) < K)
            left = mid + 1, K = K - left - 1;
        else
            right = mid - 1;	
    }
	return -1;
}

int main(){
    ifstream in("sdo.in");
	ofstream out("sdo.out");
    in >> N >> K;
    for(int i = 0; i < N; ++i)
        in >> A[i];
	find(K);
    out << A[K-1] << endl;
	return 0;
}