Cod sursa(job #2692740)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 3 ianuarie 2021 16:49:56
Problema Statistici de ordine Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <stdio.h>
#include <stdlib.h>
int v[ 3000000 ];

void qsort( int v[], int begin, int end, int k ){
    int pivot = v[ begin + rand() % ( end - begin + 1 ) ];
    int b = begin, e = end;
    while( v[ b ] < pivot )
        ++b;
    while( v[ e ] > pivot )
        --e;
    while( b < e ){
        int cop = v[ b ];
        v[ b ] = v[ e ];
        v[ e ] = cop;
        do
            ++b;
        while( v[ b ] < pivot );
        do
            --e;
        while( v[ e ] > pivot );
    }
    if( begin < e && k < e )
        qsort( v, begin, e, k );
    else if( e + 1 < end )
        qsort( v, e + 1, end, k );
}

int main()
{
    int n, k;
    FILE *fin = fopen( "sdo.in", "r" );
    fscanf( fin, "%d %d", &n, &k );
    for( int i = 0; i < n; i++ )
        fscanf( fin, "%d", &v[ i ] );
    fclose( fin );
    qsort( v, 0, n - 1, k - 1 );
    FILE *fout = fopen( "sdo.out", "w" );
    fprintf( fout, "%d\n", v[ k - 1 ] );
    fclose( fout );
    return 0;
}