Cod sursa(job #1253279)

Utilizator costyv87Vlad Costin costyv87 Data 1 noiembrie 2014 00:11:14
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
FILE *f,*g;
int v[3000010];
int n,k,i;
 
int partitie(int st, int dr)
{
    int  x=v[(rand()%(dr-st))+st];
    int j=dr+1,i=st-1;
 
    while (1)
    {
       do j--; while (v[j]>x);
       do i++; while (v[i]<x);
       if (i<j)
            swap(v[i],v[j]);
        else
            return j;
    }
}
 
int divide(int st, int dr,int k)
{
    if (st==dr) return v[st];
    int q;
    q=partitie(st,dr);
 
    if (k<=q)
        return (divide(st,q,k));
    else
        return (divide(q+1,dr,k));
}
 
 
 
 
int main()
{
    f=fopen("sdo.in","r");
    g=fopen("sdo.out","w");
 
    fscanf(f,"%d%d",&n,&k);
    for (i=1;i<=n;i++) fscanf(f,"%d",&v[i]);
 
    fprintf(g,"%d",divide(1,n,k));
 
 
    return 0;
}