I’ve stumbled upon UVa10055 Hashmat The Brave Warrior just now.

Now, don’t get me wrong. It’s a simple question, but

  • seeing the AC count on my UVa account increase is blissful, and
  • I wanted to find faster ways to solve it.

My first submission is basically the following (forgot to optimize iostream though):

#include <iostream>

int main() {
  long long a, b;
  while (std::cin >> a >> b) {
    std::cout << ((a > b) ? (a - b) : (b - a)) << "\n";
  }
}

The execution time was 0.280 seconds, which wasn’t so great. Since the maximum input was 2^32 (literally UINT_MAX + 1 on most platforms), using long long on it seemed to be a waste, especially when I didn’t know if the server was 32-bit or 64-bit.

Anyway, I wrote the following:

#include <iostream>

int main() {
  // iostream optimize
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);
  unsigned int a, b;
  // Cin first so we could call cin.eof() later
  std::cin >> a;
  while (!std::cin.eof()) {
    unsigned int ans;
    if (std::cin.fail()) {
      // If overflow ( a == pow(2, 32) )
      std::cin.clear();
      std::cin >> b;
      if (std::cin.fail()) {
        // If ( a == b == pow(2, 32) )
        std::cin.clear();
        std::cout << "0";
      } else if (b == 0) {
        std::cout << "4294967296";
      } else {
        // Underflow on purpose to get (2^32 - b)
        std::cout << -b;
      }
    } else {
      std::cin >> b;
      if (std::cin.fail()) {
        // If ( b == pow(2, 32) )
        std::cin.clear();
        if (a == 0) {
          std::cout << "4294967296";
        } else {
          // Underflow on purpose
          std::cout << -a;
        }
      } else {
        std::cout << ((a > b) ? (a - b) : (b - a));
      }
    }
    std::cout << "\n";
    std::cin >> a;
  }
}

And got a time of 0.020 seconds. Now, I wondered what results I’ll get if I went back to long long, keeping the iostream optimizations.

#include <iostream>

int main() {
  std::cin.tie(0);
  std::ios_base::sync_with_stdio(0);
  long long a, b;
  while (std::cin >> a >> b) {
    std::cout << ((a > b) ? (a - b) : (b - a)) << "\n";
  }
}

And the time was STILL 0.020. Turned out that it didn’t make a big difference.

Anyway, I might dig out the extremely optimized version of input and atoi that I wrote some time ago, and give that a try in the future.