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

Автор Thomas_94, 10 лет назад, По-английски

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.

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

»
10 лет назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

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).

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится -11 Проголосовать: не нравится

    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)."

    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        10 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        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!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
10 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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