DMOPC '16 Contest 4 P1 - Fast Exponents

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Problem types

Molly's teacher assigned her very tedious homework:

Given an integer i_i, find out if it's a power of two or not.

Molly asks Andrew, but he would much rather play Geometry Dash, so he decides to enslave ask you to do it instead!

Input Specification

The first line will contain a single integer, N.
Lines 2 \dots N + 1 will each contain an integer, i_i.

Output Specification

For each of the N integers, output T if it is a power of 2, otherwise output F.


1 \le N \le 10^6
1 \le i_i < 2^{63}

Sample Input


Sample Output



  • 1
    SuperClash  commented on Dec. 21, 2020, 3:09 p.m. edited

    Tfw your brute force solution passes.

    • 1
      sushi  commented on Dec. 22, 2020, 12:33 p.m.

      It's not really brute force/brute force is intended, as your code runs in O(N \log N), which would pass with the constraints.

  • -1
    Blackgaurdian3  commented on Aug. 1, 2020, 7:23 p.m.

    why am i getting WA for case 11?

    • -4
      YaySushi  commented on Aug. 1, 2020, 10:40 p.m.

      because your answer is wrong

      • 1
        balathegreat999  commented on Dec. 21, 2020, 1:15 p.m.

        how can you be so contraversial but so true

  • 1
    Latitude  commented on June 28, 2018, 8:24 a.m.

    PASSA EM nlogn ?

  • 1
    haytam  commented on Dec. 13, 2017, 5:45 p.m.

    pls why i get WA in the case 3

  • -7
    mrglioula  commented on Nov. 24, 2017, 5:02 p.m.

    This comment is hidden due to too much negative feedback. Click here to view it.

    • 0
      onetwothree  commented on Nov. 25, 2017, 9:03 p.m. edited

      First, you didn't use the boolean in your loop. Second, use scanf instead of cin. Finally, use long instead of int.

  • 0
    WilliamW_0627  commented on Feb. 16, 2017, 10:25 a.m.

    I submitted the exact same code twice and i got TLE (case 24) on one and AC on the other. What's up with that?

    • 5
      WallE256  commented on Feb. 16, 2017, 10:35 a.m. edited

      Please read this comment. In a nutshell, the judges don't produce the exact same result each time. As your program is really close to the timelimit, this kind of thing can happen.

  • 0
    Lunjun  commented on Feb. 14, 2017, 7:49 p.m.

    I implemented an algorithm using Python, but it did not pass. I implemented the same algorithm using C++, and it worked.

    • 2
      Kirito  commented on Feb. 15, 2017, 3:10 p.m.

      This problem has a lot of input, and input() is too slow; your code passes with sys.stdin.readline().