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

Solution (Python):



import bisect

def IT(): 
    return int(input())
def IL(): 
    return [int(_) for _ in input().split()]
def IS(): 
    return [_ for _ in input().split()]
def ILS(n): 
    return [int(input()) for _ in range(n)]
def SLS(n): 
    return [input() for _ in range(n)]
def ILSS(n): 
    return [[int(_) for _ in input().split()] for j in range(n)]


def bit_full_search2(A):
    
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])

    value.sort(key=lambda x:x[1])
    bin = [value[k][0] for k in range(len(value))]
    val = [value[k][1] for k in range(len(value))]
    return bin, val

"""ここからメインコード"""
def main():
    n = IT()
    
    list1 = [(-2) ** i for i in range(16)]
    list2 = [(-2) ** (i + 16) for i in range(16)]
    list1_bin, list1_val = bit_full_search2(list1)
    list2_bin, list2_val = bit_full_search2(list2)

    
    ans = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                ans = list2_bin[j] + list1_bin[i]
                break
    print(int(ans))

main()

Solution (Python):
N = int(input())

base = -2
l = []
while N:
    a = ((-N)//base)*-1
    r = N-(-2)*a
    l.append(r)
    N = a

if len(l) == 0:
    print(0)
else:
    print(''.join(map(str, reversed(l))))

Solution (Python):



import bisect

def IT():
    return int(input())
def IL():
    return [int(_) for _ in input().split()]
def SL():
    return [int(_) for _ in input().split()]
def ILS(n):
    return [int(input()) for _ in range(n)]
def SLS(n):
    return [input() for _ in range(n)]
def ILSS(n):
    return [[int(_) for _ in input().split()] for j in range(n)]


"""ここからメインコード"""
def main():
    n = IT()
    ans = ""
    for i in range(32):
      if n % (2 ** (i+1)) != 0:
        n -= n % (2 ** (i+1)) * (-1) ** (i % 2)
        ans += "1"
      else:
        ans += "0"
    print(int(ans[::-1]))
main()

Solution (Python):



import bisect

def IT():
    return int(input())
def IL():
    return [int(_) for _ in input().split()]
def SL():
    return [int(_) for _ in input().split()]
def ILS(n):
    return [int(input()) for _ in range(n)]
def SLS(n):
    return [input() for _ in range(n)]
def ILSS(n):
    return [[int(_) for _ in input().split()] for j in range(n)]


def bit_full_search(ss):
    n = len(ss)
    for i in range(1 << n):
        s = ""
        for j in range(n + 1):
            if ((1 & i >> j) == 1):
                s += ss[j]
        print(s)

def bit_full_search2(A):
    
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])
    return value


"""ここからメインコード"""
def main():
    n = IT()
    
    list1 = [(-2) **  i for i in range(16)]
    list2 = [(-2) ** (i + 16) for i in range(16)]

    list1 = bit_full_search2(list1)
    list1.sort(key=lambda x:x[1])
    list1_bin = [list1[i][0] for i in range(len(list1))]
    list1_val = [list1[i][1] for i in range(len(list1))]

    list2 = bit_full_search2(list2)
    list2.sort(key=lambda x:x[1])
    list2_bin = [list2[i][0] for i in range(len(list2))]
    list2_val = [list2[i][1] for i in range(len(list2))]
    ans = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                ans = list2_bin[j] +list1_bin[i]
                break
    print(int(ans))
main()

Solution (Python):
N=int(input())

if N%2==0:
  ans='0'
else:
  ans='1'
  N-=1
  
i=2
while abs(N)>0:
  if N%((-2)**i)==0:
    ans='0'+ans
  else:
    ans='1'+ans
    N-=(-2)**(i-1)
  i+=1
    
print(ans)

Solution (Python):
N = int(input())

def main(N):
    if N == 0:
        return 0, 0
    if N >= 1:
        for i in range(0, 32, 2):
            if N <= (2**(i+2)-1)//3:
                return N - 2**i, 10**i
    if N <= -1:
        for i in range(1, 34, 2):
            if (-2)*(2**(i+1)-1)//3 <= N:
                return N - (-2)**i, 10**i
    assert False, 'Never reached: N = {}'.format(N)

