Algorytm sortowania zadanie

Dzień dobry

Mam problem z poniższym zadaniem. Po wrzuceniu rozwiązania do sprawdzarki "themis" otrzymuje 12 sprawdzeń pozytywnych i 1 negatywne (time limit exceeded).

Treść zadania:

Problem code: PARTITION | Time: 2 s | Memory: 32 MB | Solved: no | print

Wielkie Klasowe Mistrzostwa W Bieganiu Za Piłką zbliżają się wielkimi krokami. Rywalizacja toczyć się będzie między Drużyną Michała i Drużyną Tych Drugich. W związku z niebagatlną rangą wydarzenia, obie drużyny wylewają z siebie ostatnie poty na treningach. Michał rozpoczyna każdy trening od przeglądu stanu osobowego drużyny. Z grubsza polega to na tym, że wszyscy jego zawodnicy mają ustwić się w szeregu. Zadanie to nie jest trudne, jednak Michał jest surowym i wymagającym kapitanem (a przy okazji skrytym milośnikiem informatyki, chociaż udaje, że wcale nie) i stawia swojej drużynie dodatkowy warunek: mają oni ustawić się od najniższego do najwyższego. W takich okolicznościach zawodnicy gubią się i patrzą na Michała tępo. Michał wskazuje zatem jednego z nich i wydaje następującą komendę: wszyscy niżsi mają stanąć przed wskazanym zawodnikiem, obok mają ustawić się wszyscy tak samo wysocy, a na końcu mają stanąć wszyscy wyżsi.

Mając dane początkowe ustawienie zawodników oraz numer zawodnika wskazanego przez Michała, wypisz jedno z możliwych końcowych ustawień.

Wejście
W pierwszej linii wejścia dane są liczby n oraz k (1 ≤ n ≤ 10^6, 1 ≤ k ≤ n) oznaczające liczbę zawodników w drużynie oraz numer wskazanego zawodnika. W drugiej linii danych jest n liczb nie większych od 10^6 – są to wzrosty kolejnych zawodników.

Wyjście
Należy wypisać n liczb: wzrosty zawodników w szeregu po wykonaniu komendy Michała. W sytuacji, gdy możliwych jest wiele poprawnych odpowiedzi, należy wypisać dowolną z nich.

Przykład
Dla danych wejściowych

9 3
1 3 5 7 9 2 4 6 8
poprawną odpowiedzią jest
3 1 4 2 5 9 6 8 7

Mój kod:

#include <iostream>

using namespace std;

int ile_mniejszych(int arr[], int k, int n)
{
    int licz = 0;
    for(int i = 0; i<n; i++)
        if(arr[i]<arr[k])
            licz++;

    return licz;
}

int ile_wiekszych(int arr[], int k, int n)
{
    int licz = 0;
    for(int i = 0; i<n; i++)
        if(arr[i]>arr[k])
            licz++;
    return licz;

}
int ile_rownych(int arr[], int k, int n)
{
    int licz = 0;
    for(int i = 0; i<n; i++)
        if(arr[i]==arr[k])
            licz++;
            return licz;

}

void ustaw(int arr[], int k, int n)
{
    int wzrost = arr[k];
    int poz = k;

    int pozostali_nizsi = 0;
    int pozostali_wyzsi = 0;
    int pozostali_rowni = 0;
    for(int i = 0; i<n; i++)
        if(arr[i]<arr[k])
            pozostali_nizsi++;
        else if(arr[i]==arr[k])
            pozostali_rowni++;
        else if(arr[i]>arr[k])
            pozostali_wyzsi++;

    //int pozostali_nizsi = ile_mniejszych(arr,k,n);
    //int pozostali_wyzsi = ile_wiekszych(arr,k,n);
    //int pozostali_rowni = ile_rownych(arr,k,n);
    int i = 0;
    int pozycja= 0;
   while(pozostali_nizsi>0)
        {

            if(arr[i]<wzrost)
            {
                swap(arr[i],arr[pozycja]);
                pozycja++;
                pozostali_nizsi--;
            }
            i++;

        }

        i = pozycja;

        while(pozostali_rowni>0)
        {

            if(arr[i]==wzrost)
            {
                swap(arr[i],arr[pozycja]);
                pozycja++;
                pozostali_rowni--;
            }
            i++;

        }

        i = pozycja;

        while(pozostali_wyzsi>0)
        {

            if(arr[i]>wzrost)
            {
                swap(arr[i],arr[pozycja]);
                pozycja++;
                pozostali_wyzsi--;
            }
            i++;

        }

        i = 0;

}

int main()
{
    int n;
    int k;

    cin >> n >> k;
    int arr[n];
    k--;
    for(int i = 0; i<n; i++)
       cin >> arr[i];

    ustaw(arr,k,n);
    for(int i = 0; i<n; i++)
        cout << arr[i] << " ";
}

Sugerując się błędem chodzi pewnie o to, że program działa za wolno.

Zadanie jest proste jak konstrukcja cepa.
Masz dosłownie zaimplementować rozkaz "Michała", nie trzeba nic wymyślać, i uzyskasz złożoność liniową.
Powinno się zmieścić w 20(mi tyle wyszło używając STL) 50 linijkach.

@Czitels: Zgadza się to jest problemem. Program nie mieści się w czasie 2 sekund przy dużych danych.

Zacznij od tego. Wersja czytelna podzielona na funkcje więc dłuższa.
Jak pogrzebiesz w dokumentacji STL kropki zastąpisz dwoma linijkami.

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <tuple>
 
void setupIO() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

std::tuple<int, std::vector<int>> load(std::istream& in)
{
    size_t n, k;
    std::cin >> n >> k;
    std::vector<int> v;
    v.reserve(n);
    std::copy_n(std::istream_iterator<int>{in}, n, std::back_inserter(v));
    return {v[k - 1], v};
}

void solve(int h, std::vector<int>& v)
{
    ..... // tu zmodyfikuj v do żądanej kolejności elementów
}

void print(const std::vector<int>& v)
{
    std::copy(v.begin(), v.end(), std::ostream_iterator<int>{std::cout, " "});
}

int main(int argc, char const *argv[]) {
    setupIO();
    auto [h, v] = load(std::cin);
    solve(h, v);
    print(v);

    return 0;
}

https://godbolt.org/z/K95v6P

@MarekR22: Dziekuje udało się. Zastosowałem sort. Nie wiem tylko czy wykładowca zaliczy mi użycie gotowego algorytmu.