Потрібно реалізувати максимально швидкий алгоритм сортування бітового масиву (0 і 1) з можливістю 100% зворотного відновлення.
Суть завдання:
Маємо масив із 0 і 1 (до 8 МБ)
Потрібно відсортувати: всі 1 зліва, всі 0 справа → "111...000"
Але без втрати оригінального порядку:
тобто потрібно зберегти лише ранг перестановки, а не повний список позицій
Ключові вимоги:
Без збереження списку позицій 1
Тільки rank (унікальний номер перестановки)
Rank має бути перетворений у короткий seed (наприклад, 60 символів)
Має бути можливість відновити повний початковий порядок з seed + N + K
Якщо можеш реалізувати зворотну функцію unrank() — це плюс
Можна використовувати GMP, OpenMP, SIMD тощо
Необхідні навички:
Відмінне знання C або C++
Досвід з алгоритмами ранжування, комбінаціями, перестановками
Знання комбінаторики (C(n, k)) на практиці
Досвід роботи з великими числами (__int128, GMP або Boost)
Оптимізація продуктивності (мультипоточність, SIMD, кешування)