Cod sursa(job #2293058)

Utilizator Dragomiralexandru621@yahoo.comDragomir ionut alexandru [email protected] Data 30 noiembrie 2018 14:44:54
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("sdo.in") ;
ofstream g("sdo.out") ;
int a[3000002] , n , nr , i ,k ;


int cautare( int a[] , int st , int dr )
{  int s = st - 1 , d = dr + 1 ;

    int pivot = a[ ( st + dr ) / 2 ] ;
    while( 1 > 0 )
    {

        do{
            s ++ ;
        } while( a[s] < pivot ) ;
        do{
            d -- ;
        }while( a[d] > pivot ) ;

        if( s < d )
            swap( a[s] , a[d] ) ;
        else
            return d ;
    }
}

void parcurgere( int a[] , int st , int dr , int k )
{
    if( st == dr )
        return ;
    int x = cautare( a , st , dr ) ;
    int y = x - st + 1 ;
    if ( y >= k )
        parcurgere( a , st , x , k ) ;
    else
        parcurgere( a , x + 1 , dr , k - y ) ;
}


int main() {
f >> n >> k ;

for( int i = 1 ; i <= n ; i ++ )
        f >> a[i] ;

 parcurgere( a , 1 , n , k ) ;
 g << a[k] ;
 }