Cod sursa(job #1715890)

Utilizator timicsIoana Tamas timics Data 11 iunie 2016 16:40:23
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#include<time.h>
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define MOD 1000000007
using namespace std;
int N,k,a[3000100];

void quicky(int l, int r) {
    if(l >= r) return;
    int piv = l + rand()%(r - l + 1);
    int st = l, dr = r;
    while(true) {
        while(a[st] < a[piv]) ++st;
        while(a[dr] > a[piv]) --dr;
        if(st < dr) swap(a[st],a[dr]);
        else break;
    }
    if(dr >= k) {
        quicky(l,dr);
    } else {
        quicky(dr+1,r);
    }
}

int main() {
	freopen("sdo.in","r",stdin);
	freopen("sdo.out","w",stdout);
	//freopen("input.in","r",stdin);
    srand(time(0));
	scanf("%d%d",&N,&k);
    for(int i=1;i<=N;++i) {
        scanf("%d",&a[i]);
    }
    quicky(1,N);
    cout<<a[k];
    return 0;
}