2

I got a homework which goes through a compiler which checks if all is correct but it keeps giving result : "time limit exceeded" , the application works as it should in normal C++ compiler but I have to send the code to Themis which doesn't accept it due to "time limit exceeded"

Task : Input: In the first input line is given the integer t (1 ≤ t ≤ 100000) specifying the number of tests. Each test is given by three integers: a, b, m as defined above (1 ≤ a ≤ 10^9, 0 ≤ b ≤ 10^9, 1 ≤ m ≤ 10^6).

Output:

T lines should be printed. In each line, the answer to the query: (a^b)% m.

example of input data:

2
3 2 10

the correct answer is : 9

One friend told me to change cout to printf which might result in faster runtime but I'm not sure how to do it.

My code 

#include <iostream>

using namespace std;

int main()
{
    int t;
    cin>>t;

    for (int i=0; i<t; ++i)
    {
        int a,b,m;
        long long int x,wynik=1;

        cin>>a>>b>>m;

        x=(long long int) a;

        do
        {
            x%=(long long int)m;
            if (b&1) {
                wynik*=x;
                wynik%=(long long int)m;
            }
            x*=x;
        } while (b>>=1);

        cout <<wynik<<endl;;
    }

    return 0;
}
Alan Birtles
  • 32,622
  • 4
  • 31
  • 60
Roksana
  • 31
  • 5
  • 4
    *but i keep failling because of too long compiling (over 1 second)* -- What do you mean by "takes 1 second to compile"? Do you really mean that your program takes more than 1 second to *run*? – PaulMcKenzie Mar 03 '20 at 21:31
  • 4
    If it's really failing because *compilation* takes too long, you should complain to your instructor. Your program is very simple and it's not your fault if their test machine is too slow. – Nate Eldredge Mar 03 '20 at 21:33
  • 2
    Do you need to perform `a RAISED TO THE POWER OF b`, or `a XOR b`? – JohnFilleau Mar 03 '20 at 21:34
  • This doesn't address the question, but none of the three casts (`(long long int)`) is needed. – Pete Becker Mar 03 '20 at 21:35
  • Also, changing your `endl` to `'\n'` will improve run times (note: compilation is NOT the same as running. You're busting run time, not compilation time) – JohnFilleau Mar 03 '20 at 21:36
  • @John \n would have the same effect with stdout (typically it's line-buffered). – Igor R. Mar 03 '20 at 21:41
  • The error which is shown says : time limit exceeded in normal c++ compiler the code is correct but I have to Submit solution in Themis which gives such problems – Roksana Mar 03 '20 at 21:41
  • @Igor I didn't realize that. My mistake – JohnFilleau Mar 03 '20 at 21:42
  • 1
    I'd recommend using [`std::pow`](https://en.cppreference.com/w/cpp/numeric/math/pow) instead of implementing exponentiation yourself. (That will also likely give a significant performance boost.) – 0x5453 Mar 03 '20 at 21:43
  • @Roksana I think it's just a bad error message. There's no way this code takes over a second to compile unless the hardware is bad. Using printf over cout is not going to meaningfully speed up compilation times. – JohnFilleau Mar 03 '20 at 21:43
  • @Roksana *time limit exceeded* - -Which means that your code takes too long. And to be honest, playing around with `cout` statements as opposed to `printf` does little, if anything, in increasing your knowledge of C++. If you can't drive a car, picking a blue car instead of a red car isn't going to teach you how to drive a car. – PaulMcKenzie Mar 03 '20 at 21:49
  • I'm sorry for the mistyping with "too long compiling" instead of "runs too much time" I got C++ this semester so I'm also quite new to it. – Roksana Mar 03 '20 at 21:52
  • you can still edit your title and question here: https://stackoverflow.com/posts/60515807/edit – 463035818_is_not_an_ai Mar 03 '20 at 21:57
  • 8
    Are you sure your input and expected output is correct? `2 3 2 10` will hang, because the first `2` means that the application wants 2 sets of a/b/m, but there is only one. When I run your application with `1 3 2 10` it runs in 4ms. I'm guessing your application is taking too long because it is waiting for the second set of a/b/m – lxop Mar 03 '20 at 21:57
  • 3
    @0x5453 Reminder: `std::pow` is a floating point function and there may be some accuracy issues when converting to integers. – Thomas Matthews Mar 03 '20 at 22:19
  • Is it possible one of the test cases is introducing an overflow situation, thus breaking the normal loop? – Kenny Ostrom Mar 03 '20 at 22:38
  • 2
    @0x5453 Wrong, the `pow` function doesn't really calculate "`a` to the power of `b` **modulo `c`**". For almost any value `b`, catastrophic loss of precision is guaranteed. And even for small powers, one has to take care rounding the result to the nearest integer instead of zero. – Gassa Mar 03 '20 at 22:41
  • 1
    Swapping output mechanisms won't help. You're getting that message because you designed a suboptimal algorithm and it's failing the hard testcases. Design a better algorithm. Think about its _algorithmic complexity_; reduce that. Think about _how it scales_; improve that. That is, ultimately, the purpose of the exercise. – Asteroids With Wings Mar 03 '20 at 22:57
  • @AsteroidsWithWings the complexity of this code doesn't seem bad at all. It's O(t log(b)), which seems about as good as you could hope for. – JohnFilleau Mar 03 '20 at 23:15
  • @0x5453 [See this about using pow](https://stackoverflow.com/questions/25678481/why-does-pown-2-return-24-when-n-5-with-my-compiler-and-os/25678721#25678721). In short, the OP **should** be implementing `pow` by hand and **not** use `std::pow`. – PaulMcKenzie Mar 04 '20 at 01:48
  • @PaulMcKenzie Seems like that could be easily fixed with `std::round(std::pow(...))`, no? (As long as the exponents are small enough that the accumulated error is < 0.5, which may not be the case for OP's example.) – 0x5453 Mar 04 '20 at 16:42

2 Answers2

1

Answering the literal question, how to change cout to printf.

Instead of #include <iostream>, you want #include <cstdio>, which is short for "C language standard input and output".

Instead of cout <<wynik<<endl;, you want printf("%d\n", (int) wynik). Here, "%d\n" is a formatting string saying "print the next argument, which should be int, in decimal, and then print a newline".

You may also want to use C-style input, then change cin>>a>>b>>m; into scanf("%d%d%d", &a, &b, &m);. This says "read three decimal integers, one into variable a (& is taking an address of a variable), the other into b, and yet another into m.

That said, note that relative speed of C-style and C++-style input and output depends on plenty of factors, including compiler version, OS, and environment. In another testing environment, you may find cout is actually on par with, or faster than, printf.

Gassa
  • 8,546
  • 3
  • 29
  • 49
0

If you want to use cin and cout you can insert this lines in main()

cin.tie(0);
cout.tie(0);
ios_base::sync_with_stdio(0);

and it should work as fast as priantf and scanf.

Jakub Swistak
  • 304
  • 3
  • 10