Cod sursa(job #1513275)

Utilizator ThomasFMI Suditu Thomas Thomas Data 29 octombrie 2015 11:30:20
Problema Statistici de ordine Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <cstdlib>
using namespace std;

#define NMax 3000005

ifstream f("sdo.in");
ofstream g("sdo.out");

int n,k;
int v[NMax];

void solve(int st, int dr)
{
    if(st >= dr) return;

    int poz = rand() % (dr-st+1) + st;
    int val = v[poz];
    int nr = 0;
    for(int i=st;i<=dr;++i) if(v[i] <= val) {++nr, swap(v[st+nr-1], v[i]);}
    for(int i=st;i<=dr;++i) if(v[i] == val) {swap(v[i], v[st+nr-1]); break;}
    if(nr >= k) solve(st, st+nr-2);
    else solve(st+nr, dr);
}

int main()
{
    f>>n>>k;
    for(int i=1;i<=n;i++) f>>v[i];

    srand(74595);
    solve(1,n);
    g<<v[k]<<"\n";

    f.close();
    g.close();
    return 0;
}