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

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