Rotacija dvostruke liste

Klasi DvostrukaLista dodati funkciju članicu

void rotiraj(long long k);

koja rotira listu za k mesta: za pozitivno k ulevo, a za negativno udesno. Rotacija za jedno mesto ulevo premešta prvi element na kraj liste, a rotacija za jedno mesto udesno premešta poslednji element na početak. Na primer, lista 1 2 3 4 5 rotirana za 2 postaje 3 4 5 1 2, a rotirana za -2 postaje 4 5 1 2 3.

Funkcija ne sme da pravi ni da briše čvorove, niti da prepisuje podatke. Ako je $n$ dužina liste i $r = k \bmod n$, složenost mora da bude $O(\min(r, n - r))$, nezavisno od veličine broja k.

Funkcija proveri_invarijantu iz zadatka 1 već je data u postavci.

Uputstvo: Čvorovi zajedno sa sentinelom već čine krug. Koliko se pravih čvorova pomera pri rotaciji?

Pitanje za razmišljanje: Koliko je pokazivača potrebno promeniti, i da li taj broj zavisi od k?

Ulaz

U prvom redu učitava se broj n $(0 \le n \le 10^5)$, a zatim n celih brojeva. Zatim se učitava broj rotacija q $(1 \le q \le 1000)$, a zatim q celih brojeva k $(|k| \le 10^{18})$. Provera invarijante se radi samo za $n \le 1000$.

Izlaz

Posle svake rotacije u posebnom redu ispisati prvi element liste (- ako je lista prazna), a na kraju, u poslednjem redu, celu listu. Ako invarijanta nije očuvana, program ispisuje redni broj rotacije posle koje je narušena.

Primer

Ulaz

5
1 2 3 4 5
3
2
-2
8

Izlaz

3
1
4
4 5 1 2 3

Postavka

dvostruka_lista.h

#ifndef DVOSTRUKA_LISTA_H
#define DVOSTRUKA_LISTA_H

#include <cassert>
#include <cstddef>

// Dvostruko povezana lista sa sentinel-cvorom iz glave 4.
//
// Sentinel-cvor stoji izmedju poslednjeg i prvog elementa, pa cvorovi
// cine krug. U praznoj listi sentinel pokazuje sam na sebe. Zahvaljujuci
// tome nijedan pokazivac nije nullptr i umetanje i brisanje nemaju
// posebnih slucajeva.
//
// Pored operacija iz knjige, klasa ima i nekoliko koje se iz njih lako
// izvode, kao i iterator (vidi odeljak o iteratorima u glavi i README).
//
// Tip T mora da podrzava kopiranje i podrazumevano konstruisanje (zbog
// polja podatak u sentinel-cvoru). Funkcija pronadji zahteva operator ==.
//
// Invarijanta:
//   Za svaki cvor c, ukljucujuci i sentinel, vazi
//   c->sledeci->prethodni == c i c->prethodni->sledeci == c.
//   Izmedju dva prolaska kroz sentinel nalazi se tacno velicina_ cvorova.

template <typename T>
class DvostrukaLista {
public:
    struct Cvor {
        T podatak;
        Cvor* prethodni;
        Cvor* sledeci;

        Cvor() : podatak(), prethodni(this), sledeci(this) {}
        Cvor(const T& p, Cvor* pre, Cvor* sl)
            : podatak(p), prethodni(pre), sledeci(sl) {}
    };

    class Iterator;

    DvostrukaLista() : sentinel(new Cvor()), velicina_(0) {}

    ~DvostrukaLista()
    {
        isprazni();
        delete sentinel;
    }

    DvostrukaLista(const DvostrukaLista&) = delete;
    DvostrukaLista& operator=(const DvostrukaLista&) = delete;

    bool prazna() const { return sentinel->sledeci == sentinel; }
    std::size_t velicina() const { return velicina_; }

    Cvor* prvi() const { return sentinel->sledeci; }
    Cvor* poslednji() const { return sentinel->prethodni; }
    Cvor* kraj() const { return sentinel; }

    void umetni_ispred(Cvor* c, const T& x);
    void obrisi(Cvor* c);

    void dodaj_na_pocetak(const T& x) { umetni_ispred(prvi(), x); }
    void dodaj_na_kraj(const T& x) { umetni_ispred(kraj(), x); }
    void umetni_iza(Cvor* c, const T& x) { umetni_ispred(c->sledeci, x); }

    void obrisi_sa_pocetka() { obrisi(prvi()); }
    void obrisi_sa_kraja() { obrisi(poslednji()); }
    void isprazni();

    void rotiraj(long long k);

    Cvor* pronadji(const T& x) const;

    bool proveri_invarijantu() const;

