Musisz zaimplementować maksymalnie szybki algorytm sortowania tablicy bitowej (0 i 1) z możliwością 100% odwrotnego odtworzenia.
Istota zadania:
Mamy tablicę z 0 i 1 (do 8 MB)
Musisz posortować: wszystkie 1 po lewej, wszystkie 0 po prawej → "111...000"
Ale bez utraty oryginalnej kolejności:
to znaczy, że musisz zachować tylko rangę permutacji, a nie pełną listę pozycji
Kluczowe wymagania:
Bez przechowywania listy pozycji 1
Tylko rank (unikalny numer permutacji)
Rank musi być przekształcony w krótki seed (na przykład 60 znaków)
Musisz mieć możliwość odtworzenia pełnego początkowego porządku z seed + N + K
Jeśli możesz zaimplementować funkcję odwrotną unrank() — to plus
Można używać GMP, OpenMP, SIMD itp.
Wymagane umiejętności:
Doskonała znajomość C lub C++
Doświadczenie z algorytmami rangowania, kombinacjami, permutacjami
Znajomość kombinatoryki (C(n, k)) w praktyce
Doświadczenie w pracy z dużymi liczbami (__int128, GMP lub Boost)
Optymalizacja wydajności (wielowątkowość, SIMD, buforowanie)