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):
N = int(input())
ans = ''
for _ in range(1000):
    r = N % 2
    if r < 0:
        r += 2
    N = (N-r)//(-2)
    ans = str(r) + ans
print(int(ans))

Solution (Python):


from itertools import dropwhile
from collections import deque
n=int(input())
ans=deque([["",n]])
def bfs(d):
    global ans
    l=len(ans)
    for i in range(l):
        x=ans.popleft()
        new1=[x[0]+"0",x[1]]
        if abs(new1[1])<abs((-2)**d):
            ans.append(new1)
        new2=[x[0]+"1",x[1]-(-2)**d]
        if abs(new2[1])<abs((-2)**d):
            ans.append(new2)
    if d!=0:
        bfs(d-1)
bfs(32)


for i in ans:
    if i[1]==0:
        ans=list(dropwhile(lambda x:x=="0",i[0]))
        if len(ans)==0:
            print(0)
        else:
            print("".join(ans))
        break

Solution (Python):
def main():
    N = int(input())
    S = list()
    pow_m2, mod = 1, 2
    S.append(N % mod)
    N -= (N % mod) * pow_m2
    while N != 0:
        pow_m2 *= (- 2)
        mod *= 2
        s = 1 if N % mod > 0 else 0
        S.append(s)
        N -= s * pow_m2
    S.reverse()
    print(''.join(map(str, S)))


if __name__ == '__main__':
    main()

Solution (Python):
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 = 1000

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

    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):
        b = bit[i]
        if b > 1:
            b1 = bit[i+1]
            if b1 > 0:
                if b1 >= b//2:
                    bit[i+1] -= b//2
                    bit[i] = b % 2
                else:
                    bit[i+1] = 0
                    bit[i] -= b1 * 2
            if bit[i] > 1:
                bit[i+2] += bit[i] // 2
                bit[i+1] += bit[i] // 2
                bit[i] = bit[i] % 2

    bit.reverse()
    i = bit.index(1)
    print(*bit[i:],sep='')

if __name__ == '__main__':
    main()

Solution (Python):
import sys

N = int(input())
if not N:
    print(0)
    sys.exit()
    
S = ''

while N:
    r = N%2
    N = N//(-2)+r
    S += str(r)

print(S[::-1])

Solution (Python):
import bisect
import heapq  

inf = 10 ** 15
mod = 10 ** 9 + 7

p = [] 
m = [] 
prep = 0
prem = 0
kaijou = []
for i in range(0,35,2):
    p.append(2**i+prep)
    m.append(2**(i+1)+prem)
    kaijou.append(2**i)
    kaijou.append(2**(i+1))
    prep = 2**i+prep
    prem = 2**(i+1)+prem

def getAns(n,i):

    if i == 0:
        if n == 0:
            return '0'
        if n == 1:
            return '1'
    else:
        if n == 0 or n == 1:
            return ''.join(['0', getAns(n, i-1)])
        elif n > 0:
            ind = bisect.bisect_left(p, n)
            if ind*2 == i:
                n -= kaijou[i]
                return ''.join(['1', getAns(n, i-1)])
            else:
                return ''.join(['0', getAns(n, i-1)])
        else:
            ind = bisect.bisect_left(m, abs(n))
            if ind*2+1 == i:
                n += kaijou[i]
                return ''.join(['1', getAns(n, i-1)])
            else:
                return ''.join(['0', getAns(n, i-1)])


n = int(input())
if n >= 0:
    ind = bisect.bisect_left(p, n)
    print(getAns(n,ind*2))
else:
    ind = bisect.bisect_left(m, abs(n))
    print(getAns(n,ind*2+1))

Solution (Python):
def main():
    N = int(input())
    if N == 0:
        return 0
    l = set()
    while N != 0:
        if N > 0:
            r = plus(N)
            l.add(r)
            N -= pow(2, r)
        else:
            r = minus(N)
            l.add(r)
            N += pow(2, r)
    s = [0] * (max(l)+1)
    for i in range(max(l)+1):
        if i in l:
            s[i] = 1
    s.reverse()
    return ''.join(str(i) for i in s)
def plus(N):
    p = 0
    n = 0
    while True:
        p += pow(2, n)
        if p >= N:
            break
        n += 2
    return n
