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

ans = []
for i in range(1, 40):
    if n % (2**i):
        n -= (-2)**(i-1)
        ans.append('1')
    else:
        ans.append('0')
    if not n:
        break
print(''.join(reversed(ans)))

Submission status: Accepted

Solution code:
N = int(input())

if N ==0:
    print('0')
    exit()
if N == 1:
    print('1')
    exit()
if N == -1:
    print('11')
    exit()
if N == -2:
    print('10')
    exit()

m = 400
length = 0
for i in range(3, m):
    posneg = 1 if i % 2 == 1 else -1
    if posneg == 1 and 4**((i+1)/2 - 1) / 3 <= N and N <= 4**((i+1)/2) / 3:
        length = i
        break
    elif posneg == -1 and -(4)**((i+1)/2 - 1)/ 3 >= N and N >= -(4)**((i+1) /2) / 3:
        length = i
        break
ans = ''
for i in range(length, 2, -1):
    posneg = 1 if i % 2 == 1 else -1
    if posneg == 1:
        if 4**((i+1)/2 - 1) / 3 <= N and N <= 4**((i+1)/2) / 3:
            N -= 2**(i - 1)
            ans += '1'
        else:
            ans += '0'
    elif posneg == -1:
        if posneg == -1 and -(4)**((i+1)/2 - 1)/ 3 >= N and N >= -(4)**((i+1) /2) / 3:
            N += 2**(i - 1)
            ans += '1'
        else:
            ans += '0'

if N ==	0:
    ans += '00'
if N == 1:
    ans += '01'
if N == -1:
    ans += '11'
if N == -2:
    ans += '10'


print(ans)

Submission status: Accepted

Solution code:
N = int(input())

Ans = ""
while N!=0:
    Ans = str(N%2) +Ans
    N = (N - N%2)//2
    N *= -1

print(Ans if Ans!="" else 0)

Submission status: Accepted

Solution code:
import sys

N = int(input())

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

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

Submission status: Accepted

Solution code:
import math

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

	i = 0

	if n == 0:
		print(0)
		return 

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

		i += 1

	print(ans[::-1])

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
# abc105c

N = int(input())

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

a = ""
b = -2

while N!=1:
    if N%b==0:
        a += "0"
        N = N//b
    else:
        a += "1"
        if N>0:
            N = N//b + 1
        else:
            N = N//b + 1
if N==1:
    a += "1"
print(a[::-1])

Submission status: Accepted

Solution code:
n=int(input())
result=''
if n==0:
    result='0'
while True:
    if n==0:
        break
    if n%2==0:
        n=n/(-2)
        result='0'+result
    else:
        n=(n-1)/(-2)
        result='1'+result
print(int(result))

Submission status: Accepted

Solution code:
n = int(input())
a = []
if n ==0:
  print(0)
else:
  while n != 0:
    if n%2 ==0:
      n = n/(-2)
      a.append("0")
    else:
      n = (n-1)/(-2)
      a.append("1")
    
  b = ""
  for i in range(len(a)):
    b += a[len(a)-i-1]

  print(b)

Submission status: Accepted

Solution code:
n = int(input())

ans = ""

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

if(ans == ""):
    ans = "0"

