https://stackoverflow.com/questions/3413166/when-does-a-process-get-sigabrt-signal-6

Moj strzal w ciemno: trzymasz dane w zmiennych lokalnych i przepelnia sie stos.

Co oznacza komunikat:
0 process exited due to signal 6

Pobrałem z tego forum kilka danych do sprawdzenia i program liczy poprawne dane zarówno, gdy odpalam go z Visuala, jak i cmd
Niestety po wysłaniu otrzymałem Błąd wykonania i podany wyżej komunikat

Ja też ciągle nie mam pojęcia jak się robi te ryki... Powalone to jakieś :P

Liczba możliwych stanów, to iloczyn po wszystkich przedziałach 1 + długość przedziału. Suma wszystkich liczb, które wymnażamy jest równa n + 1. Jak mamy iloczyn a_1 * a_2 * ... * a_k, to rozbijamy a_1 na (a_1^(1 / a_1)) ^ a_1. Dostajemy w ten sposób iloczyn mający a_1 + a_2 + ... + a_k czynników, każdy z nich jest postaci x^(1/x). Dla całkowitych x maxymalna wartość x^(1/x) jest osiągalna dla x = 3, stąd taki iloczyn szacuje się przez (3^(1/3))^(a_1 + a_2 + ... + a_k), czyli O(3^(n / 3))

Why 3^(n/3)?

Ciekawostka: dla dowolnej funkcji wypukłej f suma po wszystkich kubkach pojemność * f(temperatura) tylko maleje z czasem (jak robimy dzielenie, to wartość ta się nie zmienia, jak mieszanie, to z wypukłości maleje). Zatem jeżeli jest spełniony warunek, że zawsze k najzimniejszych litrów herbaty ma łączną energię mniejszą w stanie początkowym niż w końcowym, to zachodzi nierówność między tymi sumami, a dokładnie to mówi nierówność Karamaty.

Sprawdziłem liniowo, również pozdrawiam long longi...

Ładnie graficznie można to sobie zinterpretować tak:
Zróbmy wykres objętość->energia (energia to objetość * temperatura ).
Zróbmy łamaną składając się z kolejnych wektorów odpowiadających kubkom, posortowanym malejąco po temperaturze:
(zaznaczamy 0, mając kubek t=50, v=2 punkt to 2,100, łączymy go linią, drugi kubek to np t=20, v=2, czyli energia 40, wiec kolejnym punktem łamanej będzie 4,140).
Teraz, da sie rozlać wtedy i tylko wtedy, gdy oba wykresy
-kończą w tym samym punkcie.
-wykres zamówionych herbatek zawsze jest pod wykresem rozlanych herbatek.
(przypominam, że maja być posortowane po temperaturze, wtedy wykresy to ładne łamane łuki).

Oprócz sortowania sprawdzanie jest liniowe, dla każdego punktu wykresu zamówionych odczytuje sobie wartość na drugim wykresie (interpolując między punktami).
I tu wchodzi zapotrzebowanie na int64_t. Nie tylko energia takiej zmiennej potrzebuje, ale i objętość może 2^32 przekroczyć;-)

Polecam flagę -fsanitize=undefined

long longi?

Właśnie zrobiłem coś podobnego, ale albo zwaliłem implementację, albo czegoś nie uwzględniłem - 5/10.

Edit: pozdrawiam long longi... :C

W tym momencie jedno załadowanie strony zajmuje minutę :| (serio, patrzyłem na czas nawet)

Przetwarzamy wartości 1, 2, ..., n rosnąco, decydując dla każdej czy bierzemy ją do naszego podciągu. Jeśli bierzemy wartość x, to liczba inwersji zwiększa się o to ile wzięliśmy już wcześniej wartości po prawej stronie od x.

Naiwnie to co musielibyśmy pamiętać to zbiór pozycji które wybraliśmy, to dałoby 2^n stanów.

Zauważmy, że jeśli pewne z już przetworzonych pozycji tworzy w permutacji spójny przedział, to nie interesuje nas już dokładnie które z tych pozycji wybraliśmy do podciągu, a jedynie ich liczba. Sklejając stany w ten sposób dostajemy ich około 3^(n/3) w najgorszym wypadku.

Potwierdzam

A jakich nie przeszedł? :>