Всем привет) У меня возник вопрос, каким образом лучше выбрать приоритет в декартовом дереве, после задачи, которая падала по времени на 12 тесте, где приоритет выбирался по такой формуле:
ll prior = (rand() << 15) ^ (rand() << 15);
Задача зашла, когда приоритет считался вот так, без какого либо рандома)
const ll M = 10000000001230000000; prior = (x << 16) ^ (M*x);
После решения еще одной задачи, получилось наоборот, вторая формула давала тл, а первая зашла. Хотелось бы посмотреть как вы решаете проблему с приоритетами)
ll prior = (rand() << 16)|(rand());
По моим замерам, работает в четыре-пять раз быстрее
rand.изучайте C++ STL, там все написано
генерирует сразу 64-битные числа, работает быстрее
rand()Интересно узнать, у человека падало из-за того что рандом плохой (дерево плохо балансировалось), или слишком медленный. Мне, например, не понятно к чему такая "криптоустойчивость". Вариант выше от SirNickolas кажется намного быстрее.
дело не в криптоустойчивости, а в том что это единственный стандартный гсч в
<random>, который выдает 64-битные числа. Судя по тестам в запуске, он выдает 107 чисел за 120 мс, т.ч. не вижу никаких проблем со скоростью.Если хочется именно линейный конгруэнтный гсч, то можно либо использовать стандартные 32-битные реализации (
minstd_rand,minstd_rand0), либо написать что-нибудь свое как-то так:(должно выводить такие же числа как код SirNickolas, не считая signed integer overflow)
Проблема в том, что не все тестирующие системы принимают mt19937_64.
Проблема не во времени работы rand(), а в том, что написана какая-то ерунда — зачем оба rand() сдвигать на 15 и ксорить? Если тестирование под виндой, то у вас получается 32 тысячи различных приоритетов, декартово дерево будет бамбучить или вообще циклиться. Если под линуксом, то тоже странная конструкция — можно пользоваться обычным rand(). Ну или любым из вариантов, уже предложенных выше.
А можно немного подробнее, как такое бывает?
Нужно сдвигать только один из rand().
p.s всегда пишу rand() ^ (rand() << 15)
Тоже не самая надёжная конструкция. rand() возвращает int, а при сдвиге на 15 это может уже не влезать в int. Это undefined behavior
rand() возвращает числа в диапазоне от 0 до 2^15 — 1, так что можно.
Хотя это зависит от константы RAND_MAX, но вроде по умолчанию она 2^15 — 1.
У меня локально (linux) RAND_MAX = 2^31 — 1. На Windows может быть действительно он 2^15 — 1, но полагаться на это явно не стоит.
Ну если так, тогда можно юзать просто rand() без всяких сдвигов.
Можно. Но это опять неуниверсальное решение и его работоспособность зависит от константы RAND_MAX, которая в разных местах разная. Лучше будет использовать генераторы с фиксированной битностью (например, mt19937), либо правильно кастовать к unsigned/long long, чтобы не происходило UB.
Если говорить о более универсальных решениях, то можно (если писать на массиве, а не на указателях) присвоить всем ячейкам их порядковый номер, а затем пошафлить. К тому же, вместо лонл лонгов будут инты.
А каким рандом шаффлить?
Мне лень искать, но тут была статья, что стандартный рандом шаффлит также плохо (по тем же самым причинам) и примерно так написанная декартка не заходила.
Можно написать взять любой хороший рандом и сделать свой random_shuffle.
Другой способ заключается в использовании shuffle. http://www.cplusplus.com/reference/algorithm/shuffle/
Но честно, я не сталкивался с такими случаями, когда стандартный random_shuffle давал TL.
Нашел: https://codeforces.net/blog/entry/17132