Outów nie będzie ¯\_(ツ)_/¯. Pozostańmy przy sumie, bo to lepszy pomysł niż wszystkie outy. Iny zostawiam dla potomności, ale outy w mojej paczce są złe i takie pozostaną.

Tym samym potwierdzę, że suma poprawnych outów wynosi 62688883625.

9: 3463073456
8: 646459504
7: 1243297360
6: 1071704584
5: 1471335772
4: 70029708

ile się zgadza?

Ew. może wrzućcie outy? XD

Zgadzam się z Soko co do wie3.in i wie13.in

U mnie 2773117020.

Zgadzam się z Soko co do wie3.in. Czy na wie13.in masz 3030542428?

A może taki test?
In: 2137 2137 100
Out: 171618146

Disclaimer: nie daję ręki, palca ani nawet włosa za swój out. :P

Marcin, iterowanie się kolejno po elementach tablicy jest dużo szybsze niż skakanie po pamięci.

Po operacji ++count[GetElement(i)] spodziewałbym się, że jest ograniczona przez dostęp do pamięci. Nie byłbym w najmniejszym stopniu zdziwiony dwukrotnym spowolniem w sytacji w której dane pochodzą z pamięci.

Ale dużo ciekawsza pułapka mogła czekać w FUT. Umieszczenie w kodzie "int GetP() { return 123456789; }" spowoduje, że kompilator nie będzie generował dzieleń dla %p, ale zamieni je w mnożenia. W faktycznej sprawdzarce niemal napewno ta dana pochodzi z pliku wejściowego i wymaga wykonywania dzieleń (a przynajmniej kompilator nie zrobi tego za nas).

+3

>for(int i = 0; i < N; ++i) ++count[GetElement(i)]

Czemu miałoby to zająć ekstra 1.5s? Coś takiego mi w testach zajęło 0.49s, wraz z liczeniem GetElement (=i%1000000 +1). Czy jednak zadanie testowe nie jest miarodajne? :>

Nie potwierdzam. Jestem przekonany, że odpowiedzią do wie3.in jest 2300494716. Zaraz stworzę swoje outy i dam znać.

Edit: Suma outów (*bez* przekręcania mod 2^32 przy dodawaniu outów) to u mnie 62688883625.

Mam nadzieję być kiedyś osobą, dla której takie zadania to byłaby przyjemność.

No to spróbujmy kroczek dalej z paczką dla 4 subtaska: http://students.mimuw.edu.pl/~wn341489/Wie4.zip

Tostujcie co znaleźliście, ja zacznę.

https://imgur.com/a/pYMufiZ

Gdy zegar wybija 0. Firefox 63, Linux x86_64.

Coś więćej o tym wzorku powiesz? Zwłąszcza, co to f(.) - ta nasza suma?

Ja, po zorientowaniu się, że jednak nie mogę N po prostu rozesłać do innych instancji ;-) kombinowałem tak:

Zafiksujmy sobie k, nie będę go co chwila pisał.
Nasz ciąg S_n = nasz ciąg = \sum_0^k C(n,k)
S_k = 2^n (a wcześniejsze nas nie obchodzą).
S_{n+1} = 2 S_n - C(n,k ) (to jest wprost z trójkąta Pascala, linijka, która nas interesuje to suma linijki wyżej i linijki wyżęj, ale bez ostatnoiego elementu, który poszedł w prawo).
Na C(n,k) też jest przyjemna rekurrejcnaj, C(n,k)= C(n-1,k)n/(n-k), oznacze sobie to C_n

Jeśli moglibyśmy jechać od początku, (tzn S_k=2^k, C(k,k)=1) prosto, ale liniowo i sekwencyjnie wyliczymy S_n. Ale można zrobić coś więcej, to wszytko są liniowe operacje, da się policzyć, że jeśli na poziomie n1 mamy jakieś S_n1, C_n1 (nie znając ich!) to ileś poziomów niżej, na n2: C_n2 = br C_n1, S_n2 = sr S_n1 + ar C_n1.
Na wspołczynniki sr,ar,br można napisać rekurencję, przelecieć zakres n1..n2 wykonując głowną cześć pracy, i dopiero pod koniec odczytać Sn_1 i C_n1, który przypełzły z instancji wcześniejszej, w pakiecie wraz z liczbą N. Jeśli N jest w zakresie [n1,n2] to obliczamy Sn i wyrzucsamy w sieć wynik, jeśli było wcześneij, forwardujemy wcześniejszy wynik, jeśli dopiero będzie, oblicamy S_n2 i C_n2, aby nakarmić kolejną instncję. Ostatnia instancja wypisuje.

Cała praca jest robiona najpierw, a potem informacja leci w kółeczko. Niestety, nie pozbyłem się odwrotnośći modulo, bo trzeba było zająć się i teatrem, więc może się nie zmieścić.

teatr:
92 instancji pracuje na takich kratkach na "kostce" gdzie na bokach są widzowie.
xxxx
xxx
xx
x
Każda kosteczka ma doki o dlugości ~n/14. Zliczam w niej inwersji na obu tych bokach i inwersje pomiędzy bokami, w instancji 0 skladam ( wszystkie 'cross inwersje', wszystkie wewnętrzne z jednego boku, oraz jedna z boku prostopadłego, o której zapomnialem:) )