caustique's blog

By caustique, 9 years ago, In Russian,
Получил в задаче B 66 CFBR Time Limit на 9 тесте.
Сразу скажу, что у меня, возможно, не самое оптимальное решение, потому что я юзаю multiset <int> и прочие стандартные контейнеры, например vector <pair <int, string> >, хотя если убрать последний, ничего не меняется.

В дорешке переделал считывание и все сократил по минимуму - не помогло.

Посмотрел решения других участников и обнаружил у hos.lyric такое же решение, как у меня, за исключением того, что он использовал container.lower_bound(value), а я lower_bound(contaner.begin(), container.end(), value).

Его решение работает на 9 тесте 0.7 с., а мое не влезает в 4.
После переделки, решение заработало на том же тесте за 0.25 с.

Я в шоке.
Всегда думал, что эти стандартные алгоритмы эквивалентны.
Оказывается, нет?
Кто какие еще подводные камни знает в STL?
 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it