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:
def main():
    N = int(input())
    S = ""
    while N:
        if N % 2:
            N -= 1
            S = "1" + S
        else:
            S = "0" + S
        N //= -2
    print(S if S else "0")
    return


main()

Submission status: Accepted

Solution code:
import sys

n = int(input())

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

sum = 0
ans = ""

count = 0
d = 1

while n != sum:
    mod = (n - sum) % (d * 2)
    # print("count/d/mod %d/%d/%d" % (count, d, mod))

    if mod != 0:
        ans = "1" + ans
        sum += d * (1 if count % 2 == 0 else -1)
    else:
        ans = "0" + ans

    count += 1
    d *= 2

print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc105/tasks/abc105_c
# -2進数
# 前に考えたときはわからなかったけど、数式イジイジしたら解けた


N = int(input())

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

ans = ''
while N != 0:
    if N & 1:  # 奇数ならbitが立つのは共通する性質
        ans += '1'
        N /= -2  # -0.5ずれるのを吸収する処理
        N = int(N + 0.5)

    else:
        ans += '0'
        N //= -2


print(ans[::-1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc105/tasks/abc105_c
# -2進数
# 前に考えたときはわからなかったけど、数式イジイジしたら解けた


N = int(input())

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

ans = ''
while N != 0:
    if N & 1:  # 奇数ならbitが立つのは共通する性質
        ans += '1'
        N /= -2
        if N > 0:
            N += 1
        N = int(N)
    else:
        ans += '0'
        N //= -2


print(ans[::-1])

Submission status: Accepted

Solution code:
from _collections import deque


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
import scipy
from collections import deque
from math import sqrt
from math import floor
#https://atcoder.jp/contests/agc034/tasks/agc034_b
#B - ABC
"""
need to consider the case that ticket is not enough to lower everything
"""

N = gi()

ans = []

while (N != 0):  #
    r = N % 4
    #print(N, r)
    if (r == 0):  #
        ans.append(0)
        ans.append(0)  #
    elif r == 1:
        ans.append(1)
        ans.append(0)
    elif r == 2:
        ans.append(0)
        ans.append(1)
        N += 4
    else:
        ans.append(1)
        ans.append(1)
        N += 4
    N //= 4  #

if len(ans):
    ans.reverse()
    si = 0
    if (ans[si] == 0):  #
        si += 1

    for i in range(si, len(ans)):
        print(ans[i], end="")
else:
    print(0)  #

Submission status: Accepted

Solution code:
N = int(input())
NN = N
b = ''
i = 0
if N == 0:
  b = '0'
else:
  while (NN!=0):
    bi = abs(NN)%2
    b=str(bi)+b
    NN = (NN-bi*(-1)**i)//2
    i+=1
print(b)

Submission status: Accepted

Solution code:
N = int(input())
ans = str(N%2)
N -= N%2
i=2
while N !=0:
    if N%((-2)**i) == 0:
        ans = '0'+ans
        i += 1
    else:
        ans = '1'+ans
        N -= (-2)**(i-1)
        i += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import cmath
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

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

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N = int(sys.stdin.buffer.readline())

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

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

Submission status: Accepted

Solution code:
import math
N = int(input())
tmp = N
ans = []
# print("--------")
for i in range(len(bin(N))):
    # print(tmp % -2**(i+1), -2**(i+1))
    # print(tmp % 2**(i+1), 2**(i+1))
    k = tmp % -2**(i+1)
    # print("--------")
    if k == - 2**i:
        ans.append(1)
        tmp -= (-2)**i
    else:
        ans.append(0)
#print("".join(map(str, ans[::-1])))
tmp = 0
id = len(ans)
for i in range(len(ans)):
    if ans[i]:
        tmp += (-2)**i
    # print(tmp)
    if tmp == N:
        id = i+1
        break


ans = ans[:id]

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

Submission status: Accepted

Solution code:
N=int(input())

#S0*1-S1*2+S2*4-S3*8+S4*16-S5*32... = N
#N=2N1+S0とする
#-S1*2+S2*4-S3*8+S4*16-S5*32... = 2N1
#-S1+S2*2-S3*4+S4*8-S5*16... = N1
#N1=2N2-S1とする
#S2*2-S3*4+S4*8-S5*16... = 2N2
#S2-S3*2+S4*4-S5*8... = N2
#N2=2N3+S2とする
#-S3*2+S4*4-S5*8... = 2N3
#-S3+S4*2-S5*4... = N3
#...
#S0=abs(N)%2, N1=N//2
#S1=abs(N1)%2, N2=ceil(N/2)
#...

i=0
S=''
while N:
    s=N&1
    S=str(s)+S
    if i:
        N=N//2+(s*N//N)
    else:
        N=N//2
    i^=1
print(S if S else 0)

Submission status: Accepted

Solution code:
n = int(input())

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


reverse_ans = []
i = 0
base = -2

while n != 0:
    if n % (base**(i+1)) == 0:
        reverse_ans.append(0)
    else:
        reverse_ans.append(1)
        n -= base**i

    i += 1

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

Submission status: Accepted

Solution code:
def f(n):
    if n==0:
        x[-1]="0"
        return
    if n==1:
        x[-1]="1"
        return
    if n>0:
        k = 0
        while True:
            if 2**k>=n:
                break
            k += 2
        if n<=(2**k-1)//3:
            k -= 2
        x[K-k]= "1"
        f(n-2**k)
    else:
        k = 1
        while True:
            if (-2)**k<=n:
                break
            k += 2
        if n>=((-2)**k+2)//3:
            k -= 2
        x[K-k] = "1" 
        f(n-(-2)**k)
K = 31
x = ["0" for _ in range(K+1)]      
N = int(input())
f(N)
for i in range(K+1):
    if x[i]=="1":
        ind = i
        break
if N!=0:
    print("".join(x[ind:]))
else:
    print(N)

Submission status: Accepted

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

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

if N < 0:
  while total > N:
    total += (-2) ** (2 * i + 1)
    idx_list.append(2 * i + 1)
    i += 1
  diff = abs(total - N)
  flip_str = str(bin(diff))[2:]
else:
  while total < N:
    total += (-2) ** (2 * i)
    idx_list.append(2 * i)
    i += 1
  diff = abs(total - N)
  flip_str = str(bin(diff))[2:]

i = 0
ans = ''
while i <= max(idx_list):
  if i in idx_list:
    ans = '1' + ans
  else:
    ans = '0' + ans
  i += 1

print(bin(int(ans, 2) ^ int(flip_str.zfill(len(ans)), 2))[2:])

Submission status: Accepted

Solution code:
n = int(input())

ans = ""
# 0なら0
if n == 0:
    ans = "0"
else:
    while(n != 0):  # 2で割り切れないならその位は1
        if n % 2 != 0:
            ans = "1" + ans
            n -= 1  # "その位が1に決まった後の残りは-1した数
        else:  # 2で割り切れるならその位は0
            ans = "0" + ans
        n = n // (-2)
print(ans)

Submission status: Accepted

Solution code:
from math import ceil
n = int(input())

lst = []
if n == 0:
    ans = 0
else:
    while n!= 1:
        lst.append(n-(-2)*ceil(n/(-2)))
        n = ceil(n/(-2))
    else:
        lst.append(1)
    lst = [str(c) for c in reversed(lst)]
    ans = "".join(lst)

print(ans)

Submission status: Accepted

Solution code:
import math

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

bits = []
for keta in range(5 + int(math.log2(abs(N)))):
    if N % 2 == 1:
        bits.append("1")
        N -= 1
    else:
        bits.append("0")
    N //= -2
    if N == 0:
        break

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = input()
negBase = -2

if (n == 0): 
    converted = "0"

else:
    converted = "01"
    while (n != 0):           
        remainder = n % (negBase) 
        n = int(n/negBase) 
  
        if (remainder < 0): 
            remainder += ((-1) * negBase) 
            n += 1
  
        converted = str(remainder) + converted 
          
    converted = converted[0:len(converted)-2]

print(converted)

Submission status: Accepted

Solution code:
N = int(input())

temp = N
S = ""
while temp != 0:
    rem = temp % -2
    div = temp // -2
    if rem == -1:
        div += 1
        rem = 1
    temp = div
    S = str(rem) + S
if N == 0:
    print(0)
else:
    print(S)

Submission status: Accepted

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

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

Submission status: Accepted

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

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.append(1)
        n -= 1
    else:
        ans.append(0)
    n //= -2
print(''.join(list(map(str,ans[::-1]))))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import ceil

def solve(N: int):
    if N == 0:
        print(0)
        return 

    answer = ""
    while N != 0:
        syou = ceil(N/-2) 
        amari = N-syou*-2

        answer+= str(amari)
        N = syou
    
    print(answer[::-1])

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ans = [0]*41
answer = ""
def finder(n):
    global ans
    if n == 0:
        return 1
    elif n >= 1:
        for i in range(1,20):
            if n <= (4**i-1)//3:
                ans[2*(i-1)] = 1
                return finder(n-2**(2*(i-1)))
    else:
        for i in range(1,20):
            if n >= -2*(4**i-1)//3:
                ans[2*i-1] = 1
                return finder(n+2**(2*i-1))
finder(N)
flg = False
for i in range(len(ans)):
    if ans[-(i+1)] == 1:
        flg = True
    if flg:
        answer += str(ans[-(i+1)])
if not flg:
    answer ="0"
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
list1 = []

chinpo = 1

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

while True:
    if n==0:
        break
    if n%2 != 0:
        n -=1
        list1.append(1)
    else:
        list1.append(0)
    n /= -2

list1.reverse()
print("".join(map(str,list1)))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -2進数を求める
N = int(input())

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

Submission status: Accepted

Solution code:
import math
N= int(input())
ans = []
if N == 0:
    print(0)
else:
    for i in range(10**9):
        ans.append(str(abs(N%-2)))
        N = math.ceil(N/-2)
        if N == 1:
            break
    ans.append("1")
    ans2 = [ans[-i] for i in range(1, len(ans) + 1)]
    print("".join(ans2))

Submission status: Accepted

Solution code:
N = int(input())
A = []
if N == 0:
  A = [0]
i = 0
while N != 0:
  A = [N % 2] + A[:]
  N //= 2
  N = -N
for i in range(len(A)):
  print(A[i], end = '')

Submission status: Accepted

Solution code:
N = int(input())
ans = ""
if N == 0:
    print(0)
    exit()
while N != 0:
    # 下の桁から求めていく
    r = N % 2
    if r < 0:
        r += 2
    N = (N-r) // (-2)
    ans += str(r)
print(ans[::-1])

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
mod = 2
sign = 1
stack = deque()

while True:
    if N % mod != 0:
        stack.append("1")
        N -= mod // 2 * sign
    else:
        stack.append("0")
    mod *= 2
    sign *= -1
    # print("N = " + str(N))
    if N == 0:
        break

for i in range(len(stack)):
    print(stack.pop(), end="")

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a = INT()

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

ans = ''
while abs(a) > 0:
    # 小さいビットから見て行って、その時点の偶奇で値を特定していく
    if a % 2 == 1:
        # 今の末尾の桁は1だったので、その分を引く
        a -= 1
        ans += '1'
    else:
        ans += '0'
    # -2進数は-2で割れば桁を落とせる(10進数で割る10する感じ)
    a /= -2
print(ans[::-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

a = INT()

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

ans = ''
i = 0
while abs(a) > 0:
    # 小さいビットから見て行って、余るかどうかで値を特定していく
    if a % 2**(i+1) != 0:
        a -= (-2)**i
        ans += '1'
    else:
        ans += '0'
    i += 1
print(ans[::-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

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

print(ret)

Submission status: Accepted

Solution code:
N=int(input())
r=[]
x=0
while N!=0:
  d=abs(N)%2
  r.append(d)
  N=(N-d*(-1)**x)//2
  x+=1
print(*[0] if r==[] else r[::-1],sep='')

Submission status: Accepted

Solution code:
n = int(input())
s = "1" if n % 2 == 1 else "0"
n = - n // - 2
while n:
  mod = (n % 2) ** 2
  s = "{}".format(mod) + s
  n = n // - 2
print(s)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

answer = ""
for i in range(100):
  if N % 2 ** (i+1):
    answer += "1"
    N -= (-2)**i
  else:
    answer += "0"
  if N == 0:
    break
print(answer[::-1])

Submission status: Accepted

Solution code:
n = int(input())
ans = []
for i in range(40):
  if i % 2 == 0:
    if n % 2 == 1:
      n -= 1
      n //= 2
      ans.append(1)
    else:
      n //= 2
      ans.append(0)
  else:
    if n % 2 == 1:
      n += 1
      n //= 2
      ans.append(1)
    else:
      n //= 2
      ans.append(0)
  if n == 0:
    break
ans.reverse()
print("".join(map(str, ans)))

Submission status: Accepted

Solution code:
n = int(input())

if n == 0:
  print(0)

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

Submission status: Accepted

Solution code:
n = int(input())
if n<0:
    x = abs(n*2)
else:
    x = n
for i in range(1,100):
    if x<=(4**i-1)//3:
        ord = 2*i-1
        break
dif = -x
ans = []
for i in range(ord-1,-1,-1):
    if i%2 == 0:
        if dif < -(2**i-1)//3:
            ans.append(1)
            dif += 2**i
        else:
            ans.append(0)
    else:
        if dif > 2*(2**(i-1)-1)//3:
            ans.append(1)
            dif -= 2**i
        else:
            ans.append(0)
if n<0:
    del ans[-1]
print(*ans,sep="")

Submission status: Accepted

Solution code:
N=int(input())
ls=[]
while True:
  ls.append(N%2)
  N=-(N//2)
  if N==0:
    break
print(*reversed(ls),sep="")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


def f(n):
    v = 0
    for i in range(60):
        if 1 << i & n:
            v += (-2)**i
    return v

# @mt
def slv(N):
    v = N
    for i in range(60):
        b = 1 if 1 << i & v > 0 else 0
        if b and i % 2 != 0:
            v += 1 << (i+1)

    return v


def main():
    N = read_int()
    print(bin(slv(N))[2:])



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n = int(input().rstrip('\n'))
    bl = []
    while True:
        if n == 0:
            break
        else:
            bl.append(str(n & 1))
            n //= 2
            n *= -1
    bl.reverse()
    print("".join(bl) if len(bl) != 0 else 0)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N = int(input())
ans = ""
while N != 0:
    ans = str(N % 2) + ans
    N = - (N // 2)
if ans == "":
    ans = '0'
print(ans)

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ans=""
    while n!=0:
        ans = str(n%2) + ans
        n = -(n//2)
    if ans=="":
        print(0)
    else:
        print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ans=[]
    if n==0:
        print(n)
    else:
        while n!=0:
            ans.append(n%2)
            n = n//(-2) + n%abs(-2)
        for i in ans[::-1]:
            print(i,end="")
        print()
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    L = [(0, 1), (-2, 1)]
    for leng in range(2, 17):
        min_v = (-2*(4**(leng+(2-1)//2) - 1))//3
        max_v = (4**(leng+(2-1)//2) - 1)//3
        L.append((L[-1][0], max_v))
        L.append((min_v, max_v))
    # print(*L, sep='\n')
    S = [(1, 1)]
    for leng in range(1, 32):
        if leng & 1:
            S.append((L[leng][0], L[leng-1][0]-1))
        else:
            S.append((L[leng-1][1]+1, L[leng][1]))
    # print(*S, sep='\n')
    ans = ["0"] * 32
    cnt = 31
    for le, ri in S[::-1]:
        if ri < le:
            le, ri = ri, le
        if le <= N <= ri:
            ans[cnt] = "1"
            N -= (-2)**cnt
        cnt -= 1
    print(int("".join(ans[::-1])))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
if N == 0:
    print(0)
    exit()
bit = []
while N != 0:
    bit.append(str(abs(N % 2)))
    N = (N - N % 2) // (-2)
bit.reverse()
print("".join(bit))

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
import math
i=0
ans=0
if n!=0:
  while n!=1:
    ans+=(n-math.ceil(n/(-2))*(-2))*(10**i)
    n=math.ceil(n/(-2))
    i+=1
  ans+=10**i
else:
  ans=0
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ans = ""

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

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

print(ans)

Submission status: Accepted

Solution code:
# base-2 number
from math import ceil, floor
n = int(input())


low = 0
high = 1
digit = 1

while True:
    if low <= n <= high:
        break

    if digit & 1:
        low += (-2) ** digit
    else:
        high += (-2) ** digit
    digit += 1

ans = ""
for i in range(digit, 0, -1):
    mid = (low + high) / 2
    if low <= n < mid:
        if i % 2 == 0:
            ans += "1"
        else:
            ans += "0"
        high = floor(mid) if mid > 0 else ceil(mid)
    else:
        if i % 2 == 0:
            ans += "0"
        else:
            ans += "1"
        low = ceil(mid) if mid > 0 else floor(mid)

print(ans)

Submission status: Accepted

Solution code:
number = int(input())

def to_bin(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 digits[::-1]

ans_list = to_bin(number)

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

Submission status: Accepted

Solution code:
N=int(input())
def f(x):
  #正の数xに対して-2進数表現の桁数を出力
  i=0
  counter=0
  while counter<x:
    counter+=2**i
    i+=2
  return i-1

def g(x):
  k=f(x)
  out=[1]
  for i in range(k-1, 1, -1):
    out.append(h(x, i))
  if x%2==0:
    out.append(0)
  else:
    out.append(1)
  return out

def h(x, i):
  j=i//2
  b=sum([2**(2*k) for k in range(j)])
  if ((x-b-1)//(2**(i-1)))%2==0:
    return 1
  else:
    return 0
  
def e(n):
  #nは負
  n_=-n
  i=1
  while n_>2**i:
    i+=2
    
  return 2**i+n

if N>0:
  out=g(N)
  out=map(str, out)
  out="".join(out)
elif N<0:
  N_=-N
  k=N_//2+N_%2
  out=g(k)
  out.append(N_%2)
  out=map(str, out)
  out="".join(out)
else:
  out=0
  
print(out)

Submission status: Accepted

Solution code:
n = int(input())
ans = ''
for i in range(10000):
    # 偶奇で最下位桁を決定
    if n % 2 == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans
        n -= 1
    # 1ビット右シフト(-2進数)
    n //= -2
print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())
ans = ''
for i in range(10000):
    if n % 2 == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans
        n -= 1
    n //= -2

print(int(ans))

Submission status: Accepted

Solution code:
def main():
    n=int(input())
    ans=[]
    if n==0:
        print(0)
        return
    while n != 0:
        MOD=n%(-2)
        if MOD <0:
            MOD+=2
        ans.append(str(MOD))
        n=(n-MOD)//(-2)
    ans.reverse()
    print(''.join(ans))

if __name__=='__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
ans = []
while n:
    mod = n % 2
    n //= -2
    n += mod
    ans.append(mod)

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

Submission status: Accepted

Solution code:
import math

n=int(input())
s=""

i=0
while n!=0:
    #print(s)
    if abs(n)%2==0:
        s="0"+s
        n=n//2
    else:
        if i%2==0:
            n=(n-1)//2
        else:
            n=(n+1)//2
        s="1"+s
    i+=1
if s!="":
  print(s)
else:
  print(0)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, heapq, collections, bisect, string, copy
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7
ans = []
count = 0; pro = 1

n=int(input())
if n==0:
    print(0)
    exit()
while n!=1:
    # count+=1
    # if count>=10:
    #     exit()
    # print(n,count)
    if n<0:
        if n%2==1:
            n=-(n-1)//2
            ans.append(1)
        else:
            n=-(n//2)
            ans.append(0)
    else:
        ans.append(n%2)
        n=-(n//2)
ans.append(1)
ans.reverse()
print(*ans,sep="")

Submission status: Accepted

Solution code:
N=int(input())


if N>=0:
  k=0
  while N>2**k:
    k+=2
else:
  k=1
  while N<-2*(2**(k-1)):
    k+=2

S=[0]*(k+1)
for i in range(k+1):
  if N%(-2)==-1:
    S[i]=1
    N-=1
  N//=-2
print(int("".join(reversed(list(map(str,S))))))

Submission status: Accepted

Solution code:
def judge(m,i):
    if m==1:
        return 1
    elif m>0:
        if m%(2**i)==0:
            return 0
        else:
            return 1
    else:
        m = -m
        if m%(2**i)==0:
            return 0
        else:
            return 1

def examC():
    n = I()
    N = copy.deepcopy(n)
    i = 0
    ans = []
    while(N!=0):
        cur = judge(N,i+1)
#        print(cur,N)
#        input()
        N -=((-2)**i)*cur
        ans.append(cur)
        i +=1
    if not ans:
        ans = [0]
    print("".join(map(str,ans[::-1])))

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examC()

Submission status: Accepted

Solution code:
#C
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 = ""
    ans = ans[::-1]
    
    for a in ans:
        out+=a
        
    print(out)

Submission status: Accepted

Solution code:
import sys
from collections import deque

N = int(input())

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

Submission status: Accepted

Solution code:
N =int(input())
now = 0
max_list = [1]
min_list = [0]

def show_binary(now_val , now_idx):
    # print(now_val , now_idx)
    if now_idx == 0:
        print(now_val,end = "")
        return
    if now_val == 0:
        print("0", end='')
        show_binary(now_val, now_idx - 1)
    elif now_idx % 2 == 1:
        if min_list[now_idx - 1] > now_val >= min_list[now_idx]:
            print("1" , end = "")
            show_binary(now_val - (-2) ** now_idx, now_idx - 1)
        else:
            print("0" , end = '')
            show_binary(now_val, now_idx - 1)
    else:
        if max_list[now_idx - 1] < now_val <= max_list[now_idx]:
            print("1" , end = "")
            show_binary(now_val - (-2) ** now_idx, now_idx - 1)
        else:
            print("0" , end = '')
            show_binary(now_val, now_idx - 1)

for i in range(1,35):
    # iが奇数の時
    if i % 2 == 1:
        min_list.append(min_list[-1] - 2 ** i)
        max_list.append(max_list[-1])
        if min_list[i-1] >= N >= min_list[i]:
            break
    # 偶数の時
    else:
        min_list.append(min_list[-1])
        max_list.append(max_list[-1] + 2 ** i)
        if max_list[i-1] <= N <= max_list[i]:
            break
#print("max_list : ",max_list)
#print("min_list : ",min_list)
#print(i)
if 0 <= N <= 1:
    i = 0
show_binary(N,i)

Submission status: Accepted

Solution code:
# C - Base -2 Number
n = int(input())
s = ""
while n!=0:
    s = str(n%2)+s
    n = -(n//2)
print(0 if s=="" else s)

Submission status: Accepted

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

if N > 0:
    N_bin = bin(N)[2:]
else:
    N_bin = bin(-N)[2:]
ans = [s for s in N_bin]
ans.reverse()
ans.append('0')
ans.append('0')

if N >= 0:
    p = 1
else:
    p = 0
for i in range(len(ans)):
    if i % 2 == p:
        if ans[i] == '1':
            k = i
            while True:
                if ans[k+1] == '0':
                    ans[k+1] = '1'
                    break
                else:
                    ans[k+1] = '0'
                    k += 1
while ans[-1] == '0':
    ans.pop()

ans.reverse()
print(''.join(ans))