Cod sursa(job #2321978)

Utilizator mariusgrafuMarius Grafu mariusgrafu Data 16 ianuarie 2019 21:40:58
Problema Statistici de ordine Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

int sdo(vector<int> v, int k) {

    int left = 0, right = v.size() - 1;
    int val = v[k];

    vector<int> L;
    vector<int> R;

    for(int i = left; i <= right; ++i) {
        if(i == k) continue;
        if(v[i] <= val) L.push_back(v[i]);
        else R.push_back(v[i]);
    }

    L.push_back(val);

    if(L.size() == k + 1) return v[k];
    if(k < L.size() - 1) return sdo(L, k);
    if(R.size()) return sdo(R, k - L.size());

}

int main()
{
    int n, k;
    vector<int> v;
    ifstream in("sdo.in");
    ofstream out("sdo.out");

    in >> n >> k;

    k--;

    for(int i = 0; i < n; ++i) {
        int x;
        in >> x;
        v.push_back(x);
    }
    out << sdo(v, k);

    in.close(); out.close();
    return 0;
}