Cod sursa(job #736557)

Utilizator gener.omerGener Omer gener.omer Data 18 aprilie 2012 22:35:14
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

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

void 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;
        
		int q = (mid - left + 1);

		if(q == K)
			return;
		if(q > K)
            right = mid-1;
        else
            left = mid+1, K -= (q);
    }
}

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;
}