Блог пользователя AI_Avenger

Автор AI_Avenger, история, 5 лет назад, По-русски

Пытался решить задачу декартовым деревом и столкнулся с проблемой, после моего split изменялся root->size но хотя оно не должно. Можете пожалуйста пожалуйста помочь и указать на ошибку. Ссылка на мой код: https://ideone.com/6kVdIO. Задача 191E

UPD Решил просто исправить merge после split но теперь стал ловить тл. Как можно оптимайзить? Можете посоветовать хороший источник Декартки с++

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем AI_Avenger (предыдущая версия, новая версия, сравнить).

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Пиши хороший рандом, или делай вот так:

(rand()<<15) + rand();

UPD: обычный рандом генерирует числа до +-2^15 т.е. в промежутке от -32к до 32к

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int main() {
        cout << rand() << endl;
        return 0;
    }
    

    Мы с ребятами недавно выяснили, что поведения рандома зависит от операционной системы, в которой вы запускаете программу. Если вы попробуете запустить код выше в запуске Codeforces, то получите число 41 независимо от компилятора (под вижуалкой он не скомпилируется, но если его немного изменить, то там тоже будет 41).

    А вот в запуске на ideone все интереснее — там получается число $$$1804289383$$$, как и на моем линуксе. Поскольку этапы ICPC в основном тестируются под линуксом, то на этот недостаток рандома можно забить.

    Если вы не уверены, как ведет себя рандом в вашей тестирующей системе, то идейно более правильно использовать ((rand() << 15) ^ rand()) — так все биты в числе действительно получаются случайными, независимо от ОС. В случае со сложением это не работает из-за переноса $$$1$$$ через разряд.

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

После split должно изменяться root->size. Не осталось старой версии корня, есть только два новых дерева.

Нужно merge их обратно в root после split в строках 112-115. Либо делать дерево персистентным — вместо каждого изменения вершины создавать изменённую копию — но такое дерево требует больше памяти.