Timus Online Judge Problem 1001 - "Reverse Root"

Question

The problem statement can be found here.

Description (short):

Input

The input stream contains a set of integer numbers \$A_i\$ (\0ドル \le A_i \le 10^{18}\$). The numbers are separated by any number of spaces and line breaks. A size of the input stream does not exceed 256 KB.

Output

For each number \$A_i\$ from the last one until the first one, you should output its square root. Each square root should be printed in a separate line with at least four digits after the decimal point.

#include <iostream>
#include <iomanip>
#include <math.h>
using namespace std;
int main()
{
 double t;
 double v [128 * 1024];
 int idx = 0;
 while (cin >> t) {
 v[idx] = sqrt(t);
 ++idx;
 }
 cout << fixed;
 cout << setprecision(4);
 for (int i = idx - 1; i >= 0; --i)
 cout << v[i] << endl;
 return 0;
}

I am encountering a TLE on test case 9, with an execution time of 2.031s and memory usage of 1 474 KB. (The allowable limits are 2.0s and 64 MB.) How can I improve (or change) my method to complete the problem successfully?

Answer 1

The input stream contains a set of integer numbers \$A_i\$ (\0ドル \leq A_i \leq 10^{18}\$).

So you should change

double t;

to

unsigned long long t;

This actually speeds up the program a lot.

---

To speed up the output, instead of

cout << fixed;
cout << setprecision(4);
for (int i = idx - 1; i >= 0; --i)
 cout << v[i] << endl;

Try

for (int i = idx - 1; i >= 0; --i) {
 printf("%.4f\n", v[i]);
}

• manan: Why does changing double to unsigned long long speed up the program (after I made these modifications I got AC)? Thanks for the answer!
• AndersK: well the question was marked C++ so recommending printf seems not right. instead maybe one should turn on buffering of output of cout if printing speed is a problem.
• mjolka: @manan I would guess it's because for double it will correctly parse things like 1e5, and so is more complicated. I don't really know C++ though, perhaps someone else can chime in.

Answer 2

Some cycles might be shaved off by making v global, and/or replacing index increment/decrement with a pointer increment/decrement. For a smart compiler with necessary optimization turned on it would make no difference; do you know how do they compile the submissions?

As for the review, the code is OK except

• using namespace std, which is not OK.

• Possible buffer overflow when number of integers exceeds \2ドル^{18}\$ (I know they promised, but for code review it is a red flag)

• Misbehaving on a malformed input (see above...)

• manan: Thanks! Is using namespace std generally not ok, or is it acceptable for contest programming? I read the linked answer and it seemed to be discussing larger programs where serious maintenance would be necessary.
• vnp: It is a bad habit. The sooner you drop it, the better.