base2 = 0
while N != 0:
    N, bit = main(N)
    base2 += bit
print(base2)

Solution (Python):
N = int(input())
if N == 0:
    print(0)
    exit()

L = []
M = []

for length in range(1,41):
    if length % 2 == 0:
        l = -2 * pow(4,length//2) // 3
        m = (pow(4,length//2) - 1) // 3
    elif length % 2 == 1:
        l = -2 * (pow(4,(length-1)//2) - 1) // 3
        m = (pow(4,(length+1)//2) - 1) // 3
    L.append(l)
    M.append(m)

identify = []
for i in range(40):
    if i == 0:
        ap_list = [L[0],M[0]]
    elif i % 2 == 1:
        ap_list = [L[i],L[i-1]]
    elif i % 2 == 0:
        ap_list = [M[i-1],M[i]]
    identify.append(ap_list)

bit = [0]*40
for i in range(39,-1,-1):
    left = identify[i][0]
    right = identify[i][1]
    if i % 2 == 0 and left < N <= right:
        bit[39-i] = 1
        N -= pow(-2,i)
    elif i % 2 == 1 and left <= N < right:
        bit[39-i] = 1
        N -= pow(-2,i)

ans = "".join(str(e) for e in bit).lstrip("0")
print(ans)

Solution (Python):


n = int(input())

if n == 0:
    print(0)
    exit()

ans = ''
while abs(n) > 0:
    if n % 2 != 0:
        ans += '1'
        n -= 1
        n //= -2
    else:
        ans += '0'
        n //= -2

print(ans[::-1])

Solution (Python):
N = int(input())
if N == 0:
    print(0)
    exit()
L = []
M = []

def bit_range(bit_length,maximum=0,minimal=0):
    for i in range(bit_length-1,-1,-1):
        if i % 2 == 0:
            maximum += pow(2,i)
        else:
            minimal += pow(-2,i)
    L.append(minimal)
    M.append(maximum)

for i in range(1,41):
    bit_range(i)

identify = []
for i in range(40):
    if i == 0:
        ap_list = [L[0],M[0]]
    elif i % 2 == 1:
        ap_list = [L[i],L[i-1]]
    elif i % 2 == 0:
        ap_list = [M[i-1],M[i]]
    identify.append(ap_list)

bit = [0]*40
for i in range(39,-1,-1):
    left = identify[i][0]
    right = identify[i][1]
    if i % 2 == 0 and left < N <= right:
        bit[39-i] = 1
        N -= pow(-2,i)
    elif i % 2 == 1 and left <= N < right:
        bit[39-i] = 1
        N -= pow(-2,i)

ans = "".join(str(e) for e in bit).lstrip("0")
print(ans)

Solution (Python):
N = int(input())
minus_bit = ''
if N == 0:
    minus_bit = '00'
while N != 0:
    mod = N % 4
    if mod == 0:
        minus_bit = minus_bit + '00'
        N = N//4
    elif mod == 1:
        minus_bit = minus_bit + '10'
        N = (N-1)//4
    elif mod == 2:
        minus_bit = minus_bit + '01'
        N = (N+2)//4
    else:
        minus_bit = minus_bit + '11'
        N = (N+1)//4

if minus_bit[-1] == '0':
    minus_bit = minus_bit[:-1]
print(minus_bit[::-1])

Solution (Python):
n=int(input());s=''
while n!=0:s=str(n%2)+s;n=-(n//2)
print(s if s else 0)

Solution (Python):
n=int(input());s=''
while n!=0:s=str(n%2)+s;n=-(n//2)
print(s*(s!='')or 0)

Solution (Python):

import math

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

    max_k = 0
    if N < 0:
        min_n = 0
        for k in range(1, 32, 2):
            min_n += (-2) ** k
            if min_n <= N:
                max_k = k
                break
    else:
        max_n = 0
        for k in range(0, 32, 2):
            max_n += 2 ** k
            if N <= max_n:
                max_k = k
                break

    t = 0
    for k in range(1, max_k + 1, 2):
        t += 2 ** k

    n = N + t
    n ^= t

    print(bin(n)[2:])


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

N = int(input())
ans = ""
while (N != 0):
    if N % 2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
        N -= 1
    N //= -2
if ans == "":
    ans = "0"
print(ans)

Solution (Python):
import math
N = int(input())
ans = ''

if N == 0:
    ans += '0'
else:
    while N != 1:
        if N % 2 == 0:
            ans += '0'
        else:
            ans += '1'
        N = math.ceil(N / -2)
    ans += '1'
ans = ans[::-1]
print(ans)

Solution (Python):


kmax = 40

def main():
    n = int(input())
    di = []
    for i in range(kmax):
        assert abs(n) % (1 << i) == 0
        d = (abs(n) & (1 << i)) >> i
        assert d in [0, 1]
        n -= (-2) ** i * d
        di.append(d)
    di = reversed(di)
    di = [str(x) for x in di]
    di = "".join(di)
    print(int(di))

main()

Solution (Python):



II = lambda: int(input())
MI = lambda: map(int, input().split())


def main():
    N = II()
    if N == 0: return 0
    neg = N < 0
    if neg: N = -N
    bn = bin(N)[2:]
    bl = [int(c) for c in bn[::-1]]
    bl.extend([0] * 10)

    begin = 0 if neg else 1
    for i in range(begin, len(bl), 2):
        if bl[i]:
            bl[i + 1] += 1
        for j in range(i + 1, len(bl)):
            if bl[j] == 2:
                bl[j] = 0
                bl[j + 1] += 1
            else:
                break
    while bl[-1] == 0: bl.pop()
    return "".join(map(str, bl[::-1]))


if __name__ == "__main__":
    print(main())

Solution (Python):
N = int(input())
s = ''

if N != 0:
    while N != 0:
        if N % 2 == 1:
            s += '1'
            N = (N - 1) / (-2) 
        else:
            s += '0'
            N = N / ( -2 )
else :
    s = '0'
print(s[::-1])

Solution (Python):

N = int(input())
base = -2
n = N
a = []

while True:
    if n==0: break
    if n%base ==0:  b = 0
    else:    b = 1
    a.append(b)
    
    n = (n - b)// base
if a==[]: a = [0]
a.reverse()
for x in a: print(x, end='')

Solution (Python):
N = int(input())

if N==0:
    print(0)
else:
    ans = []
    
    while N!=0:
        now = str(N%2)
        ans.append(now)
        N = -1*(N//2)
    ans.reverse()
    print(''.join(ans))

Solution (Python):
def adja(i):
    if int(i) != i and i > 0:
        return int(i)+1
    elif int(i) != i and i < 0:
        return int(i)
    else:
        return int(i)
def mod(i):
   return i + 2 * adja(i/p)

N = int(input())
p = -2
ans=[]
while (True):
    r = mod(N)
    N = adja(N / p)
    ans.append(str(r))
    if N == 1 or N == 0 :
        if N == 1:
            ans.append(str(1))
        break
print("".join(ans[::-1]))

Solution (Python):
N = int(input())
answer = 0

def f(x,answer):
    if x == 0:
        return answer
    else:
        i = 0
        sum = 0
        if x >= 0:
            while sum < x:
                sum = sum + 4**(i)
                i = i + 1
            return f(x - 4**(i-1) ,answer + 10**(2*i-2))
        else:
            while sum < abs(x):
                sum = sum + 2*(4**(i))
                i = i + 1
            return f(x + 2*(4**(i-1)) ,answer + 10**(2*i-1) )

ans = f(N,answer)
print(ans)

Solution (Python):
N=int(input())
i=0
s=[]
n=N
while 1:
    k=pow(2,i+1)
    d=n%k
    if d!=0:
        s.append(1)
        n=n-pow(-2,i)
    elif n//k!=0:
        s.append(0)
    else:
        break
    i=i+1
while s:
    print(s.pop(),end="")
if N==0:
    print(0,end="")
print("")

Solution (Python):
N = int(input())
ans = []
res = N
while res != 1 and res != 0:
    res, tmp = res//(-2), res % (-2)
    if tmp==-1:
        tmp = 1
        res +=1
    ans.append(tmp)
ans.append(res)
print(''.join(map(str, reversed(ans))))

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

Solution (Python):
N = int(input())
ans = []
while N is not 0:
	ans.append(abs(N % (-2)))
	if N % (-2) == 0: N //= (-2)
	else: N = N // (-2) + 1

if ans == []:
	print(0)
else:
	ans.reverse()
	ans = list(map(str, ans))
	print(''.join(ans))

Solution (Python):
n = int(input())
A = []

if n == 0:
    print(0)
else:
    while n != 0:
        if n % -2 != 0:
            A.append('1')
            n = n // -2 + 1
        else:
            A.append('0')
            n = n // -2

A.reverse()
print(''.join(A))

Solution (Python):
def get_neg2(n):
    if n == -2:
        return "10"
    if n == -1:
        return "11"
    if n == 0:
        return "0"
    if n == 1:
        return "1"
    if n % 4 == 0:
        return get_neg2(n // 4) + "00"
    if n % 4 == 1:
        return get_neg2((n - 1) // 4) + "01"
    if n % 4 == 2:
        return get_neg2((n + 2) // 4) + "10"
    if n % 4 == 3:
        return get_neg2((n + 1) // 4) + "11"


N = int(input())
print(get_neg2(N))

Solution (Python):
N=int(input())

if N == 0:
    print(0)
else:
    m = 2
    s = ""
    sgn = 1
    while N!=0:
        r = N % m
        s += "1" if r != 0 else "0"
        m *= -2
        N = N -r 
    print(s[::-1])

Solution (Python):
N=int(input())
if N==0:
    N=0
elif N>0:
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==1:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
else:
    N*=-1
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==0:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
print(int(format(N,"b")))

Solution (Python):
N = int(input())
ans = ''
if N == 0:
    print('0')
    exit()

while N != 0:
    if abs(N) % 2 == 0:
        ans += '0'
        N = int(N / (-2))
    else:
        ans += '1'
        N = int((N-1)/(-2))

ans = ans[::-1]
print(ans)

Solution (Python):
N = int(input())


def f(n):
    if n == 0:
        return "0"

    if n % 2 == 0:
        return f(n // (-2)) + "0"
    else:
        return f((n - 1) // (-2)) + "1"


ans = f(N)
if ans[0] == "0" and len(ans)>=2:
    ans = ans[1:]
print(ans)

Solution (Python):
n = int(input())
binary = []

if n == 0:
    print(0)
    exit()

while n != 0:
    if n % -2 != 0:
        binary.append('1')
        n //= -2
        n += 1
    else:
        binary.append('0')
        n //= -2
        
binary.reverse()

print(''.join(binary))

Solution (Python):
n = int(input())
a = []
b = 0
while n != 0:
    c = (-2) ** b
    if n % (c*(-2)) != 0:
        n -= c
        a.append("1")
    else:
        a.append("0")
    b += 1
ans = "".join(reversed(a))
if ans == "":
  ans = 0
print(ans)

Solution (Python):
N = int(input())
quat=[]

addstr=''
if N<0:
    addstr=str(N%2)
    N-=N%2
    N//=-2

while N>0:
    quat.append(N%4)
    N//=4
quat.append(0)

ans = [0]*(2*len(quat)+2)

for i in range(len(quat)):
    if quat[i]<=1:
        ans[2*i]=quat[i]
    elif quat[i]<=3:
        ans[2*i]=quat[i]%2
        ans[2*i+1]=1
        quat[i+1]+=1
    else:
        quat[i+1]+=1

ansstr=''

i=len(ans)-1

while ans[i]==0:
    i-=1
    if i==-1:
        break

while i>=0:
    ansstr += str(ans[i])
    i-=1


if len(ansstr)>0:
    print(ansstr+addstr)
else:
    print(0)

Solution (Python):
N = int(input())

ans = ""
i = 0
while N != 0:
  if N%2**(i+1) == 2**i:
    N -= (-2)**i
    ans += "1"
  else:
    ans += "0"
  i += 1

if ans == "":
  print(0)
else:
  print(ans[::-1])

Solution (Python):
n = int(input())
s = ''

while n != 0:
    s += str(n % 2)
    n = -(n // 2)

print(s[::-1] if s else 0)

Solution (Python):
n = int(input())
if n == 0:
    print('0')
    exit()

def base_minus_two(n):
    if n == 0:
        return ''
    d = n % 2
    return base_minus_two((n-d)//2 * -1) + str(d)
print(base_minus_two(n))

Solution (Python):
n = int(input())
def minustwo(n,l):
    if n == 0:
        if l == []:
            return [0]
        return l
    else:
        odd = n % 2
        l.append(odd)
        return minustwo((-1)*(n-odd)//2,l)
l = minustwo(n,[])
l.reverse()
for c in l:
    print(c, end='')
print()

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

Solution (Python):
n = int(input())
ans = []

if n == 0:
    print('0')

else:
    while n != 0:
        if n % -2 == -1:
            n = n // -2 + 1
            ans.append('1')
        else:
            n = n // -2
            ans.append('0')
    
    ans.reverse()

    print(''.join(ans))

Solution (Python):
s = input()
if s == 0:
	print "0"
	exit()
else:
	m = s
	ans = ''
	while m != 0:
		kk = m%(-2)
		m = m//(-2)
		if kk < 0:
			kk += 2
			m += 1
		ans += str(kk)
	print ans[::-1]

Solution (Python):
def rec(num):
    if num == 0:
        return '0'
    elif num == 1:
        return '1'
    else:
        return rec((num-num%2)//-2)+str(num%2)
print(rec(int(input())))

Solution (Python):
def hoge(n):
    for i in range(40):
        if(minList[i] <= n and n <= maxList[i]):
            break
    return i

N = int(input().strip())

minList = [0]
maxList = [1]
for d in range(1, 40):
    minList.append(min(minList[-1] + (-2)**d, minList[-1]))
    maxList.append(max(maxList[-1], maxList[-1] + (-2)**d))
    
residual = N
index = hoge(residual)
ans = [0 for i in range(index + 1)]
ans[0] = 1
residual = residual - (-2)**index

while(residual != 0):
    index = hoge(residual)
    ans[len(ans) - 1 - index] = 1
    residual = residual - (-2)**index

if(N == 0):
    ans = [0]
    
print("".join(str(e) for e in ans))

Solution (Python):
from math import *


N = int(input().strip())

def search_n(N):
    if N == 0 or N == 1:
        return 1
    minN = 0
    maxN = 1
    for i in range(1, 40):
        a1 = minN + (-2)**i
        a2 = maxN + (-2)**i
        minN = min(minN, min(a1, a2))
        maxN = max(maxN, max(a1, a2))
        if N <= maxN and N >= minN:
            return i

result = ['0']
while N != 0 and N != 1:
    n = search_n(N)
    N -= (-2)**n
    if len(result) == 1:
        result = ['0' for i in range(0, n+1)]
    result[n] = '1'

if N==1:
    result[0] = '1'

result.reverse()
print(''.join(result))

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

Solution (Python):
N=int(input())

x=[]
if N != 0:
	flag = N // abs(N)
N=abs(N)
while N != 0:
	x.insert(0,N % 2 * flag )
	N //= 2
	flag *= -1
x.insert(0,0)
x.insert(0,0)


for i in range(len(x))[::-1]:
	if x[i] == -1:
		x[i] = 1
		x[i-1] += 1
	if x[i] == 2:
		x[i] = 0
		x[i-1] += 1
		x[i-2] += 1

flag=0
for i in range(len(x)):
	if x[i] == 1 or i == len(x)-1:
		flag=1
	if flag == 1:
		print(x[i],end="")
"""
print()
check=0
count=1
for i in range(len(x))[::-1]:
	check +=  x[i] * count
	count *= -2
print(check)
"""

Solution (Python):
num_dec = int(input())
num_bin = ''

while num_dec != 0:
  if num_dec % 2:
    num_dec -= 1
    num_bin += '1'
  else:
    num_bin += '0'
  num_dec /= -2

if num_bin == '':
  num_bin += '0'

print(num_bin[::-1])

Solution (Python):
def main():
    n = int(input())
    if n == 0:
        print(0)
        return

    ss = []
    t = 0
    m = 1
    while n != t:
        s = int((n - t) % (abs(m) * 2) != 0)
        ss.append(s)
        if s:
            t += m
        m *= -2
    print(''.join(map(str, reversed(ss))))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
m2 = []

if N == 0:
    print(0)
    
while N != 0:
    if N % -2 != 0:
        m2.append('1')
        N = N // -2 + 1
    else:
        m2.append('0')
        N = N // -2

m2.reverse()

print("".join(map(str, m2)))

Solution (Python):
N = int(input())

if N == 0:
  print(0)
  exit()

S = ""

cnt = 0
while N != 0:
  if abs(N) % pow(2, cnt + 1) != 0:
    S += "1"
    N -= pow(-2, cnt)
  else:
    S += "0"
  cnt += 1
print(S[::-1])

Solution (Python):
n = int(input())
m2 = []
 
if n == 0:
    print(0)
    
while n != 0:
    if n % -2 != 0:
        m2.append('1')
        n = n // -2 + 1
    else:
        m2.append('0')
        n = n // -2
        
m2.reverse()
print(''.join(map(str, m2)))

Solution (Python):
import math
n = int(input())
x = []

if n == 0:
    print(0)
else:
    if n > 0:
        a = math.ceil(math.log2(n * 3 + 1) / 2) 
        b = 2 * a - 1
        x = [[]] * (b)
    else:
        a = math.ceil(math.log2((-3 * n + 2) / 2) / 2)
        b = 2 * a
        x = [[]] * (b)
    while n != 0:
        if n > 0:
            a = math.ceil(math.log2(n * 3 + 1) / 2) 
            b = 2 * a - 1 
            n = n - (2) ** (b-1)
            x[-b] = "1"  
        else:
            a = math.ceil(math.log2((-3 * n + 2) / 2) / 2)
            b = 2 * a
            n = n - (-2) ** (b-1)
            x[-b] = "1"
x_replace = ["0" if i != "1" else i for i in x]
x_replace = "".join(x_replace)
print(x_replace)

Solution (Python):
n = int(input())
m2 = []

if n == 0:
    print(0)
    
while n != 0:
    if n % -2 != 0:
        m2.append('1')
        n = n // -2 + 1
    else:
        m2.append('0')
        n = n // -2
        
m2.reverse()
print(''.join(map(str, m2)))

Solution (Python):
n = int(input())

ans = ''


for i in range(1000):
  if n % pow(2, i+1) == 0: 
    ans += '0'
  else: 
    ans += '1'
    n = n - pow(-2, i)
  if n == 0:
    break
print(ans[::-1])

Solution (Python):
import math
import sys

N = int(input())
if N == 0:
    max = 1
else:
    max = math.ceil(math.log(abs(N), 2)) + 3

result = []
numerator = N
for i in range(0, max):
    if numerator % (math.pow(2, i + 1)) == 0:
        result.append(str(0))
    else:
        result.append(str(1))
        numerator -= math.pow(-2, i)

    if numerator == 0:
        break
result.reverse()
print("".join(result))

Solution (Python):
n = int(input())
i = 1
ans = ''

if n == 0:
    print(0)
    exit()

while n != 0:
    if  n%(2**i) != 0:
        n -= (-2)**(i-1)
        ans += '1'

    else:
        ans += '0'
    i += 1
    
print(int(ans[::-1]))

Solution (Python):
n = int(input())
binary = []
flag = 0

if n == 0:
    print(0)
    flag = 1
    
while n != 0:
    if n % -2 != 0:
        binary.append('1')
        n = n // -2 + 1
    else:
        binary.append('0')
        n = n // -2

binary.reverse()

if flag == 0:
    print(''.join(binary))

Solution (Python):
n = int(input())

if n == 0:
    print(n)
    exit(0)

t   = 0
idx = 0
max = 0

if n > 0 :
    while True:
        max = idx
        t   += 2**idx
        idx  = idx + 2
        
        if t >= n :
            break
else:
    idx = 1
    while True:
        max = idx
        t   += -2**idx
        idx  = idx + 2
        
        if t <= n :
            break



ans = ''
s   = 0
for i in range(max+1):
    idx = 0

    sidx = (i-1)//2
    t = 1

    if i > 0 :
        start = 1
        for j in range(sidx):
            t *= 4
            start += t
    else:
        start = 0
    
    t = (n - start)/(2**i)

    if t - (n - start)//(2**i)  > 0 :
        t = (n - start)//(2**i) + 1
    else :
        t = (n - start)//(2**i)   

    if t % 2 == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans

        if i % 2 == 0 :
            s += 2**i
        else:
            s -= 2**i

print(ans)

Solution (Python):
n = int(input())
s=''
while n!=0:
	s=str(n%2)+s
	n=-(n//2)
print(s*(s!='') or 0)

Solution (Python):
N=int(input())
if N==0:
    print(0)
else:
    P=0
    M=0
    A=[0 for i in range(33)]
    for j in range(33):
        if N==0:
            break
        else:
            for i in range(33):
                if i%2==0:
                    if 0<=N and N<=(((-2)**i)+P):
                        break
                    else:
                        P+=(-2)**i
                elif i%2==1:
                    if N<=0 and (((-2)**i)+M)<=N:
                        break
                    else:
                        M+=(-2)**i
            A[i]=1
            N-=(-2)**i
            P=0
            M=0
    A=A[::-1]
    ans=0
    for k in range(33):
        ans+=A[k]*(10**(32-k))
    print(ans)

Solution (Python):
N = int(input())
binarys = []
flag = 0

if N == 0:
    print(0)
    flag = 1
    
while N != 0:
    if N % -2 != 0:
        binarys.append('1')
        N = N // -2 + 1
    else:
        binarys.append('0')
        N = N // -2

binarys.reverse()

if flag == 0:
    print(''.join(binarys))

Solution (Python):

n = int(input())
if n==0:
    print(0)
    exit()
s = []

while n != 0:
    x = n%-2
    if x<0:
        s.append("1")
        n = n//-2 +1
    else:
        s.append("0")
        n = n//-2
s.reverse()
print("".join(s))

Solution (Python):
n = int(input())

ans = []
while n != 0:
    if n % -2 == -1:
        n -= 1
        ans += ['1']
    else:
        ans += ['0']
    n //= -2
ans.reverse()
if len(ans) == 0:
    print(0)
else:
    print(''.join(ans))

Solution (Python):
N = int(input())

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

print(res)

Solution (Python):
N = int(input())
if N == 0:
    print('0')
    exit()
res = []
for i in range(32):
    digit = (-2) ** i
    if N % (digit * (-2)) != 0:
        N -= digit
        res.append('1')
    else:
        res.append('0')
while res[-1] == '0':
    res.pop()
print(''.join(res[::-1]))

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

Solution (Python):
N = int(input())
ans = ""
while N != 0:
    if N % 2 != 0:
        N -= 1
        ans = "1" + ans
    else:
        ans = "0" + ans
    N = N // (-2)
if ans == "":
    ans = "0"
print(ans)

Solution (Python):
n=int(input())
ans=""
while n!=0:
    if n%2!=0:
        n-=1
        ans="1"+ans
    else:
        ans="0"+ans
    n=-n>>1
print(ans if ans!="" else 0)

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

Solution (Python):
N = input()

ans = ""

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

  if N == 0:
    print (0)
    break

Solution (Python):
n = int(input())
ans = ''

while n != 0:
    if n%(-2) == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans
        n -= 1
    n = n / (-2)

if ans == '':
    ans = '0'
print(ans)

Solution (Python):
N = int(input())
result = ''
if N == 0:
    result = '0'
else:    
    while N != 0:
        if N % 2 == 1 :
            result = '1' + result
            N -= 1
        else:
            result = '0' + result
        N = -N//2

print(result)

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

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

Solution (Python):
import sys
n = int(input())

if n == 0:
    print(0)
    sys.exit()

ans = []
x = 2
i = 0
while n != 0:
    if n%x!=0:
        ans.append(1)
        n = n - (-2)**i
    else:
        ans.append(0)    
    i += 1
    x *= 2 
print(''.join([ str(x) for x in ans[::-1]]))

Solution (Python):
import sys
N = int(input())
result = ""
if N == 0:
    print(0)
    sys.exit()
while N != 1:
    if N == -2:
        N = 10
        break
    result += str(N%2)
    if N%2:
        N = N//(-2) +1
    else:
        N = N//(-2)
print(str(N) + result[::-1])

Solution (Python):
N=int(input())
if N==0:
    print(0)
s=""
while N:
    if N%2==1:
        s="1"+s
        N-=1
    else:
        s="0"+s
    N=-N//2
print(s)

Solution (Python):
x=int(input())

LIST2=[1]
LIST2X=[-2]

N=1
for i in range(1,30):
    N=N+4**i
    LIST2.append(N)
N=-2
for i in range(1,30):
    N=N-2*4**i
    LIST2X.append(N)



LIST=[0]*60

def nex(N):
    if N>0:
        for i in range(30):
            if N<=LIST2[i]:
                break
        LIST[i*2]+=1
        return N-(-2)**(i*2)

    if N<0:
        for i in range(30):
            if N>=LIST2X[i]:
                break
        LIST[i*2+1]+=1
        return N-(-2)**(i*2+1)

while x!=0:
    x=nex(x)
    

for i in range(59,-1,-1):
    if LIST[i]==1:
        break

for j in range(i,-1,-1):
    print(LIST[j],end="")

Solution (Python):
N = int(input())

if N == 0:
    print(0)
    exit()

ans = ''
while N:
    if N%2:
        N -= 1
        ans += '1'
    else:
        ans += '0'
    N //= -2

print(ans[::-1])

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def n_based(n:int, base:int) -> str:
    if n == 0:
        return "0"
    
    ans = ""
    res = n
    
    while abs(res) > 0:
        q = res%base
        if q>=0:
            ans = str(q) + ans
            res //= base
        else:
            q += abs(base)
            ans = str(q) + ans
            res //= base
            res += 1
        
    return ans

n = ni()
print(n_based(n,-2))

Solution (Python):
import math


n = int(input())
if n == 0:
    print(0)
    exit()
out = ""
i = 0
while n != 0:
    if n % -2 != 0:
        out = str(- (n % -2)) + out
        
    else:
        out = str(- (n % -2)) + out

    
    if n > 0:
        n = int(n / (-2))
    else:
        n = math.ceil(n / (-2))
    i += 1
print(out)

Solution (Python):
import math

n = int(input())
if n == 0:
    print(0)
    exit()
out = ""
i = 0
while n != 0:
    if n % -2 != 0:
        out = str(- (n % -2)) + out
        
    else:
        out = str(- (n % -2)) + out

    
    if n > 0:
        n = int(n / (-2))
    else:
        n = math.ceil(n / (-2))
    i += 1
print(out)
"""
tmp = 1
digit = 0
while tmp < n:
    tmp *= 4
    digit += 1
number = [0 for i in range(digit)]
print(number)
tmp = n
for i in range(digit):
    if 0 < tmp % 4 < 4:
        number[i] = tmp % 4
        tmp = int(tmp / 4)
"""

Solution (Python):
n = int(input())
if n == 0:
    print(0)
    exit()
out = ""
i = 0
while n != 0:
    if n % -2 != 0:
        out = str(- (n % -2)) + out
        n += n % -2
        
    else:
        out = str(n % 2) + out
    n = int(n / (-2))
    i += 1
print(out)
"""
tmp = 1
digit = 0
while tmp < n:
    tmp *= 4
    digit += 1
number = [0 for i in range(digit)]
print(number)
tmp = n
for i in range(digit):
    if 0 < tmp % 4 < 4:
        number[i] = tmp % 4
        tmp = int(tmp / 4)
"""