Cod sursa(job #1492078)

Utilizator gabi.cristacheGabi Cristache gabi.cristache Data 27 septembrie 2015 02:05:06
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>

#define MaxN 3000005

using namespace std;

ifstream fin("sdo.in");
ofstream fout("sdo.out");

int v[MaxN], N;

void sdoswap(int x, int y) {
    int temp = v[x];
    v[x] = v[y];
    v[y] = temp;
}

int sdo(int left, int right) {


    int pivot = v[right];
    int k = left;


    for (int i = left; i < right; ++i) {
        if (v[i] <= pivot) {
            sdoswap(i, k);
            ++k;
        }
    }

    sdoswap(k, right);


    return k;
}

int main()
{
    int k, p;

    fin >> N >> k;

    int left = 0, right = N - 1;
    for (int i = 0; i < N; ++i)
        fin >> v[i];

    while (1) {
        p = sdo(left, right);
        if (p == k - 1) {
            break;
        } else if (p < k - 1){

            left = p + 1;
        } else {

            right = p - 1;
        }
    }

    fout << v[k - 1] << endl;

    return 0;
}