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 logging
import time


class Solver:
    def __init__(self):
        self.n = 0

    
    def input_value(self):
        
        
        
        
        
        self.n = int(input())

    @staticmethod
    def sigma(n):
        x = 0
        if n % 2 == 0:
            for i in range(0, n + 1, 2):
                x += (-2) ** i
        else:
            for i in range(1, n + 1, 2):
                x += (-2) ** i
        return x

    @staticmethod
    def to_base_m2(n):
        
        if n == 0:
            return '0'

        MAX_BIT = 35
        s = ''
        i = MAX_BIT
        while i >= 0:
            if i % 2 == 0:
                if Solver.sigma(i - 2) < n <= Solver.sigma(i):
                    s = s + '1'
                    n -= (-2) ** i
                else:
                    s = s + '0'
            elif i % 2 == 1:
                if Solver.sigma(i) <= n < Solver.sigma(i - 2):
                    s = s + '1'
                    n -= (-2) ** i
                else:
                    s = s + '0'
            i -= 1
        while s[0] == '0':
            s = s[1:]
        return s

        



    
    
    
    

    @staticmethod
    def test():
        start_time = time.time()

        assert Solver.sigma(2) == 5, 'Error.'
        assert Solver.sigma(3) == -10, 'Error.'
        assert Solver.to_base_m2(9) == '11001', 'Error.'
        assert Solver.to_base_m2(-9) == '1011', 'Error.'
        assert Solver.to_base_m2(123456789) == '11000101011001101110100010101', 'Error.'
        assert Solver.to_base_m2(0) == '0', 'Error.'
        assert Solver.to_base_m2(1) == '1', 'Error.'
        assert Solver.to_base_m2(2) == '110', 'Error.'
        assert Solver.to_base_m2(-1) == '11', 'Error.'
        assert Solver.to_base_m2(-2) == '10', 'Error.'

        elapsed_time = time.time() - start_time
        logging.debug('elapsed_time: {0}'.format(elapsed_time) + '[sec]')


if __name__ == '__main__':
    logging.basicConfig(level=logging.DEBUG)

    solver = Solver()

    

    solver.input_value()
    ans = solver.to_base_m2(solver.n)
    
    print(ans)

Solution (Python):


N = int(input())
moto = []
if N ==0:
    moto.append(0)
else:
    while N != 0:
        amari = (N % -2)*-1
        moto.append(amari)
        N = int((N - amari) /-2)
ans = moto[::-1]
for i in ans:
    print(i,end="")

