Thomas_94's blog

By Thomas_94, 9 years ago, In English

Hello,

This submission (11309613) failed on test 20 for 548B - Mike and Fun but this one (11309695) made it (and now I'm green! ><).

I just moved scanf("%d", &t[i][j]), which usually works for booleans (despite the warning), into cin >> t[i][j].

Can someone explain me where am I doing wrong?

Thanks in advance.

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

»
9 years ago, # |
Rev. 3   Vote: I like it +15 Vote: I do not like it

despite the warning

Here is what is wrong. Compiler tells you that one's better not to scanf to bools with %d, because it expects pointer to int. It does not matter whether it usually works or not — C++ is not like Python, there is no reference implementation, the only thing you can rely on is the standard. A lot of things are undefined behavior, i.e. they can behave as you can expect and they can behave differently on other machines. Moreover, if your program have at least one undefined behavior, its whole behavior is undefined as well — it can crash in a random place, it can produce wrong answer, it can wipe your HDD out (however, this usually does not happen).

To the details: %d expects pointer to integer, and scanf has no way to know that you've passed pointer to bool instead. I'll explain my understanding of why could it work, but remember — it's still undefined behavior, never rely on it!

As we have little-endian architecture, writing four bytes (like 0x01 0x00 0x00 0x00, and here I assume that int is four-bytes long) to bool variable works well as long as we're not spoiling memory which immediately follows this bool. For example, if you have an array of bools, it will just zero three consecutive elements, which is not a big deal, as they already were zeros. However, on big tests you reach end of the array and somewhat important can follow that array. You're overriding something and your program starts behaving strangely — very alike array overflow.

You may wonder why cin works well then. Answer is easy: cin is a C++ thing (in contrast with scanf which came from C), >> is an overloaded operator, which is defined for plenty of types, including bool, so it has a very good idea about types and can behave accordingly. If it wasn't defined for bool, you'd probably get compilation error or some strange behavior because of type casts (well-defined, however).

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it -11 Vote: I do not like it

    Are you sure about the second paragraph? As far as I'm aware booleans are not stored in bits, this is because the smallest unit a memory address can point to is a byte (this saves log(8) = 3 bits in address pointers). When a boolean is false it is 00000000, and when it is true I thought it was 11111111, but it may very well be 00000001. (EDIT: More info here /EDIT)

    As for boolean arrays, I doubt the compiler optimizes this to a sequence of bits. I mean, that's the whole appeal of a bitset, that it uses 8 times fewer memory than a simple array of booleans: "The class emulates an array of bool elements, but optimized for space allocation: generally, each element occupies only one bit (which, on most systems, is eight times less than the smallest elemental type: char)."

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't understand your question. I'm not talking about bits anywhere. Would you mind clarifying?

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        Reading your post again it seems I misinterpreted it, I thought you suggested that writing a byte to the location of a boolean overwrites successive booleans, which would only make sense if you thought a boolean took up one bit of space (or less than a byte more generally). But I now see that you didn't say that at all (as you were talking about 4-byte integers) — my mistake!

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So what can I do if I want to scanf a bool var?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      You can scanf an integer variable and then assign that to the boolean variable.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      roll_no_1 is absolutely right: you don't. You scanf into int instead and then assign its value to bool.

»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

you could do something like this: scanf("%d",&tmp); t[i][j] = tmp;