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())
if n == 0:
  print(0)
  exit(0)
for k in range(100):
    if -2*pow(4,k) +2 < 3*n < pow(4,k) - 1:
        break
l = 2*k

delta = n - (-2*(pow(2,l)-1)//3)

var = delta ^ (2*(pow(2,l)-1)//3)

ans = ''
while var > 0:
    if var&1:
        ans ='1'+ans
    else:
        ans ='0'+ans
    var = var >> 1
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())
ans = []
while N != 0:
    if  N % 2 != 0:
        N -= 1
        ans.append("1")
    else:
        ans.append("0")
    N //= -2

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

Solution (Python):
N = int(input())
p = []
if N > 0:
    for i in range(500):
        if (2**(2*i)-1)/3 < N <= (2**(2*(i+1))-1)/3:
            q = 2*i + 1
if N < 0:
    for i in range(1,500):
        if -(2**(2*i+1)-2)/3 <= N < -(2**(2*i-1)-2)/3:
            q = 2*i
if N == 0:
    q = 1
def cal(n,i):
    if i % 2 != 0:
        if (2**(i-1)-1)/3 < n <= (2**(i+1)-1)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
    elif n == 0:
        p.append(0)
        i = i-1
        if i > 0:
            cal(n,i)
    else:
        if -(2**(i+1)-2)/3 <= n < -(2**(i-1)-2)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
            
    return p
ans = cal(N,q)
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(''.join(ans))

Solution (Python):
N = int(input())
p = []
if N > 0:
    for i in range(500):
        if (2**(2*i)-1)/3 < N <= (2**(2*(i+1))-1)/3:
            q = 2*i + 1
if N < 0:
    for i in range(1,500):
        if -(2**(2*i+1)-2)/3 <= N < -(2**(2*i-1)-2)/3:
            q = 2*i
if N == 0:
    q = 1
def cal(n,i):
    if i % 2 != 0:
        if (2**(i-1)-1)/3 < n <= (2**(i+1)-1)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
    elif n == 0:
        p.append(0)
        i = i-1
        if i > 0:
            cal(n,i)
    else:
        if -(2**(i+1)-2)/3 <= n < -(2**(i-1)-2)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
            
    return p
ans = cal(N,q)
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(int(''.join(ans)))

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n = int(input())

    a = 0
    for i in range(1, 40, 2):
        a -= 2**i
    b = n - a

    res = 0
    for i in range(40):
        if i%2 == 0:
            if (b>>i) & 1:
                res += 1<<i
        else:
            if ((b>>i) & 1) == 0:
                res += 1<<i

    print('{:b}'.format(res))

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n = int(input())

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

    a = 0
    for i in range(1, 40, 2):
        a -= 2**i
    b = n - a
    res = []
    for i in range(40):
        if i%2 == 0:
            if (b>>i) & 1:
                res.append('1')
            else:
                res.append('0')
        else:
            if (b>>i) & 1:
                res.append('0')
            else:
                res.append('1')

    res = res[::-1]
    for i in range(40):
        if res[i] == '1':
            print(''.join(res[i:]))
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n = int(input())

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

    a = 0
    for i in range(1, 40, 2):
        a -= 2**i
    b = n - a
    res = []
    for i in range(40):
        if i%2 == 0:
            if (b>>i) & 1:
                res.append('1')
            else:
                res.append('0')
        else:
            if (b>>i) & 1:
                res.append('0')
            else:
                res.append('1')

    res = res[::-1]
    for i in range(40):
        if res[i] == '1':
            print(''.join(res[i:]))
            exit()

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
 
ans = []
while n != 0:
    if n % 2 != 0:
        n -= 1
        ans.append("1")
    else:
        ans.append("0")
    n //= -2
 
if len(ans) == 0:
    ans.append("0")
 
print("".join(reversed(ans)))

Solution (Python):

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  if n == 0:
    print(0)
    sys.exit()
  ans = ''
  while n!=0:
    if n%2==0:
      ans = '0' + ans
      n = n//(-2)
    else:
      ans = '1' + ans
      n=(n-1)//(-2)
  print(ans)
  
  
  
  
if __name__ == '__main__':
  main()

Solution (Python):
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip(False)
    if N == 0:
        return 0

    n = N 
    result = []
    cur = -2
    for i in range(100):
        if n % cur != 0:
            result.append(1)
            n -= cur/(-2)
        else:
            result.append(0)
        cur *= -2

        if abs(cur) > abs(N) * 10:
            break


    result.reverse()
    r = []
    f = False
    for i in result:
        if f:
            r.append(i)
        elif i == 1:
            r.append(i)
            f = True

    print("".join([str(i) for i in r]))





def iip(listed=True, num_only=True):  
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  
    if index >= len(l):                      
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  
    return "".join(sorted(s))


def iip_ord(startcode="a"):  
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  
    for i in s:
        print(i)


def bitall(N):  
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        
        pass
    return ret


def inv(n, mod):  
    return power(n, mod - 2)


def power(n, p, mod_=mod):  
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

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

Solution (Python):
N = int(input())
if N == 0:
    print("0")
else:
    ans = []
    p = 1
    while 2**(p-1) <= abs(N):
        if N%(2**p) > 0:
            ans.append("1")
            N -= (-2)**(p-1)
        else:
            ans.append("0")
        p += 1

    print("".join(ans[::-1]))

Solution (Python):



ans = []
n = int(input())
if n==0:
    print(0)
    exit()
while n:
    m = n%4
    if m == 0:
        ans.extend(["0","0"])
    elif m==1:
        ans.extend(["1","0"])
    elif m==2:
        ans.extend(["0","1"])
        n+=4
    else:
        ans.extend(["1","1"])
        n+=4
    n//=4
ans.reverse()
if ans[0]=="1":
    print(''.join(ans))
else:
    print(''.join(ans[1:]))

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

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

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

if len(ans) == 0:
    ans.append("0")

print("".join(reversed(ans)))

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

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

if len(ans) == 0:
    ans.append("0")

print("".join(reversed(ans)))

Solution (Python):
import sys
import math

def resolve():
    N = int(input())
    mods = []
    target = N
    if N == 0:
        print("0")
        return
    while True:
        if target == 1:
            mods.append("1")
            break
        v = target // (-2)
        c = target % (-2)
        if c == -1:
            v += 1
            c = 1
        mods.append(str(c))
        target = v
    mods.reverse()
    print("".join(mods))

if '__main__' == __name__:
    resolve()

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

ans_list=[]
sgn=1
for i in range(100):
  if N%2==1:
    ans_list.append("1")
    N-=sgn
  else:
    ans_list.append("0")
    
  N//=2
  sgn*=-1
  if N==0:
    break
  
print("".join(reversed(ans_list)))

Solution (Python):
n = int(input())
def encode(k):
	if k==0:
		return '0'
	if k==1:
		return '1'
	if k % 2 == 0:
		string = '{}0'.format(encode(k // (-2)))
		return string
	if k % 2 == 1:
		string = '{}1'.format(encode((k-1) // (-2)))
		return string

print(encode(n))

Solution (Python):
import sys

def encode(n:int) -> str:
  if n == 0:
      return '0'

  if n == 1:
      return '1'

  if n % 2 == 1:
      ans = '{}1'.format(encode((n-1) // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')
      return ans

  if n % 2 == 0:
      ans = '{}0'.format(encode(n // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')

      return ans

n = int(input())
ans = encode(n)
print(ans)

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

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

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[memo]
-9の例
N = ... + (-2)**i + ...の形をしている
1桁目
N = X + (-2)**0 or N = X + 0であり,このときXは必ず2の倍数
よって,N = X + 0 = -9は成り立たないので,N = X + (-2)**0 の形であり,1桁目は1
また,このときN = X + (-2)**0 = -9よりX = -10.
2桁目
X = Y + (-2)**1 or X = Y + 0であり,このときYは必ず4の倍数
よって,X = Y + 0 = -10は成り立たないので, X = Y + (-2)**1の形であり,2桁目は1
また,このときX = Y + (-2)**1 = -10よりY = -8.
3桁目
Y = Z + (-2)**2 or Y = Z + 0であり,このときZは必ず8の倍数
よって,Y = Z + (-2)**2 = -8は成り立たないので, Y = Z + 0の形であり,3桁目は0
また,このときY = Z + 0 = -8よりZ = -8.
4桁目
Z = W + (-2)**3 or Z = W + 0であり,このときWは必ず16の倍数
よって,Z = W + 0 = -8は成り立たないのおで, Z = W + (-2)**3の形であり,4桁目は1
また,このときZ = W + (-2)**3 = -8よりW = 0.
同様にするとこれ以降の桁は常に0なので,答1011
"""
n = I()
ans = ''
m = 2
cnt = 0
x = n
while 1:
    if x % m:
        ans += '1'
        x -= (-2)**(cnt)
    else:
        ans += '0'
    cnt += 1
    m *= 2
    if x == 0:
        break
print(ans[::-1])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = ''
m = 2
cnt = 0
x = n
while 1:
    if x % m:
        ans += '1'
        x -= (-2)**(cnt)
    else:
        ans += '0'
    cnt += 1
    m *= 2
    if x == 0:
        break
print(ans[::-1])

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = ''
if n == 0:
    print(0)
    quit()
while 1:
    if n == 0:
        break
    if n % -2:
        ans += '1'
        n -= 1
    else:
        ans += '0'
    n //= -2
print(ans[::-1])

Solution (Python):
n = int(input())
s = ''
value = 0
count = 0
while value != n:
    r = n % 2**(count+1)
    if (value + (-2)**count)%(2**(count+1)) == r:
        s += '1'
        value += (-2)**count
    else:
        s += '0'
    count += 1
if n == 0:
    print(0)
else:
    print(int(s[::-1]))

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

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

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

print(S[::-1])

Solution (Python):
n = int(input())
l = []
c = 1
while n != 0:
    if n % 2**c !=0:
        n -= (-2)**(c-1)
        l.append('1')
    
    else:
        l.append('0')
    
    c += 1

if len(l) == 0:
    print('0')

else:
    print(''.join(reversed(l)))

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

if N==0:
    print(0)
else:
    answer=[]
    while N != 0:

        if N % (-2) == 0:
            N=N//(-2)
            answer.append(0)
        else:
            N=N//(-2)+1
            answer.append(1)

    print(''.join(list(map(str, reversed(answer)))))

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

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

A = []
if n == 0:
    print(0)
else:
    while(n != 1):
        if n % (-2) == -1:
            t = n // (-2) + 1
            n =  t
            A.append('1')
        else:
            A.append('0')
            t = n // (-2)
            n = t
    A.append(str(n))
    A = A[::-1]
    print("".join(A))

Solution (Python):
import sys

stdin = sys.stdin
inf = 1 << 60
mod = 1000000007

ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

n = ni()

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

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

now = 1
while n != 0:
    if n % (abs(now) * 2) == 0:
        ans.append("0")
    else:
        ans.append("1")
        n -= now

    now *= -2
    

if ans == []:
    print(0)
else:
    out = ""
    for i in range(len(ans) - 1, -1, -1):
        out += ans[i]

    print(out)

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

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

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

Solution (Python):
import sys

import bisect













readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

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

    if n == -1:
        ans += "11"
    else:
        ans += str(n)

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


if __name__ == '__main__':
    main()

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

S = ""
for i in range(100):
    if abs(N) % (2 ** (i+1)) != 0:
        S += "1"
        N -= (-2) ** (i)
    else:
        S += "0"
    if N == 0:
        break

print(S[::-1])

Solution (Python):
N=int(input())
ans=''
for i in range(33):
    if N%pow(2,i+1):
        ans+='1'
        N-=pow(-2,i)
    else:
        ans+='0'
print(int(ans[::-1]))

Solution (Python):
n = int(input())
check = 2
ans =""
if n == 0:
    print(0)
    exit()
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())


def solve(x):
    ans = []
    while x != 1:
        if x % 2 == 1:
            ans.append(1)
            x = (x - 1) // -2
        else:
            ans.append(0)
            x //= -2
    
    ans.append(1)
    s = sum([-2 ** i for i in range(len(ans)) if ans[i] == 1])
    if s != x:
        ans = ans[::-1]
    print("".join(map(str, ans)))


def main():
    if N == 0:
        print(0)
    else:
        solve(N)


if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
b = -2
a = []
def d(n):
    if n > 0:
        return -(-n//b)
    elif n < 0:
        return (n-1)//b
def r(n):
    if n%b < 0:
        return -(n%b)
    else:
        return n%b

while N != 0 and N != 1:
    a.append(r(N))
    N = d(N)
if N == 1:
    a.append(N)
else:
    a.append(0)

a.reverse()
ans = "".join(map(str,a))
print(ans)

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

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

    n = (n - rest) // -2

if ans == "":
    ans += "0"

print(ans[::-1])

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

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

    n = (n - rest) // -2

if ans == "":
    ans += "0"

print(ans[::-1])

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

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

Solution (Python):

n = int(input())
if n == 0:
    print(0)
    exit()
bit = []
while n != 0:
    bit.append(-(-n % -2))
    n = -(-n // -2)

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

Solution (Python):
n=int(input())
A=[1]
for i in range(15):
  A.append(A[-1]+4**(i+1))
B=[-2,-1]
for i in range(15):
  B.append(A[i]+1)
  B.append(A[i+1])
  B.append(-2*A[i+1])
  B.append(-2*A[i]-1)
C=[1]
for i in range(32):
  C.append(C[-1]*-2)
if n==0:
  print(0)
  exit()
if n==1:
  print(1)
  exit()
a=0
i=0
while a==0:
  if B[2*i]<=n and n<=B[2*i+1]:
    a=1
  else:
    i=i+1
ans=""
while i>=0:
  if B[2*i]<=n and n<=B[2*i+1]:
    ans=ans+"1"
    n=n-C[i+1]
    i=i-1
  else:
    ans=ans+"0"
    i=i-1
if n==0:
  ans=ans+"0"
else:
  ans=ans+"1"
print(ans)

Solution (Python):
n = int(input())
q = []
i = 1
if n == 0:
    q.append(0)
while True:
    if n == 0:
        break
    if abs(n - i) % abs(-2 * i) == 0:
        q.append(1)
        n -= i
    else:
        q.append(0)
    i *= -2
q.reverse()
print("".join(map(str, q)))

Solution (Python):








import sys
sys.setrecursionlimit(10 ** 5 + 10)


def resolve():
    
    n = int(input())
    k = -2
    if n==0:
        print(0)
    else:
        bi = ''
        while n != 0:
            bi += str(n % abs(k))
            if k < 0:
                n = -(-n // k)
            else:
                n = n // k
        print(bi[::-1])


resolve()

Solution (Python):
import collections

N = int(input())
a = collections.deque()
while True:
	a.appendleft(N % 2)
	if N % -2 == -1:
		N -= 2
	N //= -2
	if not N:
		break
for i in a:
	print(i, end='')

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

Solution (Python):
from collections import *
from heapq import *
N=int(input())
if N==0:
    print(0)
    exit()
num=0
count=0
lst=[]

while N:
    if N%2==1:
        lst.append(1)
        N-=1 * (-1 if count%2 else 1)
    else:
        lst.append(0)
    count+=1
    N//=2
lst=list(reversed(lst))
print("".join([str(i) for i in lst]))

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

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

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

    ans = []
    while N != 0:
        r = N % 2
        if r < 0:
            r += 2
        ans.append(r)
        N -= r
        N //= -2
    print("".join(map(str, ans[::-1])))

if __name__ == '__main__':
    main()

Solution (Python):




def main():
    N = int(input())
    result = ""
    while N:
        result = str(N % 2) + result
        N = (N - N % 2) // -2
    print(result or 0)


if __name__ == "__main__":
    main()

Solution (Python):

import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7


    N = II()
    if N == 0:
        print(0)
        return
    ans_stack = deque()
    determined = 0
    for i in range(100):
        if (N - determined) % 2 ** (i+1) != 0:
            ans_stack.append(1)
            determined += (-2) ** i
        else:
            ans_stack.append(0)
        if determined == N:
            break
    ans_str = ''
    while len(ans_stack) > 0:
        item = ans_stack.pop()
        ans_str += str(item)
    print(ans_str)
    '''
    1 -2 4 -8 16 -32 64 -128
    '''
            
if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
N = 2**32 + N

buf = [0]*35
for i,s in enumerate(bin(N)[2:][::-1]):
    if s == "1":
        buf[i] = 1


ans = [0]*35

for i in range(33):
    if buf[i]==1:
        if i%2==0:
            ans[i]+=1
        else:
            ans[i]+=1
            ans[i+1]+=1
    while ans[i]>=2:
        ans[i]-=2
        ans[i+1]+=1
        ans[i+2]+=1
    
first = True
ans[33]-=1

a = ""
for i in ans[:32][::-1]:
    if first:
        if i==1:
            first=False
    if not first:
        a += str(i)
if a!="":
    print(a)
else:
    print(0)
"""
s = a
a = 0
b = 1
for i in s[::-1]:
    if i=="1":
        a+=b
    b *= -2
print(a)
"""

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

Solution (Python):


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

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

ans = 0
i = 1
while n:
  r = n % 2
  if r < 0:
    r += 2
  n = (n - r) // (-2)
  ans += r * i
  i *= 10

print(ans)

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

for _ in range(400):
    if n > 0:
        if n % 2 == 1:
            n = - (n // 2)
            a.append(1)
        else:
            n = -(n // 2)
            a.append(0)
    elif n < 0:
        if (-n) % 2 == 1:
            n = n // (-2) + 1
            a.append(1)
        else:
            n = n // (-2)
            a.append(0)
    
a.reverse()
ans = ''.join([str(i) for i in a])

if m != 0:
    print(ans)
else:
    print(0)

Solution (Python):
from math import ceil

n = int(input())

res = []
while n != 0:
    res.append(n % 2)
    n = ceil(n / -2)
if res == []:
    res.append(0)

print(''.join([str(i) for i in res[::-1]]))

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

ans=""
while n:
    if n%2:
        ans+=str(1)
        n-=1
    else:
        ans+="0"
    n//=-2
print(ans[::-1])

Solution (Python):

n=int(input())
if(n==0):
    print(0)
    exit()
s=""
c=0
while(n!=0):
    if(abs(n)%2==0):s+='0'
    else:
        s+='1'
        if(c%2==0):n-=1
        else:n+=1
    c+=1
    n/=2
    if(c>=100):break
        
t=reversed(s)
for x in t:print(x,end="")

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

  bi = [0]*2 + list(map(int, bin(abs(n))[2:]))

  posi = True if n > 0 else False
  for i in range(len(bi))[::-1]:
    if bi[i] == 2:
      bi[i] = 0
      bi[i-1] += 1
    elif not posi and bi[i] == 1:
      bi[i-1] += 1
    posi ^= True
  print(''.join(map(str, bi)).lstrip('0'))
  return

main()

Solution (Python):

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
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 I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  ans=''
  if n==0:
    return 0

  while True:
    if abs(n)==0:
      return ans

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


print(main())

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

Solution (Python):


N = (-1) * int(input())

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

ans = ""

while N != 0:
    N, r = divmod(N, -2)

    ans += "1" if r else "0"

print(ans[::-1])

Solution (Python):
N=int(input())
l=[]
c=0
while True:
  if N==0:
    break
  else:
    c+=1
    if N%(2**c)==0:
      l.append(0)
    else:
      l.append(1)
      N-=(-2)**(c-1)
if l==[]:
  print(0)
else:
  ans=0
  for i in range(len(l)):
    ans+=int(l[i]*(10**(i)))
  print(ans)