def minus(N):
    p = 0
    n = 1
    while True:
        p -= pow(2, n)
        if p <= N:
            break
        n += 2
    return n

print(main())

Solution (Python):
from itertools import product
def main():
    N = int(input())
    if N == 0:
        return 0
    l = set()
    while N != 0:
        if N > 0:
            r = plus(N)
            l.add(r)
            N -= pow(2, r)
        else:
            r = minus(N)
            l.add(r)
            N += pow(2, r)
    s = [0] * (max(l)+1)
    for i in range(max(l)+1):
        if i in l:
            s[i] = 1
    s.reverse()
    return ''.join(str(i) for i in s)
    
    
    
    
    
    
    
    
def plus(N):
    p = 0
    n = 0
    while True:
        p += pow(2, n)
        if p >= N:
            break
        n += 2
    return n
def minus(N):
    p = 0
    n = 1
    while True:
        p -= pow(2, n)
        if p <= N:
            break
        n += 2
    return n

print(main())

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())

s = ""

while n != 0:
    r = n % 2
    s += "0" if r == 0 else "1"
    n = (n - r) // (-2)

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

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

Solution (Python):
import sys
n = int(input())
if n == 0:
  print(0)
  sys.exit()
s = ''
while n != 0:
  s += str(n % 2)
  n -= n % 2
  n //= -2
print(s[::-1])

Solution (Python):
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  if n==0:
    print(0)
    exit()
  s=1 if n>0 else 0
  n=abs(n)
  for j in range(s,31,2):
    if ((n>>j) & 1): 
      n+=pow(2,j+1)
  print(bin(n)[2:])
if __name__=='__main__':
  main()

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

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

print(ret)

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

if s == "":
    print(0)
else:
    print("".join(s[::-1]))

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

Solution (Python):


import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))




def resolve():
    N,=pin()
    n=N
    ans=[]
    a=["00","01","10","11"]
    b=[0,1,-2,-1]
    t=0
    for t in range(30):
        
        n4=n%4
        ans.append(a[n4])
        n-=b[n4]
        n//=4
        if abs(n)==0:break
        
    ans.reverse()
    if ans[0][0]=="0":ans[0]=ans[0][1]
    print(*ans,sep="")
        

resolve()

Solution (Python):
n=int(input())
s=[]
if n==0:
    s.append('0')
while n!=0:
    r=n%(-2)
    if r<0:
        r+=2
    n=(n-r)//(-2)
    s.append(str(r))
s.reverse()
print(''.join(s))

Solution (Python):
def f_10_to_m2(n):
    if n == 0:
        return 0 

    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append(0)
        else:
            digits.append(1)
            n -= base
        i += 1
        base *= -2
    return ''.join(map(str, reversed(digits)))

print(f_10_to_m2(int(input())))

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

ans = []
d = 40

