Problem:


Score : 300 points

Problem Statement

Given an integer N, find the base -2 representation of N.

Here, S is the base -2 representation of N when the following are all satisfied:

S is a string consisting of 0 and 1.

Unless S = 0, the initial character of S is 1.

Let S = S_k S_{k-1} ... S_0, then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N.

It can be proved that, for any integer M, the base -2 representation of M is uniquely determined.

Constraints

Every value in input is integer.

-10^9 \leq N \leq 10^9

Input

Input is given from Standard Input in the following format:

N

Output

Print the base -2 representation of N.

Sample Input 1

-9

Sample Output 1

1011

As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011 is the base -2 representation of -9.

Sample Input 2

123456789

Sample Output 2

11000101011001101110100010101

Sample Input 3

0

Sample Output 3

0



Sample input:
-9


Sample output:
1011

Submission status: Wrong Answer

Solution code:
import sys
N = int(sys.stdin.readline())

def div(a):
    return -(a // 2), a % 2


res = []
while N < 0 or 2 <= N:
    N, a = div(N)
    print(N, a)
    res.append(a)
res.append(N)

print(''.join(map(str, reversed(res))))

Submission status: Wrong Answer

Solution code:
def convert_base(n):
    temp = n
    out = ''
    while temp != 0:
        q, r = divmod(temp, -2)
        if r == -1:
            q += 1
            r = 1
        out = str(r) + out
        temp = q
    return out

N = int(input())

print(convert_base(N))

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
c = []


def f(B):
    ans = 0
    for idx in range(len(B)):
        if B[len(B) - idx - 1] == "1":
            ans += ((-2)**idx)

    return ans


def is_lower(idx, c_value, N):
    add_value = 0
    for i in range(idx, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# idx未満の添え字の数を引いて行った結果，
# 目的の数を上回ればidxを引く必要がある
def is_over(idx, c_value, N):
    sub_value = 0
    for i in range(idx, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    N = int(input())
    c_value = None

    if N == 0:
        print(0)
        return

    for i in range(50):
        c.append((-2)**i)

    if N > 0:
        tmpsum = 0
        for i in range(50):
            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    print(ans)
    print(f(ans))


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
b = -2

remains = []
while n != 0:
    remain = n%b
    n = n//b
    
    if remain<0:
        remain += -b
        n += 1
    remains.append(remain)

remains = list(map(str,remains))
ans = ''.join(remains)[::-1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
c = []


def is_lower(idx, c_value, N):
    add_value = 0
    for i in range(idx, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# idx未満の添え字の数を引いて行った結果，
# 目的の数を上回ればidxを引く必要がある
def is_over(idx, c_value, N):
    sub_value = 0
    for i in range(idx, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    N = int(input())
    c_value = None

    if N == 0:
        print(0)

    for i in range(50):
        c.append((-2)**i)

    if N > 0:
        tmpsum = 0
        for i in range(50):
            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum >= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub <= N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
c = []


def is_lower(idx, c_value, N):
    add_value = 0
    for i in range(idx, -1, -1):
        if c[i] > 0:
            add_value += c[i]

    return c_value + add_value < N


# idx未満の添え字の数を引いて行った結果，
# 目的の数を上回ればidxを引く必要がある
def is_over(idx, c_value, N):
    sub_value = 0
    for i in range(idx, -1, -1):
        if c[i] < 0:
            sub_value += c[i]

    return c_value + sub_value > N


def main():
    N = int(input())
    c_value = None

    if N == 0:
        print(0)

    for i in range(50):
        c.append((-2)**i)

    if N > 0:
        tmpsum = 0
        for i in range(50):
            if c[i] > 0:
                tmpsum += c[i]

            if tmpsum > N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    else:
        tmpsub = 0
        for i in range(50):
            if c[i] < 0:
                tmpsub += c[i]

            if tmpsub < N:
                idx = i
                c_value = c[i]
                break

        ans = "1"

        for c_idx in range(idx - 1, -1, -1):
            if c[c_idx] < 0:
                if is_over(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"
            else:
                if is_lower(c_idx - 2, c_value, N):
                    ans += "1"
                    c_value += c[c_idx]
                else:
                    ans += "0"

    print(ans)


main()

Submission status: Wrong Answer

Solution code:
N = int(input())

res = ""
while N!=0:
    tmp = N % -2
    N = N//-2 -tmp
    res = str(abs(tmp))+res

print(res)

Submission status: Wrong Answer

Solution code:
def EncodeNegBase(n, b): #Converts from decimal
	if n == 0:
		return "0"
	out = []
	while n != 0:
		n, rem = divmod(n, b)
		if rem < 0:
			n += 1
			rem -= b
		out.append(rem)
	return "".join(map(str, out[::-1]))
 
def DecodeNegBase(nstr, b): #Converts to decimal
	if nstr == "0":
		return 0
 
	total = 0
	for i, ch in enumerate(nstr[::-1]):
		total += int(ch) * b**i
	return total

Submission status: Wrong Answer

Solution code:
n=int(input())

s=""
index=1

while n!=0:
    if n%2!=0:
        s+="1"
        n+=(-1)**index
    else:
        s+="0"
    n//=2
    index+=1
print(s[::-1])

Submission status: Wrong Answer

Solution code:
n = int(input())
while n%2 == 0:
    n = n//(-2)
if n != 0:
    ans = ''
    while n != 0:
        while n%2 == 0:
            n = n//(-2)
            ans = '0'+ans
        n = n-1
        ans ='1'+ans
        n = n/(-2)
else:
    ans = '0'
    
print(ans)

Submission status: Wrong Answer

Solution code:
n = int(input())

a = ""
while n != 0:
    if n % (-2) == 0:
        a += "0"
        n = n // -2
    else:
        a += "1"
        n = n // -2 + 1
b = a[::-1]
print(b)

Submission status: Wrong Answer

Solution code:
N = int(input())

ans = str(bin(N))

string = ""

if N<0:
    for i in range(3,len(ans)):
        string = string + ans[i]
else:
    for i in range(2,len(ans)):
        string = string + ans[i]
    
print(string)

Submission status: Wrong Answer

Solution code:
N = input()

i = 1
s = ""

while abs(i) <= abs(N):
	if (abs(N) & abs(i)) != 0:
		s += '1'
		N -= i
	else:
		s += '0'

	i *= -2

s = s[::-1]
print s

Submission status: Wrong Answer

Solution code:
def f(x):
 if x==0:return "0"
 if x==1:return "1"
 return f(-x/2)+str(x%2)
n=input()
print f(n)

Submission status: Wrong Answer

Solution code:
inp = input()
print('{0:b}'.format(int(inp)))

Submission status: Time Limit Exceeded

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    L = 100000

    N = NI()

    s = 1 if N > 0 else -1
    n = abs(N)

    bit = [0] * L

    i = 0
    while n > 0:
        if n % 2:
            bit[i] += 1
            if s > 0 and i % 2 == 1 or s < 0 and i % 2 == 0:
                bit[i+1] += 1
        n //= 2
        i += 1

    for i in range(L-2):
        if bit[i] > 1:
            bit[i+2] += bit[i] // 2
            bit[i+1] += bit[i] // 2
            bit[i] = bit[i] % 2

    f = False
    ans = ''
    for i in range(L-1,-1,-1):
        if bit[i] == 1:
            ans = ''.join((ans,'1'))
            f = True
        elif f:
            ans = ''.join((ans,'0'))
    if ans == '': ans = '0'

    print(ans)





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list_2 = [pow(-2, i) for i in range(21)]
ans = 0
for i in range(2 ** len(list_2)):
    value = 0
    for j in range(len(list_2)):
        if ((i >> j) & 1):
            value += list_2[j]
    if value == n:
        ans = format(i, 'b')
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
list_2 = [pow(-2, i) for i in range(31)]
ans = 0
for i in range(2 ** 31):
    value = 0
    for j in range(31):
        if ((i >> j) & 1):
            value += list_2[j]
    if value == n:
        ans = format(i, 'b')
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = N
t = ''
i = 0
while s != 0:
  if s % 2**i == 0:
    s -= (-2)**i
    t += '1'
  else:
    t += '0'
  i += 1
if t == '':
  t = 0
print(int(t))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = []
while N != 0:
  A = [N % (-2)] + A[:]
if N == 0:
  A = [0]
for i in range(len(A)):
  print(A[i], end = '')

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
i = 0
while True:
    ans = 0
    for j in range(len(str(bin(i)))-2):
        if i & 1 << j:
            ans += (-2)**j
    if ans == n:
        print(bin(i)[2:])
        break
    i += 1

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=""
while n!=0:
    x=str(n%2)+x
    s=-(n//2)
print(0 if x=="" else x)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
res = []
while True:
    if N % -2 != 0:
        res.append("1")
    else:
        res.append("0")
    
    if N == 1:
        break

    if N % -2 != 0:
        N -= 1
    N //= -2

print("".join(reversed(res)))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2))
    N = -(N - N % 2) 
print("".join(list(reversed(a))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
a = []
if N == 0:
    a = ["0"]
while N != 0:
    a.append(str(N % 2))
    # N = -(N - N % 2) 
print("".join(list(reversed(a))))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
ans = ''
while N != 1:
    if abs(N) % 2 == 1:
        ans += '1'
        N = (N-1) // -2
    else:
        ans += '0'
        N = N // -2
ans += '1'
print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log
from itertools import product


def solve(string):
    n = int(string)
    if n == 0:
        return "0"

    length = ceil(log(3 * n + 1, 4) -
                  1) * 2 if n > 0 else ceil(log(3 * abs(n) / 2 + 1, 4) - 1) * 2 + 1
    powers = [(-2)**i for i in range(length, -1, -1)]
    for digits in product("10", repeat=len(powers)):
        tmp = sum([_p if _d == "1" else 0 for _d, _p in zip(digits, powers)])
        if tmp == n:
            return "".join(digits)


if __name__ == '__main__':
    print(solve(input()))

Submission status: Time Limit Exceeded

Solution code:
a=int(input())
b=''
while a:
 b=str(a&1)+b
 a=-(a<<1)
print(b if b else 0)

Submission status: Time Limit Exceeded

Solution code:
N = input()

ans = ""

while True:
  if abs(N) % 2 == 1:
    ans += "1"
    N -= 1
  else:
    ans += "0"
  N /= -2
  if N == 1:
    ans += "1"
    break

print(ans[::-1])

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    else:
        for i in range(10**9):
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
            if n == 1:
                break
        ans += '1'
        ans = ans[::-1]
        
    return ans

print(minus_2(N))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans += '1'
    else:
        while n != 1:
            if n % 2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans

print(minus_2(N))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans.append('1')
    else:
        while n != 1:
            if n % -2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans

ans = minus_2(N)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def minus_2(n):
    ans = ''
    if n == 1:
        ans.append('1')
    else:
        while n != 1:
            if n % -2 == 0:
                ans += '0'
            else:
                ans += '1'
            n = math.ceil(n/-2)
        ans += '1'
        ans = ans[::-1]
        
    return ans

ans = minus_2(N)

print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
import math
N = int(input())

def minus_2(n):
    ans =[]
    if n == 1:
        ans.append('1')
    else:
        while n != 1:
            if n % -2 == 0:
                ans.append('0')
            else:
                ans.append('1')
            n = math.ceil(n/-2)
        ans.append('1')
        ans = ans[::-1]
        
    return ans

ans = minus_2(N)

print(''.join(ans))

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
N = int(input())

def up(n):
  global next_digit
  n += next_digit
  next_digit = 0
  if n == 0:
    return 0
  elif n == 1:
    return 1
  else:
    next_digit = 1
    return 0

digit = [0 for i in range(30)]
#a = [(digit[i] * (2 ** i)) for i in range(30)]
while True:
  a = [(digit[i] * ((-2) ** i)) for i in range(30)]
  #print(digit)
  #print(a)
  if sum(a) == N:
    break
  else:
    next_digit = 0
    digit[0] += 1
    for i in range(30):
      digit[i] = up(digit[i])
#print(digit)
rev_digit = [i for i in reversed(digit)]
result = reduce(lambda x, y:10*x+y, rev_digit)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import math

# input
N = int(input())

ans = []

if N == 0:
    print(0)
else:
    while N != 1:
        if N > 0:
            n = 2 * (math.ceil(math.log(3 * N + 1, 4)) - 1) + 1 # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
        else:
            n = 2 * math.ceil(math.log((-3 * (N - 1) / 2) + 1, 4)) # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
    ans.append(0)
    n = max(ans) + 1 # N を -2進法で表したときの桁数
    for i in range(n)[::-1]:
        if i in ans:
            print(1, end = "")
        else:
            print(0, end = "")

Submission status: Time Limit Exceeded

Solution code:
import math

# input
N = int(input())

ans = []

if N == 0:
    print(0)
else:
    while N != 1:
        if N > 0:
            n = 2 * math.ceil(math.log(3 * N + 1, 4)) - 1 # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
        else:
            n = 2 * math.ceil(math.log((-3 * (N - 1) / 2) + 1, 4)) # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
    ans.append(0)
    n = max(ans) + 1 # N を -2進法で表したときの桁数
    for i in range(n)[::-1]:
        if i in ans:
            print(1, end = "")
        else:
            print(0, end = "")

Submission status: Time Limit Exceeded

Solution code:
import math

# input
N = int(input())

ans = []

if N == 0:
    print(0)
else:
    while N != 1:
        if N > 0:
            n = 2 * math.floor(math.log(3 * N + 1, 4)) + 1 # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
        else:
            n = 2 * math.ceil(math.log((-3 * (N - 1) / 2) + 1, 4)) # N を -2進法で表したときの桁数
            ans.append(n - 1)
            N = N - (-2) ** (n - 1)
    ans.append(0)
    n = max(ans) + 1 # N を -2進法で表したときの桁数
    ans_bin = [0 for _ in range(n)]

    for i in range(n):
        if i in ans:
            ans_bin[i] = 1

    ans_bin = map(str, ans_bin)
    ans_bin_str = ''.join(ans_bin)
    ans_bin_str = ans_bin_str[::-1]
    print(ans_bin_str)

Submission status: Time Limit Exceeded

Solution code:
# input
N = int(input())

ans = []

if N == 0:
    print(0)
else:
    ans.append(0)
    while N != 1:
        if N > 0:
            k = 0
            sum = 1
            while sum < N:
                k += 2
                sum += (-2) ** k
            ans.append(k)
            N = N - (-2) ** k
        else:
            k = 1
            sum = -1
            while sum > N:
                k += 2
                sum += (-2) ** k
            ans.append(k)
            N = N - (-2) ** k

    n = max(ans) + 1 # N を -2進法で表したときの桁数
    ans_bin = [0 for _ in range(n)]

    for i in range(n):
        if i in ans:
            ans_bin[i] = 1

    ans_bin = map(str, ans_bin)
    ans_bin_str = ''.join(ans_bin)
    ans_bin_str = ans_bin_str[::-1]
    print(ans_bin_str)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
i=0
b=[]
q=n
ans=""

while 1:
  r=q%(-2)
 
  if r==0:
    b.append(0)
    q=int(q/(-2))
  else:
    b.append(1)
    q=int(q/(-2)+0.5)
    if q==0:
      break
  i=i+1

b.reverse()
for j in range(i+1):
  ans=ans+str(b[j])
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ans = ""
while n != 1:
  a = n % -2
  if a == 1 or a == -1:
    ans = "1" + ans
    if a == -1:
      n -= 1
  else:
    ans = "0" + ans
  n = n / -2
ans = "1" + ans
print (ans)

Submission status: Time Limit Exceeded

Solution code:
N = float(input())

q = N
r_s = []
while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  
  r_s.append(r)
r_s.append(1)
r_s = r_s[::-1]

for i in range(len(r_s)):
  print(r_s[i], end="")

Submission status: Time Limit Exceeded

Solution code:
N = float(input())
q = N
r_s = []
while q!=1:
  hoge = (q-1) / (-2)
  if hoge.is_integer():
    r = int(1)
    q = float(hoge)
  else:
    r = int(0)
    q = float(q/(-2))
  r_s.append(r)
r_s.append(1)
r_s = r_s[::-1]
for i in range(len(r_s)):
  print(r_s[i], end="")

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

N = int(input())

i = 0
while True:
    bins = list(bin(i)[2:])
    ans = 0
    for j in range(len(bins)-1, -1, -1):
        if bins[j] == "1":
            ans += (-2) ** (len(bins)-1-j)
    if ans == N:
        print("".join(bins))
        exit()
    i += 1

Submission status: Time Limit Exceeded

Solution code:
l=[1,-2]

#for i in range(2,100):
for i in range(2,50):
    l.append(l[-1]*-2)
#print(l)
n=int(input())
for i in range(1000000):
    t=(bin(i)[2:])[::-1]
    chk=0
#    print(t)
    for j,k in enumerate(t):
#        print(k)
        if k=='1':
            chk+=l[j]
        if chk==n:
            print(t[::-1])
            exit()

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce

n = int(input())

res = []

while True:
  if n == 1:
    res.append(1)
    break
  if n%2 == 0:
    res.append(0)
    n //= -2
  else:
    res.append(1)
    n = (n-1)//(-2)


print(reduce(lambda s, x: s + str(x), reversed(res) ,""))

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    if N == 0:
        print(0)
        exit()
    if N < 0:
        N = -N
        D = defaultdict(int)
        index = 0
        while N >= 1:
            #bitフラグがたっていたら
            if N & 1 == 1:
                #2の倍数の場合D[index]とD[index+1]に1を足す
                if index % 2 == 0:
                    D[index] += 1
                    D[index+1] += 1
                else:
                    D[index] += 1
            else:
                D[index] = D[index]
            N = N>>1
            index += 1
    else:
        D = defaultdict(int)
        if N & 1 == 1:
            D[0] = 1
        else:
            D[0] = 0
        index = 1
        N = N >> 1

        while N >= 1:
            #bitフラグがたっていたら
            if N & 1 == 1:
                #2の倍数の場合D[index]とD[index+1]に1を足す
                if index % 2 == 1:
                    D[index] += 1
                    D[index+1] += 1
                else:
                    D[index] += 1
            else:
                D[index] = D[index]
            N = N>>1
            index += 1
            
            
    index = 0
    while True:
        if not index in D.keys():
            break
        if D[index] <= 1:
            pass
        else:
            temp = D[index]
            D[index] = temp % 2
            D[index+1] += (temp // 2)
            D[index+2] += (temp // 2)
            if D[index+1] >= D[index+2] * 2:
                temp = D[index+2]
                D[index+2] -= temp
                D[index+1] -= temp * 2
        index += 1
    res = True

    for i in reversed(D.values()):
        if res and i == 1:
            res = False
        if not res:
            print(i, end="")
    print()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
if N == 0:
    s = '0'
else:
    s = ''
while N != 0:
    m = N%2
    s += str(m)
    N = (N - m)*(-1)//2
print(s[::-1])

Submission status: Accepted

Solution code:
# 解説と以下を参考に作成
# https://atcoder.jp/contests/abc105/submissions/17007379
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    if N == 0:
        print('0')
        return

    ans = ''
    while N != 0:
        # 1桁目が 1 or 0 かはNが奇数か偶数かによってのみ決まる.
        #  → 2 で割った余りから 1 or 0 を決定する.
        m = N % 2
        ans = str(m) + ans
        # 1桁目の情報を取り除いて(偶数にして)右シフトし, 次の桁についても同様に確認していく.
        # この時, 2(,4,6,...)桁目は負の要素となっているので, 1桁目(1 or 0)として判定するために正負を反転させる.
        N = (N - m) * (-1) >> 1
    print(ans)


if __name__ == '__main__':
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N):
    if N == 0:
        print('0')
        return
    x = math.ceil(math.log2(abs(N))) + 1
    minus = [(-2) ** i for i in range(1, x + 1, 2)]
    plus = [(-2) ** i for i in range(0, x + 1, 2)]
    minus.sort()
    plus.sort(reverse=True)

    minus_sum = [0]
    for m in minus:
        minus_sum.append(minus_sum[-1] + m)
    plus_sum = [0]
    for p in plus:
        plus_sum.append(plus_sum[-1] + p)

    ans = ''
    n = 0
    flg = True if len(plus) > len(minus) else False
    m = 0
    p = 0
    while True:
        if flg:
            tg = plus[p]
            p += 1
        else:
            tg = minus[m]
            m += 1

        if n + tg >= N:
            if n + tg != N and n + tg + (minus_sum[-1] - minus_sum[m]) > N:
                ans += '0'
            else:
                ans += '1'
                n += tg
        else:
            if n + tg + (plus_sum[-1] - plus_sum[p]) < N:
                ans += '0'
            else:
                ans += '1'
                n += tg
        flg = not flg
        if p >= len(plus) and m >= len(minus):
            break
    print(str(int(ans)))


if __name__ == '__main__':
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    # AB = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()