Cod sursa(job #1715912)

Utilizator timicsIoana Tamas timics Data 11 iunie 2016 17:00:30
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include<stdio.h>
#include<bitset>
#include<algorithm>
#include<iostream>
#include<vector>
#include<time.h>
#include<fstream>
#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 = a[(l+r)/2];
    //int piv = a[l + rand()%(r - l + 1)];
    int st = l, dr = r;
    while(true) {
        while(a[st] < piv) ++st;
        while(a[dr] > 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() {
    ifstream fin("sdo.in");
    ofstream fout("sdo.out");
    srand(time(0));
    fin>>N>>k;
    for(int i=1;i<=N;++i) {
        fin>>a[i];
    }
    quicky(1,N);
    fout<<a[k];
    return 0;
}