Cod sursa(job #1207876)

Utilizator Cristian1997Vintur Cristian Cristian1997 Data 14 iulie 2014 10:48:56
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
using namespace std;
#include <fstream>
#include <ctime>
#include <cstdlib>
ifstream fin("sdo.in");
ofstream fout("sdo.out");
const int Nmax = 3000000;

int v[Nmax];

int divide(int, int) ;

int main()
{
    srand(time(NULL));
    int i, n, k, gata = 0, m, st, dr;
    fin >> n >> k;
    for(i = 0; i < n; ++i) fin >> v[i];
    st = 0; dr = n-1;
    while(!gata)
    {
        m = divide(st, dr);
        if(m == k - 1) gata = 1;
        else if(m > k - 1) dr = m - 1;
        else st = m + 1;
    }
    fout << v[k - 1] << '\n';
    return 0;
}


int divide(int st, int dr)
{
    //int x = v[ rand() % (dr - st + 1) + st ];
    int x = v[st];
    while(st < dr)
    {
        while(st < dr && v[dr] >= x) --dr;
        v[st] = v[dr];
        while(st < dr && v[st] <= x) ++st;
        v[dr] = v[st];
    }
    v[st] = x;
    return st;
}