Solution (Python):
def m(K):return str(K) if K*K==K else m(-(K-K%2)//2)+str(K%2)
print(m(int(input())))

Solution (Python):
n = int(input())
b = ''
while True:
    if 0 <= n <= 1:
        b += str(abs(n))
        break
    b += str(n % 2)
    n = (n - n % 2) // (-2)
print(b[::-1])

Solution (Python):
N=int(input());S=""
while 1:
 if N*N==N:S+=str(N);break
 S+=str(N%2);N=(N-N%2)//(-2)
print(S[::-1])

Solution (Python):
N=int(input());S=""
while(True):
  if N*N==N:S+=str(N);break
  S+=str(N%2);N=(N-N%2)//(-2)
print(S[::-1])

Solution (Python):
def m(K):return str(K) if K*K==K else m(-(K-K%2)//2)+str(K%2)
print(m(int(input())))

Solution (Python):
def m(K):return "1" if K==1 else "0" if K==0 else m(-(K-K%2)//2)+str(K%2)
print(m(int(input())))

Solution (Python):
def m(K):return "1" if K==1 else "0" if K==0 else m(-(K-K%2)//2)+("1" if K%2 else "0")
print(m(int(input())))

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

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

Solution (Python):
N = int(input())
rangeList = [[0, 1], [-1, -2]]
for i in range(30): 
    a = (-2) ** (i+2)
    rangeList.append([a+rangeList[i+1][1], a+rangeList[i][1]])

maxPower = 0
for i in range(len(rangeList)):
    if min(rangeList[i]) <= N <= max(rangeList[i]):
        maxPower = i
        break
    
S = ""
sum = 0
for i in range(maxPower+1):
    mod = N % (2 ** (i+1))
    if mod - sum == 2 ** i:
        S = "1" + S
        sum += (-2) ** i
    else:
        S = "0" + S

print(int(S))

Solution (Python):

n = int(input())
if n == 0:
    print(0)
    exit
ans = ''
ans_n = 0

for i in range(1, 100):
    if n == ans_n:
        print(ans[::-1])
        exit()
    if (n - ans_n) % (2 ** i) == 0:
        ans += '0'
    else:
        ans += '1'
        ans_n += (-2) ** (i - 1)

Solution (Python):
def solve(n):
    ret = ""
    i = 0  
    while True:
        if i % 2 == 1 and n % 2 == 1:  
            n += 2
        ret += str(n % 2)
        n //= 2  
        i += 1
        if n == 0:
            break
    return ret[-1::-1]  


n = int(input())
if n == 0:
    print(0)
elif n < 0:  
    n *= -2
    print(solve(n)[:-1])
else:
    print(solve(n))

Solution (Python):
import bisect


def put(a, b):  
    l = max(len(a), len(b))  
    a = "0" * l + a
    b = "0" * l + b
    s = ""
    for i in range(-1, -l-1, -1):  
        s += a[i] + b[i]
    s = s[-1::-1]  
    print(s[s.find("1"):])  


def quad(i):  
    s = ""
    while i > 0:
        s += str(i % 4)
        i //= 4
    return s[-1::-1]


l = [0, 1]
for i in range(1, 20):  
    l += [4 ** i + j for j in l]

n = int(input())
if n == 0:  
    print("0")
else:
    for i in range(len(l)):
        ind = bisect.bisect_left(l, (l[i] - n) // 2)
        if l[i] - 2 * l[ind] == n:
            put(quad(l[i]), quad(l[ind]))
            break

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

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

if(s==""):
    print("0")
else:
    print(s)

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

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

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

    ans = '1' + ans

    print(ans)

Solution (Python):
import bisect
def put(a,b): 
    l=max(len(a),len(b)) 
    a="0"*l+a
    b="0"*l+b
    s=""
    for i in range(-1,-l-1,-1): 
        s+=a[i]+b[i]
    s=s[-1::-1] 
    ind=s.find("1")
    print(s[ind:]) 

def quad(i): 
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,20): 
    l+=[4**i+j for j in l]

n=int(input())
if n==0: 
    print("0")
else:
    for i in range(len(l)):
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Solution (Python):
def solve(n):
    ret=""
    i=0 
    while True:
        if i%2==1 and n%2==1: 
            n+=2
        ret+=str(n%2)
        n//=2 
        i+=1
        if n==0:
            break
    return ret[-1::-1] 

n=int(input())
if n==0:
    print(0)
elif n<0: 
    print(solve(n*(-2))[:-1])
else:
    print(solve(n))

Solution (Python):
def solve(n):
    ret=""
    i=0
    while True:
        if i%2==1 and n%2==1: 
            n+=2
        ret+=str(n%2)
        n//=2
        if n==0:
            break
        i+=1
    return ret[-1::-1] 

n=int(input())
if n==0:
    print(0)
elif n<0: 
    print(solve(n*(-2))[:-1])
else:
    print(solve(n))

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

Solution (Python):

from math import ceil
n = int(input())

ret = ""

while n!=0:
    r = ceil(n/-2)
    if n!=r*-2:
        ret += "1"
    else:
        ret += "0"
    n = r

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

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):
import bisect
def put(a,b): 
    l=max(len(a),len(b)) 
    a="0"*l+a
    b="0"*l+b
    s=""
    for i in range(-1,-l-1,-1): 
        s+=a[i]+b[i]
    s=s[-1::-1] 
    ind=s.find("1")
    print(s[ind:]) 

def quad(i): 
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18): 
    l+=[4**i+j for j in l]

n=int(input())
if n==0: 
    print("0")
else:
    for i in range(len(l)):
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Solution (Python):
n = int(input())
n2 = n
ans = ""
for i in range(100):
    while n != 0:
        r = (n % 2)
        n = (n - r) // (-2)
        ans = str(r) + ans
if n2==0:
    print("0")
else:
    print(ans)

Solution (Python):
n = int(input())
n2 = n
ans = ""
for i in range(100):
    while n != 0:
        r = (n % 2)
        n = (n - r) // (-2)
        ans = str(r) + ans
if n2==0:
    print("0")
else:
    print(ans)

Solution (Python):
import bisect
n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    x = 1    
    for j in range(16):
        if (i >> j) & 1:

            temp += x
        x *= 4
    ps[i] = temp

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    x = 2
    for j in range(16):
        if (i >> j) & 1:

            temp2 += x
        x *= 4
    n2 = n + temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1] == n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Solution (Python):
import bisect
n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    x = 1    
    for j in range(16):
        if (i >> j) & 1:

            temp += x
        x *= 4
    ps[i] = temp

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    x = 2
    for j in range(16):
        if (i >> j) & 1:

            temp2 += x
        x *= 4
    n2 = n + temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1] == n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Solution (Python):
