Cod sursa(job #1601412)

Utilizator bullseYeIacob Sergiu bullseYe Data 15 februarie 2016 21:50:20
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <fstream>
#define NMAX 3000010
using namespace std;

int n, A[NMAX], k;

void read();
inline int divide (int, int);
void qsort (int, int);
void result ();

int main(){
    read();
    qsort (0, n-1);
    result();
    return 0;
}

void read(){
    FILE*fin=fopen ("sdo.in", "r");
    //ifstream fin ("sdo.in");
    int i;
    fscanf(fin, "%d %d", &n, &k);
    //fin>>n>>k;
    for (i=0; i<n; ++i)
        //fin>>A[i];
        fscanf(fin, "%d", &A[i]);
    fclose(fin);
    return;
}

void result (){
    //FILE*fout=fopen ("sdo.out", "w");
    ofstream fout ("sdo.out");
    //fprintf(fout, "%d\n", A[k-1]);
    //fclose(fout);
    fout<<A[k-1]<<"\n";
    fout.close();
    return;
}

inline int divide (int st, int dr)
{
    int pivot=A[st];
    while (st<dr){//cat timp mai am macar 2 elemente
        while (st<dr && A[dr]>=pivot) --dr;
        A[st]=A[dr];
        while (st<dr && A[st]<=pivot) ++st;
        A[dr]=A[st];
    }
    A[st]=pivot;
    return st;
}

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

    int poz;
    poz=divide (st, dr);
    if (poz==k-1) return;

    if (poz>=k-1)//sortez in stanga
        qsort (st, poz-1);
        else
        qsort (poz+1, dr);
}