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.
EDIT: Reading this from the future, it seems apparent that this is unlikely to yield performance benefits.
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.