5
\$\begingroup\$

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?

\$\endgroup\$
0

2 Answers 2

4
\$\begingroup\$

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]);
}
\$\endgroup\$
3
  • \$\begingroup\$ Why does changing double to unsigned long long speed up the program (after I made these modifications I got AC)? Thanks for the answer! \$\endgroup\$
    – manan
    Jan 22, 2015 at 5:37
  • \$\begingroup\$ 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. \$\endgroup\$
    – AndersK
    Jan 22, 2015 at 5:39
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – mjolka
    Jan 22, 2015 at 5:41
1
\$\begingroup\$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.