print(ans[::-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
N = int(input())
if N == 0:
  print(0)
  sys.exit()
ans = ''
k = 1
while N != 0:
  if N%(2**k) == 0:
    ans = '0'+ans
  else:
    ans = '1'+ans
    N = N-((-2)**(k-1))
  k += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

s = ''
while n!=0:
  x = abs(n%2)
  n = (n - x)//(-2)
  s = str(x) + s

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

Submission status: Accepted

Solution code:
n = int(input())

s = ''

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

if s == '':
  s = '0'

print(s)

Submission status: Accepted

Solution code:
n = int(input())
dig,d_min,d_max = 0,0,0
d_range = []
ans = ""
while not d_min <= n <= d_max:
    if dig%2 == 0:  d_max += 2**dig
    else:  d_min -= 2**dig
    dig += 1
    d_range.append([d_min,d_max])

for i in range(dig-1):
    check = n- (-2)**(dig-1-i)
    if not d_range[dig-2-i][0] <= check <= d_range[dig-2-i][1]:
        ans += "0"
    else:
        ans += "1"
        n = check
if n == 1:
    ans+="1"
else:
    ans += "0"

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

def getMBinary(N):
    S = ""
    
    while N != 0:
        if N % -2 == 0:
            S = "0" + S
        if N % -2 != 0:
            S = "1" + S
            N = N - 1
        N = N // -2
    
    if S == "":
        S = "0"
    
    return S
if __name__ == "__main__":
    N = int(input())
    print(getMBinary(N))

Submission status: Accepted

Solution code:
import math

n=int(input())

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


    A=[]
    lim=int(math.log2(abs(n)))
    for i in range(lim+4):
        n%=2**(lim+4-i)
        A.append(n)
        


    ans=""

    #print(A)

    if A[lim+4-1]==1:
        ans+="1"
    else:
        ans+="0"

    bi=0
    st=1
    for i in range(1,lim+4): #(-2)^i の位を決める
        if bi==0:
            st+=2**(i-1)
        #print(A[lim-i-1])
        if A[lim+4-i-1]>=st and A[lim+4-i-1]<st+2**i :
            ans+="1"
        else:
            ans+="0"
        bi=(bi+1)%2

    #print(ans)

    ans2=""
    zero=0
    for i in range(len(ans)):
        if ans[-i-1]=="0" and zero==1:
            ans2+="0"
        elif ans[-i-1]=="1":
            zero=1
            ans2+="1"

    print(ans2)

Submission status: Accepted

Solution code:
n = int(input())
nn = n
ans = ''
a = 2
while True:
	if n == 0:
		break
	if n % a == 0:
		ans += '0'
	else:
		ans += '1'
		n -= (a//2)

	n = n//2
	if a == 2:
		a = -2
	else:
		a = 2


ans = ans[::-1]
if nn == 0:
	print(0)
else:
	print(ans)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
import sys
import math
y = int(input().split()[0])
result = ""
i = 0
while True:
    z = (-2) ** (i+1)
    x = y % z
    if x != 0:
        y = y + x
        result = "1" + result
    else:
        result = "0" + result
    if y == 0:
        break
    i = i + 1
print(result)

Submission status: Accepted

Solution code:
N = int(input())

def to_bits(n):
    if n == 0:
        return [0]
    else:
        bits = []
        while (n != 0):
            bit = n % 2
            bits.append(bit)
            n = (n - bit) // (-2)
        return list(reversed(bits))

print(''.join([str(bit) for bit in to_bits(N)]))

Submission status: Accepted

Solution code:
import sys


n = int(input())

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

l1 = []
t = 0
s = 0
a = 0
while a < 10 ** 9:
    a = 2 ** t
    s += a
    l1.append(s)
    t += 2

l2 = []
t = 1
s = 0
a = 0
while a < 10 ** 9:
    a = 2 ** t
    s += a
    l2.append(s)
    t += 2


result = []
while n != 0:
    if n > 0:
        N = abs(n)
        for i in range(len(l1)):
            if N <= l1[i]:
                x = 2 * i
                break
        n -= (-2) ** x
        result.append(x)
    else:
        N = abs(n)
        for i in range(len(l2)):
            if N <= l2[i]:
                x = 2 * i + 1
                break
        n -= (-2) ** x
        result.append(x)

ans = []
for i in range(result[0], -1, -1):
    if i in result:
        ans.append('1')
    else:
        ans.append('0')

answer = ''.join(ans)
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
s = ''

while N != 0:
#    print(N, s, N % (-2) == 0)
    if N % (-2) == 0:
        s = '0' + s
    else:
        s = '1' + s
        N -= 1
    N /= (-2)

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

Submission status: Accepted

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

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

    idx = 0
    while True:
        idx += 1
        left = sum([(-2)**i for i in range(idx+1) if i%2==1])
        right = sum([(-2)**i for i in range(idx+1) if i%2==0])
        if left <= N <= right:
            break

    max_idx = idx
    coeff = [0 for _ in range(max_idx+1)]
    for idx in range(max_idx, 0-1, -1):
        left = sum([(-2)**i for i in range(idx) if i%2==1])
        right = sum([(-2)**i for i in range(idx) if i%2==0])
#         print(left, N, right)
        if not left <= N <= right:
            N -= (-2)**(idx)
            coeff[idx] = 1
    #     print(N)
    # print(reversed(coeff)
    print(''.join(map(str, reversed(coeff))))

Submission status: Accepted

Solution code:
n = int(input())

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

if s == '':
    s = '0'

print(s)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    if N == 0:
        print('0')
    l = []
    while N:
        l.insert(0, str(-(N % (-2))))
        if l[0] == '1':
            N -= 1
        N = N // -2
    print("".join(l))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())

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

if(S == ""):
	S = "0"

print(S)

Submission status: Accepted

Solution code:
def binn(n):
    if n == 0: return
    r = n % -2
    if r != 0:
        r = 1
    binn((n - r) // -2)
    print(r, end="")

n = int(input())
if n == 0:
    print(0)
else:
    binn(n)
    print()

Submission status: Accepted

Solution code:
N = int(input())
sho = N
if sho == 0 or sho == 1:
    kotae = str(sho)
else:
    kotae = ''
while sho != 1 and sho != 0:
    if sho % (-2) == 0:
        newsho = sho // (-2)
    else:
        newsho = sho // (-2) + 1
    amari = sho - newsho * (-2)
    kotae = str(amari) + kotae
    if newsho == 1:
        kotae = str(newsho) + kotae
    sho = newsho
print(kotae)

Submission status: Accepted

Solution code:
# coding: utf-8

n = int(input())
a = ""

if n == 0:
    print(0)
else:
    while n != 0:
        if n % 2 == 0:
            a = "{0}{1}".format(0, a)
            n /= -2
        else:
            a = "{0}{1}".format(1, a)
            n = (n-1)/(-2)
    print(a)

Submission status: Accepted

Solution code:
import sys

n = int(input())
res = []

if n==0:
    print(0)
    sys.exit()
    
while n!=0:
    if n%2 == 1:
        res.append(1)
        n = (n-1)/(-2)
    else:
        res.append(0)
        n = n/(-2)


for i in reversed(res):
    print(i, end="")

Submission status: Accepted

Solution code:
N = int(input())

S = ''

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

print(S)

Submission status: Accepted

Solution code:
def toBasen2(x, sign):
    foo = ''
    k = 1
    while k <= x:
        if (x & k) == k:
            foo += '1'
            if not sign:
                x += k
        else:
            foo += '0'
        k <<= 1
        sign = not sign
    if foo == '':
        foo = '0'
    return foo[::-1]

def main():
    x = int(raw_input())
    if x >= 0:
        print toBasen2(x, True)
    else:
        print toBasen2(-x, False)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def ip():
    return int(input())
    
def ipp():
    return map(int,input().split())
    
def sar():
    return list(ipp())
    
def pars(a):
    print(''.join(list(map(str, a))))
    print('\r')
    
def parl(a):
    print('\r'.join(list(map(str, a))))
    print('\r')
    
#template ends   

if __name__=='__main__':
    T=1
    #T=int(input().strip())
    for _ in range(T):
        n = ip()
        k = []
        if n==0:
            print(0)
        i = 0
        while n is not 0:
            k.append((n%(-2)))
            n = n//(-2)
            if (k[-1] == -1):
                k[-1] = 1
                n+=1
            i+=1
        k = k[::-1]
        pars(k)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math

N=int(input())
S=""
while N!=0:
    if N%2==0:
        S+="0"
        N=math.floor(N/2)
    else:
        S+="1"
        N=math.floor(N/2)#切り上げ
    
    N=N*-1#
   

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

Submission status: Accepted

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

s = ''
while n != 0:
    n, k = n//(-2), n % (-2)
    if k < 0:
        n += 1
        k += 2
    s = str(k) + s
print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 
import math
import sys
import itertools
import numpy as np


# いっこ入力
n =int(input())
i = 0
a = []
while n != 0:
    if n % 2 == 1:
        a.append(1)
    else:
        a.append(0)
    n = n // 2
    n = -n

#print(len(a))
#print(a)
if len(a) == 0:
    print(0)
    exit
for i in range(0,len(a)):
    print(a[len(a)-i-1], end='')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import logging
import time


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

    # 入力
    def input_value(self):
        # self.n = int(input())
        # self.A, self.B = map(int, input().split())
        # self.A = list(map(int, input().split()))
        # self.a, self.b, self.c = map(int, [input() for i in range(4)])
        # self.t = [None] * self.n
        self.n = int(input())

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

    @staticmethod
    def to_base_m2(n):
        # logging.debug(input_str)
        if n == 0:
            return '0'

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

        # logging.debug(input_str)



    # def run(self):
    #     if self.n % self.k == 0:
    #         return 0
    #     return 1

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

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

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


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

    solver = Solver()

    # Solver.test()

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

Submission status: Accepted

Solution code:
# coding: utf-8

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(int(S))

Submission status: Accepted

Solution code:

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

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

Submission status: Accepted

Solution code:
def solve(n):
    ret = ""
    i = 0  # n%2が元の何ビット目にあたるか
    while True:
        if i % 2 == 1 and n % 2 == 1:  # 奇数ビットが1のとき
            n += 2
        ret += str(n % 2)
        n //= 2  # 1ビット右にずらす
        i += 1
        if n == 0:
            break
    return ret[-1::-1]  # 逆順に結合されているので反転


n = int(input())
if n == 0:
    print(0)
elif n < 0:  # 負数は左ビットシフト、一文字落として表示
    n *= -2
    print(solve(n)[:-1])
else:
    print(solve(n))

Submission status: Accepted

Solution code:
import bisect


def put(a, b):  # 結果の表示
    l = max(len(a), len(b))  # aとbの長さが違うときに壊れるので以下で十分な長さの0を結合しておく
    a = "0" * l + a
    b = "0" * l + b
    s = ""
    for i in range(-1, -l-1, -1):  # 長さの偶奇を考えたくないので逆順に生成してあとで反転
        s += a[i] + b[i]
    s = s[-1::-1]  # 反転
    print(s[s.find("1"):])  # 頭にたくさんついている0を除いて表示


def quad(i):  # 数値を4進数表記の文字列に直す。16→"100"など。
    s = ""
    while i > 0:
        s += str(i % 4)
        i //= 4
    return s[-1::-1]


l = [0, 1]
for i in range(1, 20):  # 候補の生成。最長で20ビット。
    l += [4 ** i + j for j in l]

n = int(input())
if n == 0:  # n==0は出力が空文字になってしまうので別に扱う
    print("0")
else:
    for i in range(len(l)):
        ind = bisect.bisect_left(l, (l[i] - n) // 2)
        if l[i] - 2 * l[ind] == n:
            put(quad(l[i]), quad(l[ind]))
            break

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

    ans = '1' + ans

    print(ans)

Submission status: Accepted

Solution code:
import bisect
def put(a,b): #結果の表示
    l=max(len(a),len(b)) #aとbの長さが違うときに壊れるので以下で十分な長さの0を結合しておく
    a="0"*l+a
    b="0"*l+b
    s=""
    for i in range(-1,-l-1,-1): #長さの偶奇を考えたくないので逆順に生成してあとで反転
        s+=a[i]+b[i]
    s=s[-1::-1] #反転
    ind=s.find("1")
    print(s[ind:]) #頭にたくさんついている0を除いて表示

def quad(i): #数値を4進数表記の文字列に直す。16→"100"など。
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,20): #候補の生成。最長で20ビット。
    l+=[4**i+j for j in l]

n=int(input())
if n==0: #n==0は出力が空文字になってしまうので別に扱う
    print("0")
else:
    for i in range(len(l)):
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Submission status: Accepted

Solution code:
def solve(n):
    ret=""
    i=0 #n%2が元の何ビット目にあたるか
    while True:
        if i%2==1 and n%2==1: #奇数ビットが1のとき
            n+=2
        ret+=str(n%2)
        n//=2 #1ビット右にずらす
        i+=1
        if n==0:
            break
    return ret[-1::-1] #逆順に結合されているので反転

n=int(input())
if n==0:
    print(0)
elif n<0: #負数は左ビットシフト、一文字落として表示
    print(solve(n*(-2))[:-1])
else:
    print(solve(n))

Submission status: Accepted

Solution code:
def solve(n):
    ret=""
    i=0
    while True:
        if i%2==1 and n%2==1: #奇数ビットが1のとき
            n+=2
        ret+=str(n%2)
        n//=2
        if n==0:
            break
        i+=1
    return ret[-1::-1] #逆順に結合されているので反転

n=int(input())
if n==0:
    print(0)
elif n<0: #負数は左ビットシフトして一文字落とす
    print(solve(n*(-2))[:-1])
else:
    print(solve(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from math import ceil
n = int(input())

ret = ""

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
import bisect
def put(a,b): #結果の表示
    l=max(len(a),len(b)) #aとbの長さが違うときに壊れるので以下で十分な長さの0を結合しておく
    a="0"*l+a
    b="0"*l+b
    s=""
    for i in range(-1,-l-1,-1): #長さの偶奇を考えたくないので逆順に生成してあとで反転
        s+=a[i]+b[i]
    s=s[-1::-1] #反転
    ind=s.find("1")
    print(s[ind:]) #頭にたくさんついている0を除いて表示

def quad(i): #数値を4進数表記の文字列に直す。16→"100"など。
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18): #候補の生成。最長で18ビット。
    l+=[4**i+j for j in l]

n=int(input())
if n==0: #n==0は出力が空文字になってしまうので別に扱う
    print("0")
else:
    for i in range(len(l)):
        ind=bisect.bisect_left(l,(l[i]-n)//2)
        if l[i]-2*l[ind]==n:
            put(quad(l[i]),quad(l[ind]))
            break

Submission status: Accepted

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

Submission status: Accepted

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

pattern1 = None
pattern2 = None

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

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

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

Submission status: Accepted

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

pattern1 = None
pattern2 = None

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

pattern1 = None
pattern2 = None

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

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

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

Submission status: Accepted

Solution code:
import bisect

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

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

pattern1 = None
pattern2 = None

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

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

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

Submission status: Accepted

Solution code:
N = int( input() )

s = []

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

print (s)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10000) # 再帰深度を変更しておく

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

# index 2からlen(B)までとりたい
# 先頭の0bをぬかす
# 負の数だったら……（最初の2つを反転するのだが）

M = N
C = 0
i = 0
# これが元

if M == 0:
	C = 0

while M > 0:
	now = M % 2

	M = int(M/2) #次に進めるために割る
	#print("{},{},{}".format(i, M, now))
	
	if now != 0:
		C += pow(2,i)
	# 0,4などがあったら足す
	
	if i%2 == 1:
		# 奇数桁目
		# 2,8など。+1があったら繰上りする。
		if now != 0:
			M += 1 # 繰上りする
	i += 1

while M < 0:
	now = M % 2

	M = int(M/2) #次に進めるために割る
	#print("{},{},{}".format(i, M, now))
	
	if now != 0:
		C += pow(2,i)
	# 0,4などがあったら足す
	
	if i%2 == 0:
		# 偶数桁目
		# 0,4など。+-1があったら繰上りする。
		if now != 0:
			M -= 1 # 繰上りする
	i += 1



res = bin(C)[2:]

print(res)

Submission status: Accepted

Solution code:
import math

n = int(input())

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

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

Submission status: Accepted

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


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

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

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

    return result[::-1]


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

    print(convert(n))