This problem is to test how fast you are able to read the input. Faster input output methods are required for some problems in UVa, SPOJ, CodeChef and other sites (Usually the problem statements have a warning that the IO is huge).
What I found out about faster IO:
Never use cin or cout. Always use scanf and printf (they are about twice faster). But there are methods much much faster than scanf and printf!!
My first solution to the above problem: was using scanf and printf. -->Execution time: 5.44 s
Then I googled to find out this function to read integers using getchar:
inline void fastRead(int *a)
{
register char c=0;
while (c<33) c=getchar();
*a=0;
while (c>33)
{
*a=*a*10+c-'0';
c=getchar();
}
}I used it and my execution time became reduced by 2 seconds to 3.40 s I then stumbled upon UVa forum where someone suggested that getchar_unlocked is faster than getchar. So I modified the function to use getchar_unlocked:
inline void fastRead(int *a)
{
register char c=0;
while (c<33) c=getchar_unlocked();
*a=0;
while (c>33)
{
*a=*a*10+c-'0';
c=getchar_unlocked();
}
}
I submitted the program again with the getchar_unlocked modification and my execution time is now believe it or not: 0.76 s
Check this out: