Делал на питоне:

import math
def solve():
    n = input()
    s = ''
    for i in xrange(n):
        k = input()
        d = math.sqrt((k << 3) - 7)
        result = int(d)
        if result == d and result & 1:
            s += '1 '
        else:
            s += '0 '
    print s

solve()

Выдает TL, как ускорить? Пробовал сразу ответ выводить - на моих тестах это дольше по времени.

k << 3 заменял на k * 8, result & 1 менял на result % 2 - все равно TL. Python 2.7

Для себя понял, что самое времязатратное - ввод/вывод. Поэтому AC получил так:

import math
import sys

stringArray = sys.stdin.read().split()
i = 0
s = ''
for string in stringArray:
    if i == 0:
        i += 1
        continue

    k = int(string)
    d = math.sqrt((k << 3) - 7)
    result = int(d)
    if result == d and result & 1:
        s += '1 '
    else:
        s += '0 '
print s

Но все равно интересует - есть ли способ ускорить первое решение?