Widzę że nie ma nigdzie rozwiązania, a komuś już zacząłem moje wykładać, więc się podzielę.

Cały oznaczał liczbę kamyków aktualnie na planszy przez m.
W danym momencie wynik to co najmniej m/2, bo możemy wziąć kamienie parzyste albo nieparzyste.
Więc jak wylosujemy sobie trochę kamyków to jest duża szansa że któryś jest w odpowiedzi. To chcemy teraz rozwiązać problem znalezienia wyniku z jednym kamieniem.
1) Długość skoku będzie liczbą pierwszą - jeśli nie jest i wynosi d, to dzielniki pierwsze d dają co najmniej taki sam wynik, więc można wziąć któryś z nich.
2) Prosta konsekwencja powyższego jest taka, że jeśli chcemy zebrać dwa wybrane kamienie, to skok musi być dzielnikiem pierwszym odległości między nimi.
Wystarczy więc dla każdego wylosowanego kamienia przeiterować się po wszystkich pozostałych i policzyć ile razy każda liczba pierwsza występuje jako dzielnik jakieś różnicy. Każda różnica może mieć maksymalnie 8 różnych dzielników pierwszych. Jak się dzielniki pierwsze preprocessuje to dla jednego kamienia można ten proces zrobić w O(m * 8).

No ale nie możemy za każdym razem losować nowych kamieni bo będzie q^2*(liczba losowań). Zamiast tego chcemy utrzymywać sobie zbiór A kamieni gwarantując że po i-tej operacji każdy kamień ma taką samą szansę bycia wybranym. Jak dostajemy nowy kamień to mu losujemy priorytet i naszym zbiorem jest zawsze A kamieni z najmniejszym priorytetem. Kameinie które nie są wybrane trzymamy na kolejce priorytetowej czy na czymś żeby móc łatwo wybrać nowy jak zostanie jakiś wybrany usunięty. Czyli po każdej operacji jest szansa A/m że wybierzemy nowy i wtedy musimy przeliczyć wynik dla niego w czasie O(m * 8). Ale w oczekiwaniu to jest po prostu O(A * 8). Dodatkowo jak dodajemy/usuwamy to musimy to dodać/odjąć wszystkim kandydatom, ale to też daje O(A * 8) na zapytanie. No i jeszcze mamy czynnik log(n) z utrzymywania kolejki, chociaż można to było robić bez niej. Całościowo O(q * A * 8).

Pominąłem kilka rzeczy, takich jak utrzymywanie maska dla każdego wylosowanego kamienia, ale to łatwiejsze części. Tylko limity są dość spore, więc dodatkowo trzeba na wszystko uważać. Na przykład nie mogłem trzymać 'ile razy dzielnik d występuje dla tego kandydata' na unordered_map. Zamiast tego musiałem skompresować wszystkie liczby pierwsze do 1,2,...K i potworzyć statyczne tablice żeby mi się w pamięci zmieściło. I jeszcze kilka innych takich spraw

My mamy deterministycznie. Pojawi się pewnie jutro rano ale tldr:

jak popatrzysz sobie na zbior wlaczonych pozycji a1,a2,…,am i na roznice elementow w odleglosc maks 2 lub 3 to kandydat na skok musi byc dzielnikiem O(m) z tych liczb

Mamy zatem juz O(1) dużych kandydatów na skoki. Jak kandydat staje się kandydatem to przeliczamy go w O(m). Jak kandydat przestaje być kandydatem, to i tak go zostawiamy i usuwamy go dopiero jak spadnie poniżej połowy progu na bycie kandydatem. W ten sposób po każdym updacie utrzymujemy O(1) kandydatów na skok, a te dodawania w O(m) się ładnie amortyzują.

:(

I to Ci wchodziło tak po prostu? Ja miałem spore problemy, w szczególności najważniejszym (dość szybkim i popularnym z tego co słyszałem) krokiem było rozważanie tak tylko liczb pierwszych większych niż pierwiastek sześcienny z n, żeby rozważać dwie liczby pierwsze zamiast ośmiu (a te mniejsze niż około 200 zrobić osobno). Pomimo to i tak wydawało mi się, że powinienem użyć clock(), żeby zrobić tyle powtórzeń ile zdążę i skrzyżować palce, bo bałem się po prostu zrobić ich np. czterdzieści.

Jeszcze nie wiem czy mi wchodzi, zakładam że nie na wszystkie punkty. Chociaż na uruchomieniach próbnych jeszcze się mieściłem. Powinienem nazwać temat "moje być może działające rozwiązanie" zamiast "rozwiązanie", sorry 😔

Ja się pochwalę obserwacją która bardzo mi się spodobała, na której oparłem swoje rozwiązanie:
Jeżeli para (liczba pierwsza, reszta) daje co najwyżej d/3 kamieni, gdzie d to aktualna liczba kamieni, to przez kolejne d/3 jednostek czasu na pewno nie będzie wybijać wyniku.

Czyli jak w jakimś momencie czasu znam wszystkie takie pary, które dają co najmniej jedną trzecią, to wystarczy mi jakiś czas utrzymywać county tylko dla nich. A jak ten czas minie to wyznaczam takich kandydatów od zera. Gdybym miał zrobić takiego rebuilda w czasie O(d) to wtedy takie rozwiązanie się pięknie amortyzuje do liniowki. Randomizowany rebuild w O(50d) działał mi jakieś absurdalne 40 sekund, chyba dlatego że dużo skakał po pamięci, więc musiałem go porzucić. Końcowo mam dwie wersje rebuilda, jedna dla małych d (<=100) w d^2 (nie jest oczywisty! korzystam z bardzo podobnej obserwacji co deterministyczna wzorcowka ale w jej słabszej wersji), druga dla dużych d w O(300+d*C), gdzie C to będzie liczba dużych liczb pierwszych (>n^1/3), które będą dzielić >=10 losowych par z 300 losowań - ciężko zrobić aby C to było więcej niż kilka.

Miałem podobną obserwację, choć trochę inną.

Zliczałem sumy prefiksowe, ile kamieni łącznie zostało dodanych (nawet jeśli potem zostały usunięte) w okresie 1..qi, co pozwala w czasie stałym określić wartość dla dowolnego przedziału [i..j].

Następnie jeśli najlepszy wyliczony wynik w chwili qi to a1_i, a następny - a2_i, to dla następnego j nie trzeba przeliczać wartości a2 dopóki a1_j > a2_i + łączna liczba kamieni dodanych w przedziale [i..j].

Weszło mi na 10 z prawie czterema sekundami zapasu. Niepotrzebnie mnie stresujecie chłopaki swoimi lepszymi rozwiązaniami :/

Może słabe testy ułożyliśmy 😭?

Myślę że nie lepsze niż Świstak ale nie uzasadnię tego głębiej 😇

A korciło mnie, żeby wziąć coś z tej jego paczki i wrzucić na sio, ale chyba nie wypada xddd
A tak na poważnie, dostałeś 10/wiesz o kimś, kto dostał za coś, co nie przechodziło Świstakowych?

Niee, ale trochę bałem się czasowo, najgorszy test Świstaka działał mi lokalnie ~6s (nie sprawdzałem na sio ale w innych zadaniach czasy lokalne i na sio miałem podobne), a na oficjalnych testach max czas był ~4.3s.