Umetanje niza

Napisati funkciju

template <typename T>
void umetni_niz(DinamickiNiz<T>& a, std::size_t indeks, const DinamickiNiz<T>& b);

koja umeće sve elemente niza b ispred pozicije indeks niza a $(0 \le \text{indeks} \le n)$, u vremenu $O(n + m)$, gde su n i m veličine nizova. Elementi niza a se pomeraju jednom (rešenje sa m poziva funkcije umetni je $O(n \cdot m)$). Koristi se klasa DinamickiNiz<T> iz zaglavlja dinamicki_niz.h.

Izazov: rešenje treba da radi i za poziv umetni_niz(a, j, a).

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva niza a. Nakon toga učitava se broj m $(0 \le m \le 10^5)$, a zatim m celih brojeva niza b. Na kraju se učitavaju indeksi i $(0 \le i \le n)$ i j $(0 \le j \le n + m)$.

Izlaz

U prvom redu ispisati niz a nakon poziva umetni_niz(a, i, b), a u drugom redu niz a nakon poziva umetni_niz(a, j, a).

Primer

Ulaz

3
1 2 3
2
8 9
1 1

Izlaz

1 8 9 2 3
1 1 8 9 2 3 8 9 2 3

Postavka

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Umece sve elemente niza b ispred pozicije indeks niza a,
    // u vremenu O(n + m).
    template <typename T>
    void umetni_niz(DinamickiNiz<T>& a, std::size_t indeks, const DinamickiNiz<T>& b)
    {
        // Ovde ide vasa implementacija
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> a;
    DinamickiNiz<int> b;
    ucitaj(a);
    ucitaj(b);

    std::size_t i, j;
    std::cin >> i >> j;

    matf::umetni_niz(a, i, b);
    ispisi(a);

    matf::umetni_niz(a, j, a);
    ispisi(a);

    return 0;
}

Rešenje

main.cpp

#include <iostream>

#include "dinamicki_niz.h"

namespace matf {

    // Umece sve elemente niza b ispred pozicije indeks niza a,
    // u vremenu O(n + m).
    template <typename T>
    void umetni_niz(DinamickiNiz<T>& a, std::size_t indeks, const DinamickiNiz<T>& b)
    {
        assert(indeks <= a.velicina());

        // Ako je &a == &b, pomeranje bi menjalo elemente koji se tek kopiraju,
        // pa se umece kopija niza b (O(m), ne menja ukupnu slozenost).
        if (&a == &b) {
            DinamickiNiz<T> kopija(b);
            umetni_niz(a, indeks, kopija);
            return;
        }

        std::size_t n = a.velicina();
        std::size_t m = b.velicina();

        // Prosirenje za m mesta: amortizovano O(m).
        for (std::size_t k = 0; k < m; ++k)
            a.dodaj(T());

        // Jedno pomeranje repa [indeks, n) za m mesta udesno; ide se zdesna
        // nalevo, da se ne prepisu elementi koji tek treba da se pomere.
        for (std::size_t k = n; k > indeks; --k)
            a[k - 1 + m] = a[k - 1];

        for (std::size_t k = 0; k < m; ++k)
            a[indeks + k] = b[k];
    }

} // namespace matf

template <typename T>
void ucitaj(DinamickiNiz<T>& niz)
{
    std::size_t n;
    std::cin >> n;
    for (std::size_t i = 0; i < n; ++i) {
        T x;
        std::cin >> x;
        niz.dodaj(x);
    }
}

template <typename T>
void ispisi(const DinamickiNiz<T>& niz)
{
    for (std::size_t i = 0; i < niz.velicina(); ++i)
        std::cout << niz[i] << " ";
    std::cout << std::endl;
}

int main()
{
    DinamickiNiz<int> a;
    DinamickiNiz<int> b;
    ucitaj(a);
    ucitaj(b);

    std::size_t i, j;
    std::cin >> i >> j;

    matf::umetni_niz(a, i, b);
    ispisi(a);

    matf::umetni_niz(a, j, a);
    ispisi(a);

    return 0;
}