import bisect
n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    x = 1    
    for j in range(16):
        if (i >> j) & 1:

            temp += x
        x *= 4
    ps[i] = temp

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    x = -2
    for j in range(16):
        if (i >> j) & 1:

            temp2 += x
        x *= 4
    n2 = n - temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1] == n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Solution (Python):
N = int(input())
s = []
while True:
    if N % 2 :
        s.append("1")
        N -= 1
    else:
        s.append("0")
    N /= -2
    if N == 0:
        break
s.reverse()
print("".join(s))

Solution (Python):
import bisect
n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    for j in range(16):
        if (i >> j) & 1:
                temp += (-2) ** (2 *j)
    ps[i] = temp

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    for j in range(16):
        if (i >> j) & 1:
                temp2 += (-2) ** (2 *j + 1)
    n2 = n - temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1] == n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Solution (Python):
import bisect

n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    for j in range(16):
        if (i >> j) & 1:
                temp += (-2) ** (2 *j)
    ps[i] = temp

"""
for index, value in enumerate(ps):
    print(bin(index)[2:].zfill(16), value)
"""

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    for j in range(16):
        if (i >> j) & 1:
                temp2 += (-2) ** (2 *j + 1)
    n2 = n - temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1]==n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

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

s = []

while True:
    if (N % 2):
        s.append( str(1) )
        N -= 1
    else:
        s.append (str(0))
        N = N
    N /= -2
    if (N == 0):
        break
    
s.reverse()
s = "".join(s)

print (s)

Solution (Python):
import sys

sys.setrecursionlimit(10000) 

l1 = sys.stdin.readline().strip()
N = int(l1.strip())
B = bin(N)





M = N
C = 0
i = 0


if M == 0:
	C = 0

while M > 0:
	now = M % 2

	M = int(M/2) 
	
	
	if now != 0:
		C += pow(2,i)
	
	
	if i%2 == 1:
		
		
		if now != 0:
			M += 1 
	i += 1

while M < 0:
	now = M % 2

	M = int(M/2) 
	
	
	if now != 0:
		C += pow(2,i)
	
	
	if i%2 == 0:
		
		
		if now != 0:
			M -= 1 
	i += 1



res = bin(C)[2:]

print(res)

Solution (Python):
import math

n = int(input())

a = []
if n==0:
  a.append('0')
while n!=0:
  if n%2 == 0:
    a.append('0')
  else:
    a.append('1')
    n-=1
  n //= -2

print(''.join(a[::-1]))

Solution (Python):
def determine_digit(digit_num, acm, n):
    mod = 2 ** (digit_num + 1)
    if (n - acm) % mod:
        return 1
    else:
        return 0


def convert(n):
    if n == 0:
        return '0'

    result = ''
    acm = 0
    digit_num = 0
    
    while n != acm:
        
        d = determine_digit(digit_num, acm, n)
        

        
        acm += d * (-2)**digit_num
        digit_num += 1
        result += str(d)

    return result[::-1]


if __name__ == "__main__":
    n = int(input())

    print(convert(n))

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

a = []

if n > 0:
    while n > 0:
        a.append(n % 2)
        n //= 2

    a.append(0)
    a.append(0)
    for i in range(len(a) - 1):
        if i % 2 == 1:
            if a[i] == 1:
                a[i + 1] += 1
            elif a[i] == 2:
                a[i + 1] += 1
                a[i] = 0
        else:
            if a[i] == 2:
                a[i + 1] += 1
                a[i] = 0

    for i in range(len(a)):
        a[i] = str(a[i])
    for i in range(len(a) - 1, -1, -1):
        if a[i] == '0':
            a[i] = ''
        else:
            break
    print(''.join(reversed(a)))
