Problem:


Score : 300 points

Problem Statement

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

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

S is a string consisting of 0 and 1.

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

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

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

Constraints

Every value in input is integer.

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

Input

Input is given from Standard Input in the following format:

N

Output

Print the base -2 representation of N.

Sample Input 1

-9

Sample Output 1

1011

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

Sample Input 2

123456789

Sample Output 2

11000101011001101110100010101

Sample Input 3

0

Sample Output 3

0



Sample input:
-9


Sample output:
1011

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
i = 1
ans = []
while n != 0:
    if n % (i*2) != 0:
        n -= i
        ans.append(1)
    else:
        ans.append(0)
    i *= -2
print("".join(map(str,ans[::-1])))

Submission status: Accepted

Solution code:
n = int(input())
s = []
while n != 0:
    rem = n%2
    if rem < 0:
        rem += 2
    
    n = (n-rem)//(-2)
    s.append(str(0+rem))

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

Submission status: Accepted

Solution code:
n = int(input())
if n==0:
    print(0)
    exit()
res = []
while n != 0:
    x = n%-2

    if x<0:
        res.append(1)
        n -= 1
        n //= -2
    else:
        res.append(0)
        n //= -2

res.reverse()
print("".join(str(c) for c in res))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


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

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
def digit_transform(N):
    if N == 0:  return "0"
    ans = ""
    while(N != 0):
        if N % -2 == 0:
            ans = "0" + ans
        else:
            ans = "1" + ans
            N -= 1
        N /= -2
    return ans

print(int(digit_transform(int(input()))))

Submission status: Accepted

Solution code:
n = int(input())

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

s = ""

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

print(s[::-1])

Submission status: Accepted

Solution code:
N = int(input())

if N == 0:
    print(0)
    exit()
elif N == 1:
    print(1)
    exit()
DP = [(0,1)]
num = 0
start = 0
end = 1
while True:
    num += 1
    a = end - start + 1
    if num % 2 == 0:
        start_ = end + 1
        end_ = start_ + a - 1
        end = end_
    else:
        end_ = start - 1
        start_ = end_ - a + 1
        start = start_
    DP.append((start_, end_))
    if start <= N <= end:
        break

Ans = ''
DP[0] = (1, 1)
for i, (start, end) in enumerate(DP[::-1]):
    if start <= N <= end:
        Ans += '1'
        N -= (-2) ** (num-i)
    else:
        Ans += '0'

print(Ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


def main():
    """
    Nを-2べきで展開したときの末端項がmod 2で決定できるから
    末尾から再帰的に桁が決められたのか。。。
    """
    N = int(input())
    if N == 0:
        print(0)
        return
    idx = 0
    ans = deque([])
    while N != 0:
        if N % 2 == 0:
            ans.appendleft(0)
        if N % 2 != 0:
            ans.appendleft(1)
            N -= (-1) ** idx
        N //= 2
        idx += 1
    print("".join(map(str, ans)))    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

ans=''
while n!=0:
  r=n%(-2)
  if r<0:
    r+=2

  ans+=str(r)

  n-=r
  n//=(-2)

print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()

def first_bit_of(n):
    """
    nの先頭ビットが下から何桁目かを出力する。（最下位を0桁目として）
    """
    if n == 0: return 0
    if n > 0:
        idx = 0
        while n > 0:
            n -= pow(4, idx)
            idx += 1
        return 2 * (idx - 1)
    if n < 0:
        idx = 0
        while n < 0:
            n += pow(2, 2 * idx + 1)
            idx += 1
        return 2 * idx - 1
        

def main():
    N = int(input())
    if N == 0:
        print(0)
        return
    first_place = first_bit_of(N)
    #print("first_bit={}".format(first_place))
    ans = [0] * (first_place + 1)
    ans[0] = 1
    N -= pow(-2, first_place)

    while N != 0:
        place = first_bit_of(N)
        #print("first_bit_of({})={}".format(N, place))
        ans[first_place - place] = 1
        N -= pow(-2, place)
    print("".join(map(str, ans)))
    

if __name__ == "__main__":
    main()

Submission status: Accepted

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

    if N is 0:
        print(0)
        return

    ans = []  # 末尾の桁から
    while N:
        q, r = divmod(N, 2)
        ans.append(r)
        N = -q
    print(*reversed(ans), sep='')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())

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

