Hi,
I've sent submission 25136808 using a global anonymous struct with some big arrays and methods inside. The submission got RTE case 7.
Next, I send submission 25137642 only removing the struct from around the arrays and the methods, and I got AC.
Then I thought "maybe the global arrays are not being initialized to zero when they are inside the struct". So I called memset(&st,0,sizeof st); and I got RTE case 7 again: 25137670.
What's the deal with structs in Codeforces? All these 3 codes work fine I'm my notebook in test case 7.
UPD: I've just submitted the same 3 codes again, now with GNU C++14. The behavior is the same for all 3 codes.
UPD2: Now I've just submitted 25138080, only giving a name to the struct from the first submission and it got AC. So the problem is with anonymous structs??
UPD3: Seems like anonymous structs are not supported in C++ 11, after some Internet research...
How do you check? Test 7 is truncated when you view the submissions.
I print the input in Codeforces with
if (n == 1000). I have to print several times, several ranges... It's exhaustive =(That's clever.
As for the original question, I don't know. Have you tried a named struct type? Or using custom test?
So you have the whole test case. If the effect is reproducible in custom test, you can try to gradually simplify your program there, and so find the point when the effect vanishes. This will perhaps localize the problem, so that the source of the bug (in your program or elsewhere) becomes obvious.
I've just made a second update to the post. If I just put a name in the struct, the code gets AC! But a friend just told me that anonymous structs are not in the C++ 11 standard... That's probably the cause...
This is an unnamed class, not an anonymous one. See http://stackoverflow.com/a/14248127/4879303 for their differences. Unnamed classes are explicitly permitted in C++:
A class-specifier whose class-head omits the class-head-name defines an unnamed class.(§ 9.0.1, P231, n4618). Note thatclassandstructare the same in C++, except for the default permission.Would you please share the data for test 7 so others can try to reproduce this issue easier?
Sure! Here: http://pastebin.com/TiDmbkH7
The correct answer is 10.
It seems g++ didn't initialize the variable
stin the runtime error case. When compiling with a struct name, I can see:at the bottom, so
stis clearly initialized as expected, but without a struct name, there's no such thing, I cannot find wherestis initialized. Also the address printed at runtime has large difference.And what about the third submission, in which I call memset to initialize the variable st? Why does it get RTE?
In the assembly level, consider st as a pointer, if it's uninitialized, the memset was called to an invalid address.
Nice! That explains everything... Well, I wish I could get at least a compilation error for that...
And here is my guess for why the code works for small test cases (1 to 6). The label
stis present throughout the assembly, but not declared in the data segment. Then the assembler makesstequivalent to zero or some other initial offset in the data segment. With luck, some bytes after this offset are zero initialized and the code works for small test cases. But when it came to a big one, the bad actually happened. Is that it? Is this a good theory?If the issue is related to uninitialized
st. That's a reasonable explanation. (I can't be sure since I failed to find doesn't imply g++ couldn't initialize it somewhere and the assembly is obtained under linux which may differ from what we have under windows.)The difference between unnamed and named structure in this case is linkage. For unnamed type we have internal linkage and it allows compiler to do more optimizations.
Overall it looks like G++ optimizer bug, I've tried to play around with your code and minified it to:
http://mirror.codeforces.com/contest/319/submission/25139170
This one still gets RTE.