elif n == 0:
    print('0')
else:
    n = 0 - n
    while n > 0:
        a.append(n % 2)
        n //= 2

    a.append(0)
    a.append(0)
    for i in range(len(a) - 1):
        if i % 2 != 1:
            if a[i] == 1:
                a[i + 1] += 1
            elif a[i] == 2:
                a[i + 1] += 1
                a[i] = 0
        else:
            if a[i] == 2:
                a[i + 1] += 1
                a[i] = 0

    for i in range(len(a)):
        a[i] = str(a[i])
    for i in range(len(a) - 1, -1, -1):
        if a[i] == '0':
            a[i] = ''
        else:
            break
    print(''.join(reversed(a)))

Solution (Python):
import bisect
def put(a,b):
    l=max(len(a),len(b))
    a="0"*l+a
    b="0"*l+b
    s=""
    for i in range(-1,-l-1,-1):
        s+=a[i]+b[i]
    s=s[-1::-1]
    ind=s.find("1")
    print(s[ind:])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
if n==0:
    print(0)
else:
    for i in range(len(l)):
        if (n-l[i])%2==0:
            ind=bisect.bisect_left(l,(l[i]-n)//2)
            if l[i]-2*l[ind]==n:
                put(quad(l[i]),quad(l[ind]))
                break

Solution (Python):
def main():
    """
    S: N の -2進数表現の条件

    1: S 0/1 からのみなる文字列
    2: S ='0' でなければSの先頭の文字は'1'
    3: S=S_k S_k-1...S_0
        S_0 * (-2)^0 + S_1 * (-2)^1 + ... + S_k * (-2)^k = N
    """
    N = int(input())
    ans = editorial_movie(N)
    
    
    print(ans)


def TLE(N):
    if N == 0:
        return 0

    n_bit = 16 * 2
    for i in range(1, 2 ** n_bit):
        s = 0
        bits = []
        for j in range(n_bit):
            bit = (i & (1 << j))
            on = int(bit != 0)
            s += on * ((-2) ** j)
            bits.append(str(on))

        

        if N == s:
            bits = bits[::-1]
            for k, b in enumerate(bits):
                if b == "1":
                    return "".join(bits[k:])

    return ""


def my_bin(N):
    if N == 0:
        return "0"

    ans = ""
    while N > 0:
        if N % 2 == 0:
            ans += "0"
        else:
            ans += "1"
        N //= 2

    return ans[::-1]


def editorial_movie(N):
    """
    桁: 可能数値: 範囲
    0:  1,  0 ~ +1
    1: -2, -2 ~ +1,  -2: 0-2, -1:1-2
    2:  4, -2 ~ +5,   2:-2+4, 3:-1+4, ...
    といった感じで全範囲カバー可能

    -2進数なので、基数は-2
    10進数を2進数に変換するとき、2(基数)で割る
    ただし、実装では調整が必要
    """
    if N == 0:
        return "0"

    ans = ""
    while N != 0:
        if N % 2 == 0:
            ans += "0"
        else:
            
            
            
            
            
            
            
            
            
            
            N -= 1
            ans += "1"

        N //= -2

    return ans[::-1]


def f(N):
    """
    bit全探索
    """
    if N == 0:
        return 0

    if N > 0:
        i = 0
    else:
        i = 1

    ans = 0
    while True:
        if N > 0 and (-2) ** i >= N:
            break
        elif N < 0 and (-2) ** i <= N:
            break
        i += 2

    print(2 ** i)

    return ans


if __name__ == '__main__':
    main()

Solution (Python):
import itertools
import sys
sys.setrecursionlimit(10000)

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

    if n == 0:
        print(0)
        return

    s = ''
    m = n
    while m != 0:
        if m % 2 == 0:
            s += '0'
        else:
            s += '1'
            m -= 1

        m //= -2

    print(s[::-1])

if __name__ == '__main__':
    main()

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

lft = 0
rgt = 1
ret = [(0, 0, 0), (0, 1, 0)]
for i in range(1, 32):
    if i % 2 != 0:
        lft -= 2**i
        ret.append((lft, rgt, i))
    else:
        rgt += 2**i
        ret.append((lft, rgt, i))

ret.reverse()
s = [0 for i in range(32)]
for i in range(len(ret) - 1):
    if ret[i][0] <= n <= ret[i][1] and not(ret[i+1][0] <= n <= ret[i+1][1]):
        n -= (-2) ** ret[i][2]
        s[i] = 1

for i in range(len(s)):
    if s[i] == 1:
        break

for j in range(i, len(s)):
    print(s[j], end='')
print()

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

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

Solution (Python):
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 = int(input())
print(n_based(N, -2))

Solution (Python):



def solve():
    n = int(input())
    ans, m = "", 1
    while n != 0:
        m *= (-2)
        if abs(n) % abs(m) > 0:
            ans += "1"
            n -= m // (-2)
        else:
            ans += "0"
    print(ans[::-1] if ans else 0)

if __name__=="__main__":
    solve()

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

Solution (Python):
def minus2(K):
    if K==1:
        return "1"
    if K==0:
        return "0"
    S=""
    if K%2==1:
        S="1"
    else:
        S="0"
    K-=K%2
    return minus2(-K//2)+S

print(minus2(int(input())))

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

ma = 50
result=[]
for i in range(ma):
  if n==((-2)**i):
    result.append("1")
    break
  
  if (n%(2**(i+1)))==0:
    result.append("0")
  else:
    result.append("1")
    n-=((-2)**i)

result.reverse()
head=0
for x in result:
  if x=="1":
    break
  if x=="0" and (len(result)-1)>head:
    head+=1

print("".join(result[head:]))

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

while 1:
  r=q%(-2)
  if q==0:
    b.append(0)
    break
 
  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)

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

print(ans)

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

n = N
result = ""
for k in range(K_MAX):
    sign = (-1) ** k
    if n % 2 == 1:
        n = n - sign
        result = "1" + result
    elif n != 0:
        result = "0" + result
    else:
        break        
    n = n / 2
if len(result) == 0: result = "0"

print(result)

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

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

print(ans)

Solution (Python):
import numpy as np

def SolveNegBinary(N):
    if N == 0:
        print "0"
    else:
        r = N
        
        ansTrue = []

        while r != 0:
            ind = (- np.sign(r) + 1)/2
            s = (-2)**ind
            while np.abs(s) < np.abs(r):
                ind +=2
                s += (-2)**ind

            ansTrue.insert(0,ind)
            r = r - (-2)**ind

        disAnswer = ""
        for k in range(ansTrue[-1] + 1)[::-1]:
            if k in ansTrue:
                disAnswer += "1"
            else:
                disAnswer += "0"


        print disAnswer
    

N = input()
SolveNegBinary(N)

Solution (Python):


N = int(input())

m = -2
S = []
while(N):
    Nm = abs(N) % abs(m)
    S.append("1" if Nm else "0");
    if Nm:
        N = N - m / (-2)
    m = m * -2

S = "".join(reversed(S))
print("0" if S == "" else S)

Solution (Python):
import math
a = int(input())


if a == 0:
    print('0')
    exit(0)

used = []
i = 0
while a != 0:
    if a % 2 == 1:
        used.append(True)
        if i % 2 == 0:
            a -= 1
        else:
            a += 1
    else:
        used.append(False)
    a = a // 2
    i += 1


ans = ''
for elem in reversed(used):
    if elem:
        ans += '1'
    else:
        ans += '0'

print(ans)

Solution (Python):
def f(n):
    s=""
    while n>0:
        s=str(n%2)+s
        n//=2
        if n==0:
            break
        if n%2==1:
            n+=2
            s="1"+s
        else:
            s="0"+s
        n//=2
    return s

n=int(input())
if n==0:
    print(0)
elif n<0:
    print(f(n*(-2))[:-1])
else:
    print(f(n))

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

S = ""
if N != 0:
    while N != 0:
        remainder = N % -2
        if remainder < 0:
            remainder += 2
            N = (N // -2) + 1
        else:
            N //= -2
        S = str(remainder) + S
else:
    S = "0"

print(S)

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


ans = ""
divide = 1

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

print(ans)

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


ans = ""
divide = 1

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

print(ans)

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

if N % 2 == 0:
    A = "0" + A
else:
    A = "1" + A
    N -= 1

n = -2
while N != 0:
    if N == n:
        A = "1" + A
        break
    if N % ( n * 2 ) == 0:
        A = "0" + A
    else:
        A = "1" + A
        N -= n
    n *= -2

print(A)

Solution (Python):

n = int(input())

if n == 0:
    print(0)

else:
    s = ''
    cnt = 1
    while n != 0:
        s += str(1) if n % (-2)**cnt != 0 else str(0)
        n -= (-2)**(cnt - 1) if n % (-2)**cnt != 0 else 0
        cnt += 1
    print(s[::-1])

Solution (Python):
n=int(input())
a=[]
k=0

if n==0:
    print(0)

while k<1:
    if n==0:
        k=1
    else:
        if n%2==0:
            a.append(0)
            n=n/(-2)
        else:
            a.append(1)
            n=(n-1)/(-2)
            
for i in (reversed(a)):
    print(i,end="")

Solution (Python):
n=int(input())
a=[]
k=0

if n==0:
    print(0)

while k<1:
    if n==0:
        k=1
    else:
        if n%2==0:
            a.append(0)
            n=n/(-2)
        else:
            a.append(1)
            n=(n-1)/(-2)
            
for i in (reversed(a)):
    print(i,end="")

Solution (Python):
N=int(input())
out=[]
if N==0:
    out.append(0)
else:
    while abs(N)>0:

        if N%2==1:
            out.append(-1)
        else:
            out.append(0)
        N=int(N//-2)
for i in range(len(out)-1):
    if out[i]==-1:
        out[i]=1
        out[i+1]+=1

if out[len(out)-1]==-1:
    out[len(out)-1]=1
    out.append(1)
out.reverse()
if len(out) is not 1:
    while out[0]==0:
        del out[0]


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

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())

if N == 0:
    print(0)
    exit

bits = ''
rest = N
while rest != 0:
    if rest % 2 == 0:
        bits = '0' + bits
        rest = rest // -2
    else:
        bits = '1' + bits
        rest = (rest - 1) // -2

print(bits)

Solution (Python):
n = int(input())
b2 = []
while n != 0:
    rem = n % -2
    n //= -2
    if rem == -1:
        rem = 1
        n += 1
    b2.insert(0, rem)

if len(b2) == 0:
    print(0)
else:
    print(str(b2).replace("[", "").replace("]", "").replace(", ", ""))

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

temp = N
result = []

while temp != 0:
    if temp % 2 == 0:
        ans = 0
    else:
        ans = 1
    temp = (temp - ans) // (-2)
    result.append(str(ans))
result.reverse()
if N == 0:
    print(0)
else:
    print("".join(result))

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

ans=[]

while True:
  if N%2==0:
    ans.append("0")
    N//=(-2)
  else:
    ans.append("1")
    N=(N-1)//(-2)
    
  if N==-1:
    ans.append("11")
    break
  elif N==1:
    ans.append("1")
    break
  elif N==0:
    break

ans.reverse()
print("".join(ans))

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

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

t = -2

while N != 0:
	if N - t == 0:
		ans = '1' + ans
		break
	if N % (abs(t) * 2) == 0:
		ans = '0' + ans
	else:
		ans = '1' + ans
		N -= t
	t *= -2

print(ans)

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

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

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

ans = ''
N = N * (-1)
while N :
    m = abs(N%2)
    ans = ans + str(m)
    N = (N // (-2))
    

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

Solution (Python):



def main():
    from math import ceil
    n = int(input())
    ans = ''

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

    while n != 0:
        mod_n = ceil(n / (-2))
        ans += str(n - mod_n * (-2))
        n = mod_n

    print(ans[::-1])


if __name__ == '__main__':
    main()

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

Solution (Python):

N = int(input())




ans = ""
while N != 0:
    
    if N % 4 == 0:
        ans = "00" + ans
        N -= 0
    elif N % 4 == 1:
        ans = "01" + ans
        N -= 1
    elif N % 4 == 2:
        ans = "10" + ans
        N -= -2
    else:
        ans = "11" + ans
        N -= -1
    N = int(N / 4)
    
for i in range(len(ans)):
    if ans[i] != "0":
        print(ans[i:])
        break
else:
    print(0)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    if n == 0:
        return 0
    r = []
    i = 0
    while n != 0:
        ii = 2**(i+1)
        if n % ii != 0:
            r.append('1')
            if i % 2 == 0:
                n -= ii // 2
            else:
                n += ii // 2
        else:
            r.append('0')
        i += 1
    return ''.join(r[::-1])




print(main())