    Iterator begin() const { return Iterator(prvi()); }
    Iterator end() const { return Iterator(kraj()); }

private:
    Cvor* sentinel;
    std::size_t velicina_;
};


// -----------------------------------------------------------------------------
// Iterator
//
// Iterator cuva pokazivac na cvor, ali ga ne otkriva korisniku: dozvoljava
// samo pristup podatku i prelazak na susedni cvor. Zahvaljujuci funkcijama
// begin() i end(), lista moze da se obilazi i petljom
//     for (int x : lista) ...
// Kao i kod std::list, end() je pozicija sentinel-cvora.
// -----------------------------------------------------------------------------

template <typename T>
class DvostrukaLista<T>::Iterator {
public:
    explicit Iterator(Cvor* c) : trenutni(c) {}

    T& operator*() const { return trenutni->podatak; }

    Iterator& operator++()
    {
        trenutni = trenutni->sledeci;
        return *this;
    }

    Iterator& operator--()
    {
        trenutni = trenutni->prethodni;
        return *this;
    }

    bool operator==(const Iterator& drugi) const { return trenutni == drugi.trenutni; }
    bool operator!=(const Iterator& drugi) const { return trenutni != drugi.trenutni; }

private:
    Cvor* trenutni;
};


// -----------------------------------------------------------------------------
// Definicije funkcija clanica
// -----------------------------------------------------------------------------

template <typename T>
void DvostrukaLista<T>::umetni_ispred(Cvor* c, const T& x)
{
    Cvor* novi = new Cvor(x, c->prethodni, c);
    c->prethodni->sledeci = novi;   // jos se koristi stara vrednost c->prethodni
    c->prethodni = novi;
    ++velicina_;
}

template <typename T>
void DvostrukaLista<T>::obrisi(Cvor* c)
{
    assert(c != sentinel);
    c->prethodni->sledeci = c->sledeci;
    c->sledeci->prethodni = c->prethodni;
    delete c;
    --velicina_;
}

template <typename T>
void DvostrukaLista<T>::isprazni()
{
    while (!prazna())
        obrisi(prvi());
}

// Cvor je tip definisan unutar sablona, pa se van klase njegovo ime pise
// kao typename DvostrukaLista<T>::Cvor. Rec typename kaze prevodiocu da je
// to ime tipa.
template <typename T>
typename DvostrukaLista<T>::Cvor* DvostrukaLista<T>::pronadji(const T& x) const
{
    for (Cvor* p = prvi(); p != kraj(); p = p->sledeci)
        if (p->podatak == x)
            return p;
    return nullptr;
}


// TODO: Rotira listu za k mesta: za k > 0 ulevo, za k < 0 udesno, u vremenu
// O(min(k mod n, n - k mod n)).
template <typename T>
void DvostrukaLista<T>::rotiraj(long long k)
{
    // Ovde ide vasa implementacija
}

// Obilazi listu od sentinela, proverava obe veze svakog cvora i broji cvorove.
// Obilazak je ogranicen sa velicina_, pa se zavrsava i kada je lanac sledeci
// pokvaren.
template <typename T>
bool DvostrukaLista<T>::proveri_invarijantu() const
{
    Cvor* c = sentinel;
    std::size_t broj = 0;
    do {
        if (c->sledeci->prethodni != c || c->prethodni->sledeci != c)
            return false;
        c = c->sledeci;
        ++broj;
    } while (c != sentinel && broj <= velicina_);

    return c == sentinel && broj == velicina_ + 1;
}

#endif

main.cpp

#include <iostream>

#include "dvostruka_lista.h"

template <typename T>
void ispisi(const DvostrukaLista<T>& l)
{
    for (auto p = l.prvi(); p != l.kraj(); p = p->sledeci)
        std::cout << p->podatak << " ";
    std::cout << std::endl;
}

int main()
{
    int n;
    std::cin >> n;

    DvostrukaLista<int> l;
    for (int i = 0; i < n; ++i) {
        int x;
        std::cin >> x;
        l.dodaj_na_kraj(x);
    }

    // Provera je O(n), pa bi na velikom ulazu sama pokvarila slozenost.
    bool proveravaj = n <= 1000;

    int q;
    std::cin >> q;
    for (int i = 1; i <= q; ++i) {
        long long k;
        std::cin >> k;
        l.rotiraj(k);
        if (proveravaj && !l.proveri_invarijantu()) {
            std::cout << "invarijanta je narusena posle rotacije " << i << std::endl;
            return 0;
        }
        if (l.prazna())
            std::cout << "-" << std::endl;
        else
            std::cout << l.prvi()->podatak << std::endl;
    }
    ispisi(l);

    return 0;
}