Необходимо реализовать максимально быстрый алгоритм сортировки битового массива (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, кэширование)