Cod sursa(job #1149174)

Utilizator theodor.moroianuTheodor Moroianu theodor.moroianu Data 21 martie 2014 15:20:50
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include <iostream>
#include <fstream>
using namespace std;
int v[3000000];
int n,k,aux;
void schimb (int a,int b){
    aux=v[a];
    v[a]=v[b];
    v[b]=aux;
}
int pozitie (int st,int dr);
void med(int st,int dr){
    if (st>=dr)
        return;
    int p=pozitie(st,dr);
    if (k<p)
        med(st,p-1);
    else if (k>p)
        med(p+1,dr);
}
int pozitie(int st,int dr){
    int i=st,j=st;
    while (i<dr){
        if (v[i]<v[dr]){
            schimb (i,j);
            j++;
        }
        i++;
    }
    schimb(j,dr);
    return j;
}
int main()
{
    ifstream in ("sdo.in");
    ofstream out ("sdo.out");
    in>>n>>k;
    for (int i=1;i<=n;i++){
        in>>v[i];
    }
    int j;
    for (int i=n/2;i<n;i++){
        j=(long long)v[i]*i%n+1;
        schimb(i,j);
    }
    med(1,n);
    out<<v[k];
    return 0;
}