Cod sursa(job #1410128)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 30 martie 2015 21:12:18
Problema Statistici de ordine Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <cstdio>
#include <ctime>
#include <cstdlib>
#define nmax 3000005

using namespace std;

FILE *fi, *fo;

int n, k;
int A[nmax];

int qs(int st, int dr)
{
    
    int i = st;
    int j = dr;
    int pivot = A[i + rand() % (j - i + 1)];
    
    while (1)
    {
        
        for (; A[i] < pivot;) i++;
        for (; A[j] > pivot;) j--;
        
        if (i <= j)
            swap(A[i++], A[j--]);
        else
            return j;
        
    }
    
    return 0;
}

void solve(int st, int dr, int k)
{
    if (st == dr)
        return;
    
    int pos = qs(st, dr);
    int len = pos - st + 1;
    
    if (len >= k)
        solve(st, pos, k);
    else
        solve(pos+1, dr, k-len);
    
}

int main()
{
    
    fi = fopen("sdo.in", "r");
    fo = fopen("sdo.out", "w");
    
    srand(time(0));
    
    fscanf(fi, "%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        fscanf(fi, "%d", &A[i]);
    
    solve(1, n, k);
    
    fprintf(fo, "%d", A[k]);
    
    fclose(fi);
    fclose(fo);
    
    return 0;
}