Today I was playing (never competing, please!) on a CodeChef programming contest and was dismayed when comparing my timings with some other competitors. Theirs were way shorter and I saw no way to improve my O(N) solution because I HAD to read an array of values. My processing was taking place while reading the data, using no loops only simple calculations.
Where was the problem… where… the I/O?
I was using the C Standard Library for I/O, scanf("%d", &var)
for reading numbers and printf("%d",var)
for writing. Those "%d"
needed to be parsed and THEN processed. Every time! So they surely were one of the culprits of my slight slowness.
My CodeChef timings using scanf() and printf() were around 0.65 seconds.
So I decided to write my own specialized I/O for the problems:
#include <stdio.h>
int getint()
{
int r = 0, i = 0;
int c;
for (;;) {
c = getchar();
if (c < 0) return i;
if (c >= '0' && c <= '9') {
if(!r) r = 1;
i = i * 10 + c - '0';
} else {
if (r) return i;
}
}
}
void putlonglong(long long v)
{
if (v > 9) {
putlonglong(v / 10);
}
putchar('0' + v % 10);
}
And now by timings improved considerably: 0.30 seconds!
But there are still some people doing it in 0.01 seconds! Man, what are they doing? Anything better than getchar()/putchar()? C++ streams?
Comments