ans=''
while n!=0:
  q=n%(-2)
  if q<0:
    q+=2

  ans+=str(q)

  n-=q
  n//=(-2)

print(ans[::-1])

Submission status: Accepted

Solution code:
N=int(input())

A= [(-2)**i for i in range(40)]
#print(A)
ans=""

for i,num in enumerate(A):
    if N%((-2)**(i+1))==0:
        ans += "0"
    else:
        ans += "1"
        N -= num
    if N==0:
        break
print(ans[::-1])

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
tmp = N
ans = deque()
while tmp != 0:
  r = tmp % 2
  ans.appendleft(r)
  tmp = (tmp-r)//(-2)
print(0 if N == 0 else "".join([str(a) for a in ans]))

Submission status: Accepted

Solution code:
n = int(input())

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

s = ""

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

print(s[::-1])

Submission status: Accepted

Solution code:
N = int(input())
num = N
bit = []
for i in range(1,10000):
    r = abs(num%2)
    bit.append(str(r))
    num = (num-r)//-2
    if num == 0 :
        break
bit.reverse()
print(''.join(bit))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    if n == 0:
        print(0)
        exit()
    bit = []
    i = 0
    base = 1
    while n != 0:
        if n % (base * 2) == 0:
            bit.append("0")
        else:
            bit.append("1")
            n -= base
        i += 1
        base *= -2
    print("".join(bit[::-1]))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N = int(input())
sec = [1,-2]
for i in range(2,32):
  if i%2 == 0:
    sec.append(sec[i-2]+pow(2,i))
  else:
    sec.append(sec[i-2]-pow(2,i))
#print(sec)
sec.reverse()
sec.append(0)
sec.append(0)
ans = []
for i in range(32):
  temp = 0
  if N >0 and sec[i] >0:
    if N>sec[i+2]:
      temp = 1
      #print(N,pow(-2,31-i))
      N -= pow(-2,31-i)
  elif N<0 and sec[i] <0:
    if N < sec[i+2]:
      temp = 1
      #print(N,pow(-2,31-i))
      N -= pow(-2,31-i)      
  ans.append(str(temp))

T = "".join(ans)
print(int(T))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ans = []
for i in range(100):
    if n%(2**(i+1))>0:
        ans.append('1')
        n -= (-2)**i
    else:
        ans.append('0')
    if n==0:
        break
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
n = int(input())

ans = ""
cnt = 0

while n != 0:
    new = n - (-2) ** cnt
    if new % (2 ** (cnt + 1)) == 0:
        ans = "1" + ans
        n = n - (-2) ** cnt
    else:
        ans = "0" + ans
    cnt += 1

if not ans:
    print("0")
else:
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

ans = []
while N != 0:
    d = len(ans)
    if N % 2 == 1:
        ans.append('1')
        N -= pow(-1, d)
        N //= 2
    else:
        ans.append('0')
        N //= 2

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

Submission status: Accepted

Solution code:
n = int(input())
ans = []
now = n
cou = 1
if n == 0:
    print(0)
    exit()
while True:
    if now == 0:
        break
    if now % (2**cou) == 2**(cou-1):
        ans.append(1)
        now -= (-2)**(cou-1)
    elif now % (2**cou) == 0:
        ans.append(0)
    cou += 1

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

Submission status: Accepted

Solution code:
n = int(input())
ansl = []
if n == 0:
	print(0)
	exit()
while n != 0:
	if n % 2 == 1:
		ansl.append("1")
		n -= 1
	else:
		ansl.append("0")
	n //= -2
print("".join(ansl)[::-1])

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans_rev[::-1])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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


#############
# Main Code #
#############

N = getN()

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

cnt = 0
rep = N
lista = []

# -2進数　N = -9のとき
# -9を1, -2, 4, -8...で表現する → 1 + (-10) を1, -2, 4, -8...で表現する
# -10を-2, 4, -8...で表現する
# ↑　使う数に1を加えないと-9を-2, 4, -8...で表現する事になりこれは不可能
while rep != 0:
    split = (abs(rep) % 2 ** (cnt + 1)) // 2 ** cnt
    if split == 0:
        lista.append(0)
    else:
        lista.append(1)
    rep -= (split * ((-2) ** cnt))
    cnt += 1
