Рейтинг

Сомневаюсь. Если даже в первом тесте было удаление пилонов, то в следующих наверняка встречалось бы оно и не раз. Да и если программа работает на добавление пилонов, в чём собственно говоря проблема дописать пару строк на удаление и изменение ситуации?

Martoon | 2011-12-18 20:30:22

Может быть были тесты (например некий max-тест), где ответ бы неким случайным образом совпал с правильным даже если игнорить удаление, или были специально сделаны тесты для решения с одним добавлением (как частичного решения). На олимпиаде я стал писать это так: заводил две кучи, одна для левой половины пилонов, другая для правой (в левой мы знали где пилон с максимальной координатой, в правой с минимальной). Когда состояние менялось, надо было просто добавить или удалить пилон из кучи, а затем уравнять их количество в кучах, перенеся один слева направо или справа налево. После того как я написал добавление пилона, стал думать над удалением и понял что за бред написал. Тут парой строк кода было не обойтись. Тогда я не подумал отправить написанное. Мне просто интересно, дало ли мне бы такое решение хоть какие-нибудь 10-15 баллов

ftc | 2011-12-18 22:43:03

Насколько я помню, мы не сделали специфичных тестов на только добавление, потому не думаю, что это решение набрало бы много. Вопрос в другом: что мешает написать кучу с возможностью удаления и перебалансировать её так же, как ты и написал. В результате получим как раз полное решение и 100 баллов :-)

Martoon | 2011-12-19 17:47:44

Чтобы написать удаление, нужно знать местоположение каждого элемента в куче, а значит пришлось бы перелопатить весь код дописывая обработку местоположений элементов, что я и попытался сделать, да вот не успел. Выходит, всё-таки не было смысла посылать то незавершённое решение, значит я буду спокоен :)

trueNikita | 2011-12-21 21:45:03

А что мешало вместо двух куч использовать два multiset'a? Более того, первое решение жюри было именно таким :)

Martoon | 2011-12-22 13:18:58

Пфф, и вправду. Так было бы куда проще

Ответить.

Версия для печати