Cod sursa(job #381474)

Utilizator ConsstantinTabacu Raul Consstantin Data 10 ianuarie 2010 18:42:19
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include <fstream>
#include <ctime>
using namespace std;
ifstream fin ("sdo.in");
ofstream fout("sdo.out");
 
int n,k;
int v[3000001];
 
void swap(int &x, int &y){
    int aux = x;
    x = y;
    y = aux;
};
 
int sdo(int k, int ex1,int ex2){
    int poz = ex1 + rand()%(ex2-ex1 + 1);
    int x = v[poz];
    swap(v[poz], v[ex1]);
    int i = ex1, j = ex2;
    while (i < j){
        for (; v[i] <= x && i < j; ++i);
        for (; v[j] > x && i <= j; --j);
        if (i < j) swap(v[i], v[j]);
    };
    v[ex1] = v[j];
    v[j] = x;
    if (j == k)
        return x;
    if (j < k)
        return sdo(k, j+1, ex2);
    return sdo(k, ex1, j-1);
 
};
 
int main(){
    srand(time(NULL));
    fin>>n>>k;
    for (int i = 1; i <= n ; i++)
        fin>>v[i];
    fout<<sdo(k, 1,n);
 
};