Реализация декартовых деревьев

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

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

Я попытался сдать задачу декартовыми деревьями, и получил TLE10. Также оно еле укладывается в TL по задаче D отсюда: http://codeforces.com/gym/100093 (а если все приоритеты брать по mod1000, то оно ловит TLE15) и проваливает F.

Допустил ли я где-то ошибку, или ни одна из этих задач не должна сдаваться декартовыми деревьями?

Посылки:

Задача D из тренировок

Задача F из тренировок

По неведомой причине залетевшее решение F

SPOJ

(В процессе написания у меня почему-то зашла F, но поскольку это случилось 1 раз из 4, этим, видимо, стоит пренебречь).

HUECTRUM1
7 лет назад
10

Комментарии (10)

Написать комментарий?

dalex

7 лет назад, # |

rand() вроде возвращает 15-битное число, попробуй (rand() << 15) | rand() вместо этого

→ Ответить

yeputons

7 лет назад, # ^ |

+13

А ещё лучше — (rand() << 16) ^ rand() (основное — ^ вместо |), тогда будет генерировать случайные числа независимо от того, 16 бит выдаёт или больше.

→ Ответить

tyamgin

7 лет назад, # ^ |

← Rev. 2 →

Тогда уже без UB ((unsigned)rand() << 16) ^ rand() и хранить в unsigned

http://ideone.com/dPcCUi

→ Ответить

riadwaw

7 лет назад, # ^ |

← Rev. 2 →

+39

или таки начать использовать то, что заведомо нормально работает

std::uniform_int_distribution<>([l,r если надо])(gen);

→ Ответить

Zlobober

7 лет назад, # ^ |

← Rev. 2 →

+13

Кто-нибудь, замутите пикчу наподобие этой вида:


srand(42);                                       | // чёткая 
int y = (rand() << 16) ^ rand();                 | // аватарка
                                                 | // yeputons
==================================================================
                                                 | // размазанная 
std::random_device rd;                           | // аватарка 
std::mt19937 gen(rd());                          | // AlexDmitriev типа  
std::uniform_int_distribution<> dis(0, 1 << 30); | // многобукоф ни  
int y = dis(gen);                                | // о чём

→ Ответить

AlexanderBolshakov

7 лет назад, # ^ |

std::mt19937 gen(69);
int y = gen();

Для декартова дерева мне норм.

→ Ответить

Zlobober

7 лет назад, # ^ |

← Rev. 2 →

Так да, норм.

Я всего-лишь придрался к std::uniform_int_distribution<>, которым, кажется, можно подпирать потолок, если положить на бок.

→ Ответить

riadwaw

7 лет назад, # ^ |

← Rev. 2 →

ну если честно сравнивать, то первая строчка не нужна и просидировать можно напрямую.

→ Ответить

xsc

7 лет назад, # |

Задача F solution Проблема не только в рандом, лучше не используй std::cin, std::cout , even sync_with_stdio(false). Лучше используй printf/scanf Твое решение почти идентичен с моим, кроме метод чтение/запись.

→ Ответить