Hello, Codeforces.
I've sent three submissions with different compilers on problem 1553E - Permutation Shift from last round and got different results(OK, ML 1, WA 1)
Then i've ran valgrind (g++ 11.1.0) and discovered strange "still reachable" memory addresses, somehow connected with ios_base::sync_with_stdio. Then I realised, that fast IO was in solve function, which is called in main $$$T$$$ times for each test case. Then I moved it to main and got OK in all compilers.
valgrind output on sample
==36581==
==36581== HEAP SUMMARY:
==36581== in use at exit: 122,880 bytes in 6 blocks
==36581== total heap usage: 120 allocs, 114 frees, 197,964 bytes allocated
==36581==
==36581== 8,192 bytes in 1 blocks are still reachable in loss record 1 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4982194: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4982194: std::basic_filebuf<char, std::char_traits<char> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x497FEBA: __gnu_cxx::stdio_filebuf<char, std::char_traits<char> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E6A2: std::ios_base::sync_with_stdio(bool) (ios_init.cc:181)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== 8,192 bytes in 1 blocks are still reachable in loss record 2 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4982194: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4982194: std::basic_filebuf<char, std::char_traits<char> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x497FEBA: __gnu_cxx::stdio_filebuf<char, std::char_traits<char> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E6C6: std::ios_base::sync_with_stdio(bool) (ios_init.cc:182)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== 8,192 bytes in 1 blocks are still reachable in loss record 3 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4982194: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4982194: std::basic_filebuf<char, std::char_traits<char> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x497FEBA: __gnu_cxx::stdio_filebuf<char, std::char_traits<char> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E6EA: std::ios_base::sync_with_stdio(bool) (ios_init.cc:183)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== 32,768 bytes in 1 blocks are still reachable in loss record 4 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4983F47: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4983F47: std::basic_filebuf<wchar_t, std::char_traits<wchar_t> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x49800BA: __gnu_cxx::stdio_filebuf<wchar_t, std::char_traits<wchar_t> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E757: std::ios_base::sync_with_stdio(bool) (ios_init.cc:190)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== 32,768 bytes in 1 blocks are still reachable in loss record 5 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4983F47: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4983F47: std::basic_filebuf<wchar_t, std::char_traits<wchar_t> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x49800BA: __gnu_cxx::stdio_filebuf<wchar_t, std::char_traits<wchar_t> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E77B: std::ios_base::sync_with_stdio(bool) (ios_init.cc:191)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== 32,768 bytes in 1 blocks are still reachable in loss record 6 of 6
==36581== at 0x484021F: operator new[](unsigned long) (vg_replace_malloc.c:579)
==36581== by 0x4983F47: _M_allocate_internal_buffer (fstream.tcc:56)
==36581== by 0x4983F47: std::basic_filebuf<wchar_t, std::char_traits<wchar_t> >::_M_allocate_internal_buffer() (fstream.tcc:49)
==36581== by 0x49800BA: __gnu_cxx::stdio_filebuf<wchar_t, std::char_traits<wchar_t> >::stdio_filebuf(_IO_FILE*, std::_Ios_Openmode, unsigned long) (stdio_filebuf.h:161)
==36581== by 0x492E79F: std::ios_base::sync_with_stdio(bool) (ios_init.cc:192)
==36581== by 0x109410: solve() (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581== by 0x109AB8: main (in /home/thematdev/AlgoProgs/tinkoffgeneration2020/tmp/HarbourSpaceScholarship/problemE/a.out)
==36581==
==36581== LEAK SUMMARY:
==36581== definitely lost: 0 bytes in 0 blocks
==36581== indirectly lost: 0 bytes in 0 blocks
==36581== possibly lost: 0 bytes in 0 blocks
==36581== still reachable: 122,880 bytes in 6 blocks
==36581== suppressed: 0 bytes in 0 blocks
==36581==
==36581== For lists of detected and suppressed errors, rerun with: -s
==36581== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
Pretty strange and interesting situation, so I am asking those, who know what's the problem to write about it in comments. Also I am glad to see critics of my code, especially if it will help to avoid situations like this.
The results are indeed very strange. However, the cppreference page for
sync_with_stdio
mentions the following:In this case, the read buffer is probably destroyed in the GCC implementation (and somehow not in the MSVC one). As a result, the variables
n
andm
don't get initialized properly from the callcin >> ...
, and things go awry from there. Moreover, if you check the error flags incin
after unsyncing with stdio and then reading more input, you would find thatcin.good()
becomes false, whereascin.eof()
andcin.fail()
become true. It means EOF is reached, so the buffered input from early is really gone. (See the reference page forbasic_istream
for more info.)This is an implementation-defined territory, and I guess it's not that far from undefined behavior (which is a main source for common bugs in programming), so it might be a good idea to try to avoid dealing with these territories.