t = 0
while d >= 0:
    bottom = t+(-2)**d+(-2)*(1-4**(d//2))//(-3)
    top = t+(-2)**d+(1-4**math.ceil(d/2))//(-3)
    if bottom <= N <= top:
        ans.append('1')
        t += (-2)**d
    else:
        ans.append('0')
    d -= 1

print(int(''.join(ans)))

Solution (Python):


import sys
import math





















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def calc_covered_k(num):
        """
        abs(num) > 0 の時 -> num が -2 進数表記で k + 1 桁で表現される場合 k を返す ([k] に 1 が立つことを表す)
        """
        assert(num != 0)
        if num > 0:
            return (math.ceil(math.log(3 * num + 1, 4)) - 1) * 2
        else:
            return (math.ceil(math.log(3 / 2 * abs(num) + 1, 4)) - 1) * 2 + 1
    
    n = ii()
    if n == 0:
        print(0)
    else:
        k = calc_covered_k(n)
        ans = ['0'] * (k + 1)    
        ans[k] = '1'
        n -= pow(-2, k)
        while n != 0:
            k = calc_covered_k(n)
            ans[k] = '1'
            n -= pow(-2, k)
        print(''.join(reversed(ans)))

if __name__ == "__main__":
    main()

Solution (Python):
n = int(input())
if n == 0:
    print(0)
    exit()
ans = []
while abs(n) > 0:
    ans.append(n%2)
    n = (n - (n % 2)) // -2
print(''.join(map(str, ans[::-1])))

Solution (Python):
n = int(input())
if n == 0:
    print(0)
    exit()
i = 0
ans = []
while abs(n) > 0:
    ans.append(n%2)
    
    n = (n - (n % 2)) // -2
    i += 1
print(''.join(map(str, ans[::-1])))

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

ans = []
while abs(n) > 0:
    
    
    ans.append(n%2)
    
    n = (n - n % (2 * (-1)**i)) // 2
    i += 1


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

Solution (Python):
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):
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p = i % 2
        ans += str(p)
        i = - (i // 2)

    print(ans[::-1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        ans += str(i % 2)
        i = - (i // 2)

    print(ans[::-1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p, q = divmod(i, 2)
        if q:
            ans += "1"
        else:
            ans += "0"
        i = -p

    print(ans[::-1])


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p, q = divmod(i, 2)
        if q:
            ans = "1" + ans
        else:
            ans = "0" + ans
        i = -p

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
s=''
if n==0:
    print(0)
    exit()
while n!=0:
    m=n%2
    s+=str(m)
    n=(n-m)//-2
print(int(s[::-1]))

Solution (Python):


n = int(input())
def sub(n):
    if n==0:
        return []
    k = 1
    count = 0
    pos = 1
    neg = 0
    while True:
        if (n>0 and pos>=n) or (n<0 and abs(neg)>=abs(n)):
            break
        count += 1
        k *= (-2)
        if k>0:
            pos += k
        else:
            neg += k

    return [count] + (sub(n-k) if n>0 else sub(n-k))
out = sub(n)
if not out:
    print(0)
else:
    s = ["0"] * (max(out)+1)
    for item in out:
        s[item] = "1"
    print("".join(s[::-1]))

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

    
    d = n
    bin_arr = []
    while d != 0:
        
        if d > 0:
            _d = d // 2
            bin_arr.append(d % 2)
            d = -1 * _d  
        
        else:
            _d = (abs(d) + 1) // 2
            bin_arr.append(abs(d) % 2)
            d = _d
        

    bin_str = ''.join(map(str, reversed(bin_arr)))
    print(bin_str)

abc105_c()

Solution (Python):
n = int(input())
gu = [1]
ki = [0]
for i in range(0, 20):
  gu.append(gu[-1] + (-2)**(2 + 2*i))
  ki.append(ki[-1] + (-2)**(1 + 2*i))
ans = []
for i in range(20):
  if gu[-2-i] < n <= gu[-1-i]:
    ans.append('1')
    n-= (gu[-1-i]-gu[-2-i])
  else:
    ans.append('0')
  if ki[-1-i] <= n < ki[-2-i]:
    ans.append('1')
    n -= (ki[-1-i]-ki[-2-i])
  else:
    ans.append('0')
ans.append(str(n))
print(str(int(''.join(ans))))

Solution (Python):
if __name__ == '__main__':
    N = int(input())

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

    ans = []
    cnt = 0
    while abs(N) >= 1:
        mod_val = N % ((-2) ** (cnt + 1))
        if mod_val == 0:
            ans.append(0)
        else:
            ans.append(1)
            N -= (-2) ** cnt
        cnt += 1

    print(''.join([str(val) for val in ans[::-1]]))

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

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

print(ans)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    N=int(readline())

    if N==0:
        print(0)
    else:
        nums=[]
        fugou=1  
        power=1  
        total=0
        while total!=N:
            m=N%(power*2)
            if m==total%(power*2):
                nums.append(0)
            else:
                nums.append(1)
            total+=nums[-1]*power*fugou
            fugou*=-1
            power*=2

        nums=nums[::-1]
        for i in range(len(nums)):
            print(nums[i],end="")
        print()
if __name__=="__main__":
    main()

Solution (Python):
n = int(input())
m=-2
t=0
pos=0
ans=[]
while n!=t:
  if (n-t)%m == 0:
    ans.insert(0,0)
  else:
    ans.insert(0,1)
  t+=ans[0]*(m//-2)
  m=m*(-2)

if n == 0:
  print(0)
else:
  ans = [str(n) for n in ans]
  print("".join(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())
x=""
while n != 0:
    x = str(n%2) + x
    n = -(n//2)
print(0 if x == "" else x)

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

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


ans = []
i = 1
while N:
    if N % 2 == 0:
        ans.append('0')
    else:
        ans.append('1')
        if i % 2 == 0:
            N += 1
        else:
            N -= 1
    N //= 2
    i += 1

zero = True
for b in reversed(ans):
    if zero and b == 0:
        continue
    elif b == 1:
        zero = False
    print(b, sep='', end='')
print()

Solution (Python):

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

print(ans[::-1])

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

def main():
    N = int(readline())
    if N == 0:
        print(0)
        return
    ans = []
    i = 0
    while N:
        if N % 2 == 0:
            ans.append(0)
            N //= 2
        else:
            ans.append(1)
            if i % 2 == 0:
                N -= 1
            else:
                N += 1
            N //= 2
        i += 1

    print(*ans[::-1], sep='')

if __name__ == '__main__':
    main()

Solution (Python):
from statistics import median


from fractions import gcd
from itertools import combinations 
from collections import deque
from collections import defaultdict
import bisect










import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    str_ = ""
    while n != 0:
        r = n % 2
        if r < 0:
            r += 2
        n = (n-r)//(-2)
        str_ += str(r)
    str_ = str_[::-1]
    if str_ == "":
        str_ = '0'
    print(str_)
if __name__ == '__main__':
  main()

Solution (Python):
n=int(input())
now=1
A=[]
while n!=0:
    if n%(now*2)==0:
        A.append(0)
    else:
        A.append(1)
        n-=now
    now*=-2
A=list(reversed(A))
S=""
for a in A:
    S+=str(a)
if len(S)==0:
    print(0)
else:
    print(S)

Solution (Python):
N = int(input())
def solve(N):
    if N == 0:
        return '0'
    ans = ''
    while N != 0:
        ans += str(N & 1)
        N >>= 1
        N *= -1
    return ans[::-1]
print(solve(N))

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

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

if n == 0:
    print(0)
    
else:
    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append('0')
        else:
            digits.append('1')
            n -= base

        i += 1
        base *= -2

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    res = []
    coef = 1
    while n:
        if n & 1:
            res.append('1')
            n -= coef
        else:
            res.append('0')
        coef *= -1
        n >>= 1
    res = ''.join(res[::-1]) if res else '0'
    print(res)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    res = []
    digit = 0
    while n:
        if (n >> digit) & 1:
            res.append('1')
            coef = 1 if digit & 1 == 0 else -1
            n -= coef * (1 << digit)
        else:
            res.append('0')
        digit += 1
    res = ''.join(res[::-1]) if res else '0'
    print(res)
resolve()

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

s=[]
if n%2==0:
    s.append(0)
else:
    s.append(1)
nn=n
ii=0
while nn<=-1 or 2<=nn:
    nn=(nn-s[ii])//(-2)
    if nn%2==0:
        s.append(0)
    else:
        s.append(1)
    ii+=1

ss=""
for i in range(len(s)):
    ss=str(s[i])+ss
print(ss)

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

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


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

    res = []
    while N != 0:
        r = N % 2
        if r < 0:
            r += 2
        N = (N - r) // (-2)
        res += [str(r)]
    res = res[::-1]
    if len(res) == 0:
        print(0)
    else:
        print(''.join(res))


if __name__ == '__main__':
    main()

Solution (Python):

def base_n_num(N, d):
    p = 1
    ans = []
    if N == 0:
        return [0]
    while N != 0:
        if N % (d**p) == 0:
            ans.append(0)
        else:
            ans.append(1)
            N -= (d**(p-1))
        p += 1
        if N == 0:
            break
    return reversed(ans)

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

    
    ans = base_n_num(n, -2)
    print(''.join(list(map(str, ans))))

solve()

Solution (Python):
import sys

n = int(input())

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

cur = n
S = ""

while cur != 0:
    if cur % 2 == 0:
        S = "0" + S
        cur /= -2
    else:
        S = "1" + S
        cur -= 1
        cur /= -2
print(S)

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

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

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

    while n != 0:
        s = str(abs(n % -2)) + s
        if n % -2 != 0:
            n //= -2
            n += 1
        else:
            n //= -2

    print(s)

Solution (Python):
n=int(input());r=0
while n:
 p,a,k=[(1,1,1),(-2,-2,2)][n<0]
 while abs(n)>abs(a):p*=4;a+=p;k<<=2
 r|=k;n-=p
print(bin(r)[2:])

Solution (Python):
N=int(input());r=[0]
def s(n,p=1,a=1,k=0):
 if n<0:p,a,k=-2,-2,1
 while abs(n)>abs(a):p*=4;a+=p;k+=2
 r[0]|=1<<k
 if n-p:s(n-p)
if N:s(N)
print(bin(r[0])[2:])

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


def solve(n):
    if n == 0:
        return
    if n > 0:
        p, a, k = 1, 1, 0
    else:
        p, a, k = -2, -2, 1
    while abs(n) > abs(a):
        p *= 4
        a += p
        k += 2
    while len(ans) <= k:
        ans.append(0)
    ans[k] = 1
    solve(n - p)


solve(N)
print("".join([str(x) for x in reversed(ans)]))

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


def basem2(n, ans):
    if n == 0:
        if not ans:
            ans.append(0)
        return ans
    if n > 0:
        p, a, k = 1, 1, 0
        while n > a:
            p *= 4
            a += p
            k += 2
        
    else:
        assert n < 0
        p, a, k = -2, -2, 1
        while n < a:
            p *= 4
            a += p
            k += 2
        
    while len(ans) < k + 1:
        ans.append(0)
    ans[k] = 1
    return basem2(n - p, ans)


print("".join([str(x) for x in reversed(basem2(N, []))]))

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    l=[(-2)**i for i in range(32)]
    S=[0]*34
    for i in range(16):
        S[i*2+2]=S[i*2]+l[i*2]
        S[i*2+3]=S[i*2+1]+l[i*2+1]
    ans=0
    while N!=0:
        for i in range(16):
            if abs(S[i*2+2+(N<0)])>=abs(N):
                ans|=1<<(i*2+(N<0))
                N-=l[i*2+(N<0)]
                break
    print(format(ans,'b'))

if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
s=''
if n==0:
    print(0)
    exit()
while n!=0:
    m=n%2
    s+=str(m)
    n=(n-m)//-2
print(s[::-1])

Solution (Python):

import io
import math

data = int(input())
result=""
counter=1
if data==0:
	result="0"
while data:
	t=counter
	counter*=-2
	if data%counter:
		data-=t
		result+="1"
	else:
		result+="0"
print(result[::-1])

Solution (Python):
n=int(input())
ans=""
i=0
if n==0:
    print(0)
    exit()

while n!=0 :
    if n%2==0:
        ans+="0"

    else:
        ans+="1"
        if i%2==0:
            n-=1
        else:
            n+=1
    n=n//2
    i+=1
    

print(ans[::-1])

Solution (Python):
N=int(input())
if N==0:
  print(0)
  exit()
ans=[]
while N!=0:
  tmp=N%(2)
  if tmp<0:
    tmp+=2
  N=(N-tmp)//(-2)
  ans.append(str(tmp))
  
ans=ans[::-1]
Ans=''.join(ans)
print(Ans)

Solution (Python):
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)


def input(): return sys.stdin.readline().rstrip()


N = int(input())
l = deque()
if N == 0:
    print(0)
else:
    while N != 0:
        x = (-2) ** len(l)
        y = (-2) * x
        if abs(N) % abs(y) != 0:
            N -= x
            l.appendleft('1')
        else:
            l.appendleft('0')
    print(''.join(l))

Solution (Python):
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    ret = ""
    while N != 0:
        ret = str(N%2) + ret
        N = -1 * (N//2)
    print(0 if ret == "" else ret)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    ret = ""
    while N != 0:
        ret = str(N%2) + ret
        N = -(N//2)
    print(0 if ret == "" else ret)


if __name__ == '__main__':
    main()

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

Solution (Python):
from math import floor
N=int(input())
l=[0]*41
ans=""
for i in range(40,-1,-1):
    
    n=abs(N/abs(pow(2,i)))
    if n>=1:
        if N/abs(pow(-2,i))<0:
            N=N+abs(pow(-2,i))
            if i%2==0:
                l[i]=-1
            else:
                l[i]=1
        else:
            N = N - abs(pow(-2, i))
            if i%2==0:
                l[i]=1
            else:
                l[i]=-1

for i in range(40):
    if l[i]==-1:
        l[i]=1
        l[i+1]=l[i+1]+1
    elif l[i]==2:
        l[i]=0
        l[i+1]=l[i+1]-1
    elif l[i]==-2:
        l[i]=0
        l[i+1]=l[i+1]+1
flag=0

for i in range(40,-1,-1):
    if l[i]==1:
        flag=1
        ans="".join((ans,str(l[i])))
    elif flag==1:
        ans = "".join((ans,str(l[i])))
if len(ans)==0:
    ans="0"
print(ans)

Solution (Python):
def log2(n):
    i = 1
    r = 0
    if n < 0:
        i = 2
        r = 1
        n = -n
    s = i
    while n > s:
        i *= 4
        s += i
        r += 2
    return r


def resolve():
    n = int(input())
    if n == 0:
        print(0)
        return
    ans = [0] * 40
    while n:
        l = log2(n)
        ans[l] += 1
        n = n - (-2) ** l
    while ans[-1] == 0:
        ans.pop()
    print("".join([str(x) for x in ans[::-1]]))


if __name__ == '__main__':
    resolve()

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

Solution (Python):
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
ans = ''
while n != 0:
    r = n % 2
    if r < 0:
        r += 2
    n = (n - r) // (-2)
    ans += str(r)
if ans == '':
    print(0)
else:
    print(ans[::-1])

Solution (Python):
import sys

def base_convert(n, b):
  if not n: return 0
  res = ''
  while n:
    n, r = divmod(n, b)
    if r < 0: n += 1; r -= b
    res += str(r)
  return int(res[::-1])

n = int(sys.stdin.readline().rstrip())

def main():
    print(base_convert(n, -2))

if __name__ ==  '__main__':
    main()

Solution (Python):





mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    
    
    
    
    
    
    
    
    str_ = ""
    while n != 0:
        
        r = n % 2
        if r < 0:
            r += 2 
        n = (n-r)// (-2)
        
        str_ += str(r)
    
    str_ = str_[::-1]
    if str_ == '':
        str_ = '0'
    print(str_)



if __name__ == '__main__':
  main()

Solution (Python):
N = int(input())
ans = ""
b = -2
while N:
    n = N % b
    if n:
        ans = "".join(["1", ans])
    else:
        ans = "".join(["0", ans])

    N += n
    b *= - 2
print(ans if ans else 0)

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())
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 != 0):
	r = n % 2
	if r < 0:
		r += 2

	n = (n - r) // (-2)
	ans.append(r)

if ans == []:
	ans.append(0)
ans = ans[::-1]

print(*ans, sep='')

Solution (Python):
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    s = []
    if n == 0:
        print('0')
        return

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

if __name__ =='__main__':
    main()

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

while (n!=0):
    r = int(n%2)
    if(r<0):
        r += 2
    lst.append(r)
    n = (n-r)/(-2)

if len(lst) ==0:
    print("0")
else:
    for i in range(len(lst)):
        print(lst[-1-i],end="")
    print()

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

ans = ''

a = n
while True:
    if abs(a) % 2 == 1:
        a -= 1
        ans = '1' + ans
    else:
        ans = '0' + ans

    if abs(a) == 0:
        break
    a /= -2

print(ans)

Solution (Python):
n=int(input())
l=[]
while n!=1 and n!=0:
  l.append(abs(n)%2)
  if n>0:
    n=-n
    n//=(-2)
    n=-n
  elif n<0:
    n=abs(n)
    n//=(-2)
    n=-n
l.append(n)
l=l[::-1]
ans=str()
for i in l:
  ans+=str(i)
print(ans)

Solution (Python):
N = int(input())
digits = []
i = 1
while N != 0:
    if N % pow(2,i) == 0:
        digits.append('0')
    else:
        digits.append('1')
        N -= pow(-2,i-1)
    i += 1

if digits:
    print("".join(reversed(digits)))
else:
    print("0")

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def check(n):
    if n == 0:
        return ''
    if n % 2 == 0:
        return check(n // (-2)) + '0'
    return check((n - 1) // (-2)) + '1'


n = int(readline())
if n == 0:
    print(0)
else:
    print(check(n))

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