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

Автор clueless_girrafe, история, 9 месяцев назад, По-английски

Weird non-determinism in 2197E1 (Interactive Graph)

While solving 2197E1 (Interactive Graph – Simple Version) in the recent Div 2, I ran into something really confusing, the same logic gave both AC and WA depending on tiny, irrelevant code changes.

I had multiple submissions within minutes:

Some Accepted, some WA on test 8 / 9 / 20 / 21 / 22 / 23

No logic changes. Same idea. Same queries.

The strangest example

This version ACs:

if (q == -1) { return; }

This version WAs:

if (q == -2) { return; } Logically, if I'm getting accepted, both branches are dead code.

Either the checker is non deterministic or there's some UB shenanigans going on.

Links to submissions

362583126 WA

362583031 AC

Darsh_Jain also tried testing it, and the following two submissions

362582232 WA

362581962 AC

And the difference between the two is only that we have added a comment in the first one!

FelixArg and sevlll777 pls help

EDIT: It was indeed UB :(, fixed now. PS: Always use #define _GLIBCXX_DEBUG kids.

  • Проголосовать: нравится
  • +23
  • Проголосовать: не нравится

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by clueless_girrafe (previous revision, new revision, compare).

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

The 2nd case is a dead case, but I don't think the 1st case is, since -1 is returned in case you exceed the number of permitted queries, and you get wrong answer if you keep querying after getting -1.

But still you should have gotten WA as you are returning on -1.

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by clueless_girrafe (previous revision, new revision, compare).

»
9 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

#define _GLIBCXX_DEBUG

What's the meaning of this?