• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

C++ vector assign złożonność czasowa / Zadanie Włoska Czekolada IX OIG

Object Storage Arubacloud
0 głosów
198 wizyt
pytanie zadane 9 lutego 2023 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
edycja 9 lutego 2023 przez pasjonat_algorytmiki

Robiłem zadanie, i robiłem tam assigna, chciałem sprawdzić czy działa pomysł poprawność, w sensie czy daje dobre odpowiedzi. (wydawało mi się, że będzie O(N^2), bo assign działa W O(N), niedowieżam, bo wchodzi na 100, a N <= 10^6, czyli assign działa w O(1)? Linia 30.

Kod:

#include <iostream>
#include <vector>

using namespace std;

int n = 0, wczytana_liczba = 0, wyn = 0;
vector<int> liczby;
vector<int> ile(1e6+1,0);
vector<int> ile_mamy(1e6+1,0);

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        ile[wczytana_liczba]++;
        liczby.push_back(wczytana_liczba);
    }
    for (int i = 0; i < n; ++i)
    {
        ile_mamy[liczby[i]]++;
        if (ile_mamy[liczby[i]] == ile[liczby[i]])
        {
            wyn++;
            ile_mamy.assign(1e6+1,0);
        }
    }

    cout << wyn << '\n';

    return 0;
}

 

komentarz 9 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Bo ten assign może wykonać się nawet N razy, opcje są 2, albo assign działa szybko, albo testy są dobrane fatalnie, ale to by było dziwne, bo to był OIG, i testów jest dużo.

Btw. Wiem, że nie muszę robić assigna, tylko da się całośc w złożonności amortyzowanej O(N), zrobić, ale to miał być brut.
komentarz 9 lutego 2023 przez Whistleroosh Maniak (56,980 p.)
Jakiego rzędu jest zmienna wyn? W sensie jaką ma maksymalną wartość?
komentarz 9 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Taka jest treść:

Marcin przyszedł do szkoły z podłużną tabliczką włoskiej czekolady, składającej się z N kostek ułożonych jedna obok drugiej. Każda kostka ma określony smak. Podczas pierwszej przerwy, znajomi Marcina od razu zauważyli, że ma ze sobą niezwykłą tabliczkę. Każdy chce jej spró bować, zatem prosi o kawałek. Jako, że Marcin jest dobrym kolegą, postanowił się podzielić słodką przekąską w następujący sposób. Dzieli czekoladę na spójne fragmenty tak, że każda kostka należy do dokładnie jednego fragmentu. Powiemy, że dany fragment jest unikatowy, jeśli istnieje w nim conajmniej jedna kostka o pewnym smaku oraz w żadnym innym fragmencie nie występuje ani jedna kostka o tym smaku. Marcin chce, aby każdy fragment otrzymany z podziału czekolady był unikatowy. Chłopiec postanowił, że każdy fragment otrzyma jeden kolega. Aby jak najwięcej osób mogło spróbować włoskiej czekolady, Marcin chce podzielić ją na jak największą liczbę fragmentów. Pomóż mu w tym zadaniu zanim skończy się przerwa.

Wejście:

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita N (1 <= N <= 10^6 ) oznaczająca długość czekolady. W drugim wierszu znajduje się N dodatnich liczb całkowitych nie większych niż 10^6 . Liczby te oznaczają smaki kolejnych kostek czekolady. Dwie kostki czekolady są tego samego smaku wtedy i tylko wtedy, gdy ich liczby są równe.

Wyjście:

Twój program powinien wypisać na standardowe wyjście jedną liczbę całkowitą oznaczającą maksymalną liczbę fragmentów, na jaką Marcin może podzielić czekoladę tak, aby każdy z nich był unikatowy.
1
komentarz 9 lutego 2023 przez Whistleroosh Maniak (56,980 p.)

Zgodnie z dokumentacją assign działa liniowo. Więc może rzeczywiście wyniki są rzędu <= 100. Możesz wysłać błedny program i zobaczyć jakie są oczekiwane wyniki.

komentarz 9 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

No tak, wszystko jasne, dziwne że na OIG-u taki babol się wkradł:

Nie mogłem uwieżyć co się dzieje. Dzięki za pomoc!

komentarz 9 lutego 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

@pasjonat_algorytmiki, 

No i wystarzczy poprostu zwykłym forem cofnąć się do przedziału od jakiego zaczeliśmy nowe dodawanie, i wykonamy 2N operacji, czyli wchodzi zachlan w O(N).

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
3 odpowiedzi 269 wizyt
pytanie zadane 24 lutego 2023 w C i C++ przez polandonion Mądrala (7,140 p.)
0 głosów
1 odpowiedź 162 wizyt
pytanie zadane 19 maja 2022 w C i C++ przez pasjonat_algorytmiki Pasjonat (19,540 p.)
+1 głos
2 odpowiedzi 655 wizyt
pytanie zadane 12 stycznia 2022 w JavaScript przez Martita Bywalec (2,500 p.)

92,675 zapytań

141,579 odpowiedzi

320,058 komentarzy

62,039 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...