На прошлом опенкапе нам "посчастливилось" обнаружить в g++ новую багу (тут предыдущая бага, которая недавно обсуждалась здесь).
Бага проявляется в сложных рекурсивных функциях при включенной оптимизации -O2.
В нашем случае это было дерево отрезков, и приводило это к неверному ответу даже на семпле (хотя без -O2 всё работает). Ещё интересным было то, что если пытаться добавить дебаг-вывод (с cout/cerr/printf) - то всё начинало работать верно :) Конечно, сами по себе эти признаки могут означать, что это кривое решение, но, по всей видимости, это не так.
В общем, после контеста минимизация нашего дерева отрезков привела к такой минимальной программе: на pastebin.
По дебаг-выводам видно, что при включении -O2 функция auxillary() вызывается два раза, один раз возвращая единицу, другой раз - ноль, а query() в итоге возвращает ноль, хотя её результат получается как сумма результатов auxillary().
Впрочем, в баг-трекере другой человек сумел сделать гораздо более простой пример: на pastebin.
Ссылка на баг здесь: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=48837.
В данный момент этот баг подтверждён, а также подтверждено, что он проявляется на (!внимание!) g++ 4.3.3 - 4.6.0.
Т.е. все версии GCC за последние 2.5 года. Мда...
P.S. С подобным странным поведением решений на g++ мы сталкивались давно, но обычно как-то не придавали значения - ну, наверное, решение кривое; прошло на вижаке - и слава богу. Оказалось, что не всё так просто, и, значит, в голове надо держать ещё один фактор - кривость компилятора.
P.P.S. А на финале будет тот же g++...
People from bugtracker say that the following compiler option fixes the problem:
-fno-optimize-sibling-calls
I think it would be fair to add this option on the codeforces (btw, the previous bug with -fno-strict-aliasing option was not specified for C++ 0x compiler).
Also it turned out that we can fool the optimizer using complex enough expression, such as:
int ans = ans1 + ans2;
if (ans1 & 1)
ans = ans2 + ans1 % 2 * ans1;
Two these expressions are not equivalent (when ans1<0), but in our program all numbers were non-negative.
Our solution with this hack gives OK in the upsolving...
Всё думаю о переходе на вижак. Там я о багах в компиляторе не слышал. С другой стороны, на IOI будет g++...
А долго ты искал это на той олимпиаде? Когда мы первый раз послали задачу и получили WA#1, у нас оставалось 25 минут до конца. Прогнали еще раз семпл, убедились, что на нем все работает - ну значит там первый тест не семпл. Отложили задачу, я отсел читать код - так ничего и не нашел до конца контеста. А подозревать, что что-то тут не так, мы начали только в самом конце, когда послали printf(<ответ на семпл>) и получили WA#2.
Да, assert действительно помогает. Кстати, в вижаке по умолчанию в релизе assert не работает, поэтому вместо него надо писать if (...) throw.
#ifndef DEBUG
#undef assert
#define assert(...)
#endif
Поэтому словив RTE на первом тесте мы удивились. Что любопытно, это уже второй случай magic assert в моей жизни - поэтому и нашли быстро. Когда был первый - увы, не помню.
Но тем не менее, баги g++ гораздо суровей ) Достаточно погуглить по форуму топкодера, там такие вещи попадаются, что аж глаза на лоб лезут (типа неверной работы abs()).
В MS Compiler - по крайней мере, из того, о чем я слышал - баги концентрируются вокруг сложных иерархий классов, сложных шаблонов, и т.д. На контестах мне вообще ещё не встречалось такой ситуации, чтобы под вижаком задача не проходила (я имею в виду, странные wa/re), а под g++ - проходила.
Нет, это:
http://apps.topcoder.com/forums/?module=Thread&threadID=595322&start=0
Ну наверное она совпадает с этой багой? Я думаю, что наверняка да.
Попробуй найди ту прогу, и включи эту опцию компилятора. Или сделай финт с бессмысленными операциями, как во 2-ом комменте.