Zadanie "Skrzaty" z VI OIG

Dlaczego /64?
1 pole w wektorze<bool> przechowuje 1 skrzata a nie 64.
I nie, wydajność nie będzie taka sama.
Będzie wielokrotnie mniejsza.
Tak, sprawdzałem w tym konkretnym zastosowaniu.

I nie, wydajność nie będzie taka sama. Będzie wielokrotnie mniejsza.

Jeżeli uważasz, że wiesz lepiej co jest lub będzie szybsze to myślę, że kontynuowanie tego tematu nie ma już najmniejszego sensu. Dodam jeszcze, że Twoje stwierdzenie jest nieprawdziwe, ponieważ wygenerowany kod binarny aplikacji będzie taki sam dla tablicy jak i dla vectora w trybie Release, więc te same instrukcje procesora w tej samej kolejności nie nie mogą być 'wielokrotnie' wolniejsze. Takie tematy były na forum i nawet wygenerowany kod asemblera był przedstawiany dla obu przypadków przez osoby, które mają nieporównywalnie większą wiedzę i doświadczenie niż Ty. Niemniej jednak jeżeli uważasz, że Ty wiesz 'lepiej' to nie mam nic przeciwko abyś miał własne poglądy, dopóki nie zaczynasz wygłaszać fałszywych twierdzeń na forum, bo potem n-kolejnych początkujących programistów takie przeczytane stwierdzenie przyjmuje za prawdę i chwali się swoją nierzetelną wiedzą wśród znajomych, propagując tym samym informacje niezgodne z prawdą.

Witam.
Byłoby miło poczekać z zamykaniem na moją odpowiedź.
anyways oto ona:
Będzie ponieważ w 1 uint64_t przechowywane są wartości 64 skrzatów a w bool 1, więc podczas kopiowania z safeT do safe wykonywane jest iloscSkrzatow/64 a nie iloscSkrzatow operacji bitowych.
Jak pisałem sprawdziłem to w praktyce.
Ale nie, bo "wygenerowany kod binarny aplikacji będzie taki sam dla tablicy jak i dla vectora".
Cy pan nie czyta to co piszę, czy my się nie rozumiemy?
Jedyne co otrzymuje to sugestię, że nie potrafię korzystać z najoczywistszych funkcji (vector.reserve/resize).
Wszystko co piszę odnosi się do TEJ KONKRETNEJ SYTUACJI i pochodzi w większości z praktyki, więc co mają do rzeczy początkujący programiści?
Tego, że złożoność nie jest kwadratowa np. nie skomentowaliście.
Może początkujący programiści będą myśleli, że n = n^2?
Chyba ma pan rację, moja dalsza obecność tutaj nie ma sensu.

Złożoność masz n*m


Stałą masz faktycznie bardzo małą, zaledwie 1 if albo jakaś operacja bitowa. Kompilator być może Ci to jakoś optymalizuje, ale fakt faktem, że powinieneś założyć że nie masz tu złożoności liniowej i tego się trzymać. W innych zadaniach już tak łatwo żyłować się nie będzie dało gdy stałe będziesz miał bardzo duże. Dla tego typu programów może tego aż tak nie będziesz widział, jak w przypadku bardziej skomplikowanych.

To tak jakby mówić, że f(x) = x+0.001*x^2 to nie funkcja kwadratowa, gdyż 0.001 jest wystarczająco małe.
Jeśli dostajesz 100 pkt. za to zadanie to gratulacje.

//edit
n*m*m odpada, nie zauważyłem, że tam jest break. Tak więc zostaje n*m.

A jednak ktoś czyta to, co piszę, miło.
Nie mówiłbym, że jest liniowa, gdyby z logów wynikało inaczej.
Jest to spowodowane konstrukcją tych konkretnych test casów (mnóstwo sytuacji 1 iloscSkrzatow).

Ale na jakich testach sprawdzałeś? To normalne, że niekiedy brute force'y działają 'prawie liniowo' dla zupełnie losowych testów, tu właśnie chodzi o to aby takiego rozwiązania nie udało się uwalić jakimś sprytnym testem.

Rozpatrywanie złożoności nie ma sensu jeśli mamy tylko 1 przypadek bez zmiennych. Jeśli testujesz rozwiązanie na stałych danych to złożoność też masz stałą.

Tutaj akurat różnicę zobaczyłbyś dla większych danych, lub na 'sprytniejszych' testach. Dla n i m < 10^999 rozwiązanie liniowe działałoby przykładowo 10 dni a Twoje 10000 dni, na mniejszych testach po prostu nie widać różnicy gdyż masz za małą stałą.
Jeśli miałbyś mniejszą złożoność to nie musiałbyś się bawić w tego typu optymalizacje, mógłbyś nawet mieć ogromne stałe, a i tak byś się zmieścił w czasie.

A jakie jest to lepsze rozwiązanie?
Sprawdzałem na ostatnim teście od nich, na wszystkich pozostałych mam w dolnej połowie limitu.
/edit: Nie, inne dane by nic nie zmieniły.
Już teraz scanf to ~10%mocy, żeby nie było == za pierwszym razem smok musiałby obserwować pierwsze 64 skrzaty -> ~40 razy więcej miejsc niż teraz -> więcej czasu w scanf niż w algorytmie -> wszystko udupione lub wielokrotnie krotnie dłuższe maksymalne czasy. Te przykłady które są są złośliwe.

Nie używaj dzielenia bo jest wolne i niepotrzebne.