lista.reverse()
print(''.join(map(str, lista)))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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


#############
# Main Code #
#############

N = getN()

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

cnt = 0
rep = abs(N)
lista = []

while rep != 0:
    split = (rep % 2 ** (cnt + 1)) // 2 ** cnt
    if split == 0:
        lista.append(0)
    else:
        lista.append(1)
    if N * (-1) ** cnt < 0:
        rep += (split * (2 ** cnt))
    else:
        rep -= (split * (2 ** cnt))
    cnt += 1
lista.reverse()
print(''.join(map(str, lista)))

Submission status: Accepted

Solution code:
n = int(input())

def helper(x):
    if x == 0:
        return []
    r = x % (-2)
    return [r] + helper((x - r) // (-2))


tmp = helper(n)

ans = ''
carry = 0
for x in tmp:
    xx = x + carry
    if xx == -1:
        ans += '1'
        carry = 1
    elif xx == 0:
        ans += '0'
        carry = 0
    elif xx == 1:
        ans += '1'
        carry = 0
if carry:
    ans += '1'

if n == 0:
    print(0)
else:
    ans = str(int(ans[::-1]))
    print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

N = int(input())


ans = []
of = 0


if N < 0:
    N = -N
    s = "0000" + bin(N)[2:]
    l = len(s)
    for i in range(l):
        # 1010 = N + 0101
        of, b = of, int(s[l - i - 1])
        if i % 2 == 0:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 1
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 1
            else:
                ans.append(0)
                of = 1
        else:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 0
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 0
            else:
                ans.append(0)
                of = 1
    ans.reverse()
    pre_ans = "".join(list(map(str, ans)))
    print(pre_ans[pre_ans.find("1"):])

elif N > 0:
    s = "0000" + bin(N)[2:]
    l = len(s)

    for i in range(l):
        # 10101 = N + 01010
        of, b = of, int(s[l - i - 1])
        if i % 2 == 0:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 0
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 0
            else:
                ans.append(0)
                of = 1
        else:
            if (of, b) == (0, 0):
                ans.append(0)
                of = 0
            elif (of, b) == (0, 1):
                ans.append(1)
                of = 1
            elif (of, b) == (1, 0):
                ans.append(1)
                of = 1
            else:
                ans.append(0)
                of = 1
    ans.reverse()
    pre_ans = "".join(list(map(str, ans)))
    print(pre_ans[pre_ans.find("1"):])
else:
    print(0)

Submission status: Accepted

Solution code:
n = int(input())

ans = []
while n:
    r = n % 2
    if r < 0:
        r += 2
    ans.append(str(r))
    n = (n-r) // -2
ans.reverse()

if len(ans) == 0:
    print(0)
else:
    print("".join(map(str, ans)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n=I()
lis=[[0,0] for i in range(48)]
lis[0]=[0,1]
sup=1
low=0
for i in range(1,48):
    #print(low,sup)
    lis[i][0]=low+(-2)**i
    lis[i][1]=sup+(-2)**i
    if i%2==1:
        low+=(-2)**i
    else:
        sup+=(-2)**i
#print(lis)
x=47
table=[0 for i in range(48)]
while x>0:
    if lis[x][0]<=n<=lis[x][1]:
        table[x]=1
        n-=(-2)**x
    x-=1
if n==1:
    table[0]=1
#print(table)
u=sum(table)
if u==0:
    print(0)
    sys.exit()
goal=[]
y=0
sm=0
while sm<u:
    if table[y]==1:
        sm+=1
    goal.append(table[y])
    y+=1
#print(goal)
print(''.join(list(map(str,list(reversed(goal))))))

Submission status: Accepted

Solution code:
n = int(input())

cnt = 0
ans = ""
while n != 0:
    if n % 2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
        if cnt % 2 == 0:
            n -= 1
        else:
            n -= -1
    cnt += 1
    n //= 2
if len(ans) == 0:
    ans = "0"
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())
if n==0:
    print('0')
    exit(0)
i = 1
s = []
while n!=0:
    if n%2**i>0:
        s.append('1')
        n -= (-2)**(i-1)
    else:
        s.append('0')
    i += 1
print(''.join(s[::-1]))

Submission status: Accepted

Solution code:
N = int(input())

if N == 0:
    print(0)
else:
    s = ""
    while abs(N) > 0:
        m = N % (-2)
        if m != 0:
            s = "1" + s
        else:
            s = "0" + s
        N = (N+m) // (-2)
    print(s)

Submission status: Accepted

Solution code:
N = int(input())

lt = [0 for _ in range(50)]
rt = [0 for _ in range(50)]

lt[0] = 1
rt[0] = 1
lt[1] = -2
rt[1] = -1

for i in range(2, 50):
    if i % 2 == 0:
        lt[i] = rt[i - 2] + 1
        rt[i] = lt[i] + 2**i - 1
    else:
        rt[i] = lt[i - 2] - 1
        lt[i] = rt[i] - 2**i + 1


res = [0 for _ in range(50)]
while N:
    for i in range(50):
        if lt[i] <= N <= rt[i]:
            res[~i] = 1
            N -= (-2)**i
            break
            
print(int(''.join(map(str, res))))

Submission status: Accepted

Solution code:
N = int(input())
i = 0
s = ""
while N != 1 and N != 0:
    a = (N+1)//(-2)+1
    m = N - (-2)*a
    s += str(m)
    N = a

s += str(N)

print(s[::-1])

Submission status: Accepted

Solution code:
n = int(input())
p = 1
ans = ""
for i in range(32):
    mod = n%(-2*p)
    if mod>0 and p<0:
        if -2*p>0: mod -= (-2*p)
        else: mod += (-2*p)
    if mod<0 and p>0:
        if -2*p>0: mod += (-2*p)
        else: mod -= (-2*p)
    if mod==p:
        ans += "1"
        n -= p
    else :
        ans += "0"
    p *= -2
ans = ans[::-1].lstrip("0")
if len(ans): print(ans)
else: print(0)

Submission status: Accepted

Solution code:
N = int(input())
S = []
i = 0

if(N % 2 == 0):
  S.append("0")

while N!= 0:
  j = 0
  while N % 2** (i+ 1) == 0:
    i+= 1
    j+= 1
  for k in range(max(j- 1, 0)):
    S.insert(0, "0")
  S.insert(0, "1")
  N-= (-2)** i
  
ans = ""

for i in range(len(S)):
  ans+= S[i]
  
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
amari = 0
i = 0
result = []
while i <= 40:
  if i ==0:
   hoge =  n % 2
   if hoge ==1:
      result.append(1)
      amari = 1
      i += 1
   else:
    result.append(0)
    i += 1
  else:
    hoge = n % (2**(i+1))
    if (amari + (-2)**(i)) % (2**(i+1)) == hoge:
      result.append(1)
      amari = amari + (-2)**(i)
      i += 1
    else:
      result.append(0)
      i += 1
      
result = result[::-1]
if n == 0:
  print(0)
else:
  s = ""
  check = False
  for r in result:
    if r == 0 and check == True:
      s += str(r)
    if r == 1:
      s += str(r)
      check = True
  print(int(s))

Submission status: Accepted

Solution code:
N = int(input())
out = []
U = 0
D = 0
t = 1
now = 0

if N>0:
    while now!=N:
        X = (N-D)%(2**t)
        if X!=0 and X<=(2**t)//2:
            out.append(1)
        else:
            out.append(0)
        if t%2==1:
            D += 2**(t-1)
        now = 0
        for i in range(len(out)):
            now += out[i]*(-2)**i
        t+=1
if N<0:
    while now!=N:
        X = (U-N)%(2**t)
        if X!=0 and X<=(2**t)//2:
            out.append(1)
        else:
            out.append(0)
        if t%2==0:
            U += -1*2**(t-1)
        now = 0
        for i in range(len(out)):
            now += out[i]*(-2)**i
        t+=1
if N==0:
    out = [0]

print("".join(list(map(str,out[::-1]))))

Submission status: Accepted

Solution code:
N = int(input())

ans = ''
m = 2
i = 0

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

print(ans[::-1])

Submission status: Accepted

Solution code:
N=int(input())
ans=''
a=-2
r=abs(N%a)
q=(N-r)//a
while q!=0:
  ans=str(r)+ans
  N=q
  r=abs(N%a)
  q=(N-r)//a
ans=str(r)+ans
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
if n==0:
  print(0)
  exit()
if n==1:
  print(1)
  exit()
ans=[]
while n!=1:
  r=n%2
  ans.append(str(r))
  n=(n-r)//(-2)
ans.append(str(1))
ans.reverse()
print(''.join(ans))

Submission status: Accepted

Solution code:
n=int(input())

ans=[]
if(n==0):
    print(0)
    exit()


while n!=0:
    r=n%2
    ans.append(r)
    n=int((n-r)/(-2))

ans.reverse()

for i in ans:
    print(i,end='')

Submission status: Accepted

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

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

r_bits = ""
p = 0
d = 0
while N + p:
    if (N & 1) ^ p:
        r_bits += '1'
        if d ^ p:
            p ^= 1
    else:
        r_bits += '0'
    N >>= 1
    d ^= 1

print(r_bits[::-1])

Submission status: Accepted

Solution code:
import sys
import heapq
import re
from heapq import heapify, heappop, heappush
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)

# ここから書き始める
n = int(input())
ans = ""
cnt = 0
if n == 0:
    print(0)
else:
    while True:
        if n == (-2) ** cnt:
            ans += "1"
            break
        if n % (-2) ** (cnt + 1) == 0:
            ans += "0"
        else:
            ans += "1"
            n -= (-2) ** cnt
        cnt += 1
        # if cnt == 4:
        #     break
    print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
s = []
if N == 0:
    print(0)
    exit()
base = 1
cur = 2
while N != 0:
    r = N % cur
    if r > 0:
        s.append("1")
        N -= base
    else:
        s.append("0")
    cur *= 2
    base *= -2
print("".join(s[::-1]))

Submission status: Accepted

Solution code:
import sys
N = int(sys.stdin.readline().rstrip())
s = []
if N == 0:
    print(0)
    exit()
base = 1
cur = 2
while N != 0:
    r = N % cur
    r = r + cur if r < 0 else r
    if r > 0:
        s.append("1")
        N -= base
    else:
        s.append("0")
    cur *= 2
    base *= -2
print("".join(s[::-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ans = ''
p = -2
while n!=0:
    n,r = divmod(n,p)
    if r < 0:
        r -= p
        n += 1
    ans = str(r) + ans
if ans == '': ans = '0'
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def mainusbin(num):
    base = -2
    dst = ""
    i = 0
    if abs(base) > abs(num):
        return num
    while abs(base**i) <= abs(num):
        i += 1
        amari = num % base**i
        if amari:
            dst = "1" + dst
            num -= base**(i-1)
        else:
            dst = "0" + dst
    return dst
src = int(input())
dst = mainusbin(src)
print(dst)

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	if n == 0:
		print("0")
		return
	out = ""
	base = 1
	while n != 0:
		if n % (-2) == 0:
			out = "0" + out
		else:
			r = n % (-2)
			if r < 0:
				r = 1
			n -= r
			out = "1" + out
		n /= (-2)


	print(out)
resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3


def main():
    N = int(input())
    if N == 0:
        print(0)
        exit()

    ans = ''
    while N != 1:
        m = N % (-2)
        ans += str(abs(m))
        N = N // (-2)
        if m != 0:
            N += 1
        # print(ans,N)
    ans += str(N)
    print(ans[::-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def resolve():
	n = int(input())
	if n == 0:
		print("0")
		return
	out = []
	while n != 0:
		n, rem = divmod(n, -2)
		if rem < 0:
			n += 1
			rem -= -2
		out.append(rem)
	print("".join(map(str, out[::-1])))
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

Solution code:
N=int(input())
ans=""
for i in range(1,10000):
   tmp=2**i
   if N%tmp==2**(i-1):
      N-=(-2)**(i-1)
      ans="1"+ans
   else:
      ans="0"+ans
   if N == 0:
      break
print(ans)