Cod sursa(job #2183457)

Utilizator AndreiSorin26012001Cirpici Andrei Sorin AndreiSorin26012001 Data 23 martie 2018 10:31:32
Problema Statistici de ordine Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("data.in");
ofstream out("data.out");

int n, k, p, aux;
int arr[3000005];

int poz( int st, int dr )
{
    int d_st = 0, d_dr = -1;

    while( st != dr )
    {
        if( arr[st] > arr[dr] )
        {
            swap( arr[st], arr[dr] );
            aux = d_st;
            d_st = -d_dr;
            d_dr = -aux;
        }

        st += d_st;
        dr += d_dr;
    }

    return st;
}

int cauta( int st, int dr, int t )
{
    if( st < dr )
    {
        p = poz( st, dr );

        if( p > k )
            return cauta( st, p - 1, t );
        else if( p < k )
            return cauta( p + 1, dr, t - p );
        else
        {
            return p;
        }

    }
}

int main()
{
    in>>n>>k;
    for( int i = 1; i <= n; i++ )
        in>>arr[i];

    srand( time(0) );
    for( int i = n; i >= 2; i-- )
        swap( arr[i], arr[ 1 + rand()%(i-1) ] );

    out<<arr[ cauta( 1, n, k ) ];

    return 0;
}