Wskaźnik w secie - Zadanie Agar.io - 3 Etap OIJ

Question

Cześć,

Wczoraj pisałem 3 etap OIJ. Nie udało mi się zrobić na 100 pkt zadania Agar.io:

Gra agar.io (swego czasu dość popularna w sieci) jest rozgrywana w przeglądarce internetowej. Każdy z obecnych na serwerze graczy steruje pojedynczą komórką o pewnej masie. Kiedy spotyka komórkę o masie mniejszej niż swoja, wchłania ją, powiększając swoją masę o masę drugiej komórki. Kiedy jednak spotka komórkę o masie większej lub równej swojej, natychmiast przegrywa. Bajtek połączył się właśnie z serwerem gry i jego komórka ma niezbyt imponującą masę 2. Bardzo chciałby jednak wygrać, czyli zostać najwiekszą komórką na tym serwerze. Dzięki niebywałym umiejętnościom hakerskim udało mu się zablokować możliwość poruszania się innych graczy – czyli jest w stanie swobodnie wybierać kolejne ofiary do wchłonięcia, a inni gracze nie mogą uniknąć spotkania. Ta miła sytuacja nie potrwa jednak długo i administratorzy serwera niebawem cofną blokady Bajtka. Bajtek jest w stanie wchłonąć swoją komórką inną komórkę w czasie jednej sekundy. Ile sekund będzie potrzebował, aby stać się największą komórką na serwerze? Bajtek zadowoli się ewentualnym remisem z innymi największymi komórkami. Napisz program, który na podstawie masy komórek kontrolowanych przez przeciwników Bajtka na serwerze gry, wyznaczy minimalny czas potrzebny Bajtkowi aby stać się największą komórką w grze. Przypominamy, że komórka Bajtka zaczyna z masą równą 2.

Wejście:

7

1 2 2 10 5 12 1

Wyjście: 4

Mi udało się jedynie je zrobić na 60 pkt - (Sortując masy i w O(n^2) sprawdzając jaką największą mogę zjeść.)

Jednak mój pomysł był taki, żeby trzymać te masy na secie i w O(log n) znajdywać ostatnią < niż masa bajtka i ją jeść wtedy O(n log n). Jednak nie umiem zrobić binary seracha na secie. Więc wiecie może jak mogę odwołać się np. za pomocą wskaźników do jakiegoś elementu w secie(wtedy mogę zrobić binary searcha), lub jak napisać funkcję, która znajdzie mi liczbę ostatnią < niż x?

PS - wiem, że w secie nie ma idx-ów.

Z góry dziękuję za pomoc!

Answer 1

Set ma wbudowaną funkcję lower_bound, która robi mniej więcej to czego potrzebujesz. Tylko ona znajdzie element większy/równy, więc trzeba cofnąć się do poprzedniego elementu, żeby znaleźć mniejszy

Comments

Dzięki!, szkoda że nie znalazłem tego w dokumentacji podczas zawodów ale trudno.