Cod sursa(job #1238661)

Utilizator MarronMarron Marron Data 7 octombrie 2014 14:27:27
Problema Statistici de ordine Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
#define MAXN 3000000

ifstream f("sdo.in");
ofstream g("sdo.out");

int n, k;
vector<int> v;

void my_nth_element(int k)
{
    int st = 0, dr = n - 1;
    while (st <= dr)
    {
        int i = st, j = dr, dir = 1;
        while (i != j)
        {
            if (dir == 1) {
                if (v[i] <= v[j]) {
                    i++;
                } else {
                    swap(v[i], v[j]);
                    j--;
                    dir = -1;
                }
            } else {
                if (v[i] <= v[j]) {
                    j--;
                } else {
                    swap(v[i], v[j]);
                    i++;
                    dir = 1;
                }
            }
        }
        if (i == k) {
            break;
        }
        if (i < k) {
            st = i + 1;
        } else {
            dr = i - 1;
        }
    }

}

int main()
{
    f >> n >> k;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        f >> v[i];
    }

    my_nth_element(k - 1);

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

    f.close();
    g.close();
    return 0;
}