LLI_E_P_JI_O_K's blog

By LLI_E_P_JI_O_K, 6 years ago, In Russian,

Обнаружил не так давно одну интересную проблему с компилятором Microsoft Visual C++ 2010.

Посылка № 4997092 на "acm.timus.ru" от 2 июня 2013 по задаче 1542 получает "Wrong Answer" на первом тесте на компиляторе Visual C++ 2010 и получает Accepted на всех версиях G++.

Я попытался выяснить, в чем проблема. В решении был фрагмент кода:

...
    for (int i=1; i<=k; i++) {
        sch[i] = find_max(a,b);
        update(sch[i], -1);
    }
...

где функции find_max() и update() — для работы с деревом максимумов. С таким фрагментом — "Wrong Answer 1" (на Visual C++ 2010).

Однако! Если добавить никогда не выполняющийся "if" или просто сделать какое-либо действие с sch[i], то получается "Accepted":

...
        for (int i=1; i<=k; i++) {
            sch[i] = find_max(a,b);
            
            if (sch[i] < 0)
               printf("ha-ha-ha"); // if никогда не выполнится (а если бы выполнился,
                                   // то тогда всё равно WA должно быть, а не AC) 
            
            update(sch[i], -1);
        }
...

См. посылку № 4997093 от того же числа.

Как это объяснить? В голову приходит только мысль о том, что оптимизатор Microsoft Visual C++ 2010 просто подсчитал один раз значение функции find_max(a,b) и использовал в дальнейшем его, не вызывая функцию на последующих итерациях цикла, что является неверным, т.к. find_max(a,b) использует дерево tree, изменяющееся в вызовах update(sch[i], -1).

Может быть, есть возможность изменить параметры компиляции, чтобы такого не происходило?

Примечание 1: в ключах компиляции стоит 2-й уровень оптимизации, даже не 3-й. Вроде бы не должно тогда такого происходить.

Примечание 2: на Codeforces такая ошибка тоже проявляется.

 
 
 
 
  • Vote: I like it
  • +36
  • Vote: I do not like it