# Timus Online Judge Problem 1001 - "Reverse Root"

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?

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]);
}

• Why does changing double to unsigned long long speed up the program (after I made these modifications I got AC)? Thanks for the answer! Jan 22, 2015 at 5:37
• 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. Jan 22, 2015 at 5:39
• @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. Jan 22, 2015 at 5:41

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...)

• 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. Jan 22, 2015 at 5:40
• It is a bad habit. The sooner you drop it, the better.
– vnp
Jan 22, 2015 at 6:02