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

a = []

if n > 0:
    while n > 0:
        a.append(n % 2)
        n //= 2

    a.append(0)
    a.append(0)
    for i in range(len(a) - 1):
        if i % 2 == 1:
            if a[i] == 1:
                a[i + 1] += 1
            elif a[i] == 2:
                a[i + 1] += 1
                a[i] = 0
        else:
            if a[i] == 2:
                a[i + 1] += 1
                a[i] = 0

    for i in range(len(a)):
        a[i] = str(a[i])
    for i in range(len(a) - 1, -1, -1):
        if a[i] == '0':
            a[i] = ''
        else:
            break
    print(''.join(reversed(a)))
elif n == 0:
    print('0')
else:
    n = 0 - n
    while n > 0:
        a.append(n % 2)
        n //= 2

    a.append(0)
    a.append(0)
    for i in range(len(a) - 1):
        if i % 2 != 1:
            if a[i] == 1:
                a[i + 1] += 1
            elif a[i] == 2:
                a[i + 1] += 1
                a[i] = 0
        else:
            if a[i] == 2:
                a[i + 1] += 1
                a[i] = 0

    for i in range(len(a)):
        a[i] = str(a[i])
    for i in range(len(a) - 1, -1, -1):
        if a[i] == '0':
            a[i] = ''
        else:
            break
    print(''.join(reversed(a)))

Submission status: Accepted

Solution code:
import bisect
def put(a,b):
    l=max(len(a),len(b))
    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:])

def quad(i):
    s=""
    while i>0:
        s+=str(i%4)
        i//=4
    return s[-1::-1]

l=[0,1]
for i in range(1,18):
    l+=[4**i+j for j in l]

n=int(input())
if n==0:
    print(0)
else:
    for i in range(len(l)):
        if (n-l[i])%2==0:
            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 main():
    """
    S: N の -2進数表現の条件

    1: S 0/1 からのみなる文字列
    2: S ='0' でなければSの先頭の文字は'1'
    3: S=S_k S_k-1...S_0
        S_0 * (-2)^0 + S_1 * (-2)^1 + ... + S_k * (-2)^k = N
    """
    N = int(input())
    ans = editorial_movie(N)
    # ans = f(N)
    # ans = TLE(N)
    print(ans)


def TLE(N):
    if N == 0:
        return 0

    n_bit = 16 * 2
    for i in range(1, 2 ** n_bit):
        s = 0
        bits = []
        for j in range(n_bit):
            bit = (i & (1 << j))
            on = int(bit != 0)
            s += on * ((-2) ** j)
            bits.append(str(on))

        # print(i, s, "".join(bits[::-1]), sep="\t")

        if N == s:
            bits = bits[::-1]
            for k, b in enumerate(bits):
                if b == "1":
                    return "".join(bits[k:])

    return ""


def my_bin(N):
    if N == 0:
        return "0"

    ans = ""
    while N > 0:
        if N % 2 == 0:
            ans += "0"
        else:
            ans += "1"
        N //= 2

    return ans[::-1]


def editorial_movie(N):
    """
    桁: 可能数値: 範囲
    0:  1,  0 ~ +1
    1: -2, -2 ~ +1,  -2: 0-2, -1:1-2
    2:  4, -2 ~ +5,   2:-2+4, 3:-1+4, ...
    といった感じで全範囲カバー可能

    -2進数なので、基数は-2
    10進数を2進数に変換するとき、2(基数)で割る
    ただし、実装では調整が必要
    """
    if N == 0:
        return "0"

    ans = ""
    while N != 0:
        if N % 2 == 0:
            ans += "0"
        else:
            # N = a * (-2) + 1
            # -3 < 0
            #      -3 = [2]  * (-2) + 1
            #      -3       // (-2) = 1
            #     (-3 - 1)  // (-2) = [2]
            #
            #  3 > 0
            #      3 = [-1] * (-2) + 1
            #      3       // (-2) = -2
            #     (3 - 1)  // (-2) = [-1]
            N -= 1
            ans += "1"

        N //= -2

    return ans[::-1]


def f(N):
    """
    bit全探索
    """
    if N == 0:
        return 0

    if N > 0:
        i = 0
    else:
        i = 1

    ans = 0
    while True:
        if N > 0 and (-2) ** i >= N:
            break
        elif N < 0 and (-2) ** i <= N:
            break
        i += 2

    print(2 ** i)

    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import itertools
import sys
sys.setrecursionlimit(10000)

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

    if n == 0:
        print(0)
        return

    s = ''
    m = n
    while m != 0:
        if m % 2 == 0:
            s += '0'
        else:
            s += '1'
            m -= 1

        m //= -2

    print(s[::-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())

lft = 0
rgt = 1
ret = [(0, 0, 0), (0, 1, 0)]
for i in range(1, 32):
    if i % 2 != 0:
        lft -= 2**i
        ret.append((lft, rgt, i))
    else:
        rgt += 2**i
        ret.append((lft, rgt, i))

ret.reverse()
s = [0 for i in range(32)]
for i in range(len(ret) - 1):
    if ret[i][0] <= n <= ret[i][1] and not(ret[i+1][0] <= n <= ret[i+1][1]):
        n -= (-2) ** ret[i][2]
        s[i] = 1

for i in range(len(s)):
    if s[i] == 1:
        break

for j in range(i, len(s)):
    print(s[j], end='')
print()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def n_based(n:int, base:int) -> str:
    if n == 0:
        return "0"
    
    ans = ""
    res = n
    
    while abs(res) > 0:
        q = res%base
        if q>=0:
            ans = str(q) + ans
            res //= base
        else:
            q += abs(base)
            ans = str(q) + ans
            res //= base
            res += 1
        
    return ans

N = int(input())
print(n_based(N, -2))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

def solve():
    n = int(input())
    ans, m = "", 1
    while n != 0:
        m *= (-2)
        if abs(n) % abs(m) > 0:
            ans += "1"
            n -= m // (-2)
        else:
            ans += "0"
    print(ans[::-1] if ans else 0)

if __name__=="__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
ans = ""
i = 0
while n!=0:
    #print("{0}%{1} = {2}あまり{3}".format(n,-2,n//-2,n%-2))
    if n%2==0:
        ans = "0" + ans
    else:
        ans = "1" + ans
        n -= 1
    #print("n={0}".format(n))
    n=n//(-2)
    #print("n={0}".format(n))
if ans == "":
    print("0")
else:
    print(ans)

Submission status: Accepted

Solution code:
def minus2(K):
    if K==1:
        return "1"
    if K==0:
        return "0"
    S=""
    if K%2==1:
        S="1"
    else:
        S="0"
    K-=K%2
    return minus2(-K//2)+S

print(minus2(int(input())))

Submission status: Accepted

Solution code:
n = int(input())

ma = 50
result=[]
for i in range(ma):
  if n==((-2)**i):
    result.append("1")
    break
  
  if (n%(2**(i+1)))==0:
    result.append("0")
  else:
    result.append("1")
    n-=((-2)**i)

result.reverse()
head=0
for x in result:
  if x=="1":
    break
  if x=="0" and (len(result)-1)>head:
    head+=1

print("".join(result[head:]))

Submission status: Accepted

Solution code:
n=int(input())
i=0
b=[]
q=n
ans=""

while 1:
  r=q%(-2)
  if q==0:
    b.append(0)
    break
 
  if r==0:
    b.append(0)
    q=int(q/(-2))
  else:
    b.append(1)
    q=int(q/(-2)+0.5)
    if q==0:
      break
  i=i+1

b.reverse()
for j in range(i+1):
  ans=ans+str(b[j])
  
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
K_MAX = 100

n = N
result = ""
for k in range(K_MAX):
    sign = (-1) ** k
    if n % 2 == 1:
        n = n - sign
        result = "1" + result
    elif n != 0:
        result = "0" + result
    else:
        break        
    n = n / 2
if len(result) == 0: result = "0"

print(result)

Submission status: Accepted

Solution code:
N = int(input())

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

def SolveNegBinary(N):
    if N == 0:
        print "0"
    else:
        r = N
        # ansTrue allocates the "True" index for -2nary expression
        ansTrue = []

        while r != 0:
            ind = (- np.sign(r) + 1)/2
            s = (-2)**ind
            while np.abs(s) < np.abs(r):
                ind +=2
                s += (-2)**ind

            ansTrue.insert(0,ind)
            r = r - (-2)**ind

        disAnswer = ""
        for k in range(ansTrue[-1] + 1)[::-1]:
            if k in ansTrue:
                disAnswer += "1"
            else:
                disAnswer += "0"


        print disAnswer
    

N = input()
SolveNegBinary(N)

Submission status: Accepted

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

N = int(input())

m = -2
S = []
while(N):
    Nm = abs(N) % abs(m)
    S.append("1" if Nm else "0");
    if Nm:
        N = N - m / (-2)
    m = m * -2

S = "".join(reversed(S))
print("0" if S == "" else S)

Submission status: Accepted

Solution code:
import math
a = int(input())
# a = 123456789

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

used = []
i = 0
while a != 0:
    if a % 2 == 1:
        used.append(True)
        if i % 2 == 0:
            a -= 1
        else:
            a += 1
    else:
        used.append(False)
    a = a // 2
    i += 1

# print(used)
ans = ''
for elem in reversed(used):
    if elem:
        ans += '1'
    else:
        ans += '0'

print(ans)

Submission status: Accepted

Solution code:
def f(n):
    s=""
    while n>0:
        s=str(n%2)+s
        n//=2
        if n==0:
            break
        if n%2==1:
            n+=2
            s="1"+s
        else:
            s="0"+s
        n//=2
    return s

n=int(input())
if n==0:
    print(0)
elif n<0:
    print(f(n*(-2))[:-1])
else:
    print(f(n))

Submission status: Accepted

Solution code:
N = int(input())

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

print(S)

Submission status: Accepted

Solution code:
N = int(input())


ans = ""
divide = 1

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

print(ans)

Submission status: Accepted

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

if N % 2 == 0:
    A = "0" + A
else:
    A = "1" + A
    N -= 1

n = -2
while N != 0:
    if N == n:
        A = "1" + A
        break
    if N % ( n * 2 ) == 0:
        A = "0" + A
    else:
        A = "1" + A
        N -= n
    n *= -2

print(A)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n = int(input())

if n == 0:
    print(0)

else:
    s = ''
    cnt = 1
    while n != 0:
        s += str(1) if n % (-2)**cnt != 0 else str(0)
        n -= (-2)**(cnt - 1) if n % (-2)**cnt != 0 else 0
        cnt += 1
    print(s[::-1])

Submission status: Accepted

Solution code:
n=int(input())
a=[]
k=0

if n==0:
    print(0)

while k<1:
    if n==0:
        k=1
    else:
        if n%2==0:
            a.append(0)
            n=n/(-2)
        else:
            a.append(1)
            n=(n-1)/(-2)
            
for i in (reversed(a)):
    print(i,end="")

Submission status: Accepted

Solution code:
N=int(input())
out=[]
if N==0:
    out.append(0)
else:
    while abs(N)>0:

        if N%2==1:
            out.append(-1)
        else:
            out.append(0)
        N=int(N//-2)
for i in range(len(out)-1):
    if out[i]==-1:
        out[i]=1
        out[i+1]+=1

if out[len(out)-1]==-1:
    out[len(out)-1]=1
    out.append(1)
out.reverse()
if len(out) is not 1:
    while out[0]==0:
        del out[0]


print("".join(map(str,out)))

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())

if N == 0:
    print(0)
    exit

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

print(bits)

Submission status: Accepted

Solution code:
n = int(input())
b2 = []
while n != 0:
    rem = n % -2
    n //= -2
    if rem == -1:
        rem = 1
        n += 1
    b2.insert(0, rem)

if len(b2) == 0:
    print(0)
else:
    print(str(b2).replace("[", "").replace("]", "").replace(", ", ""))

Submission status: Accepted

Solution code:
N = int(input())

temp = N
result = []

while temp != 0:
    if temp % 2 == 0:
        ans = 0
    else:
        ans = 1
    temp = (temp - ans) // (-2)
    result.append(str(ans))
result.reverse()
if N == 0:
    print(0)
else:
    print("".join(result))

Submission status: Accepted

Solution code:
N=int(input())

ans=[]

while True:
  if N%2==0:
    ans.append("0")
    N//=(-2)
  else:
    ans.append("1")
    N=(N-1)//(-2)
    
  if N==-1:
    ans.append("11")
    break
  elif N==1:
    ans.append("1")
    break
  elif N==0:
    break

ans.reverse()
print("".join(ans))

Submission status: Accepted

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

Submission status: Accepted

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

t = -2

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N = int(input())

ans = ''
N = N * (-1)
while N :
    m = abs(N%2)
    ans = ans + str(m)
    N = (N // (-2))
    

if len(ans) == 0:
    ans = '0'
    
ans = ans[::-1]
print (ans)

Submission status: Accepted

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


def main():
    from math import ceil
    n = int(input())
    ans = ''

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

    while n != 0:
        mod_n = ceil(n / (-2))
        ans += str(n - mod_n * (-2))
        n = mod_n

    print(ans[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# encoding: utf-8
N = int(input())

# define L

# adjust
ans = ""
while N != 0:
    # print(N, ans)
    if N % 4 == 0:
        ans = "00" + ans
        N -= 0
    elif N % 4 == 1:
        ans = "01" + ans
        N -= 1
    elif N % 4 == 2:
        ans = "10" + ans
        N -= -2
    else:
        ans = "11" + ans
        N -= -1
    N = int(N / 4)
    
for i in range(len(ans)):
    if ans[i] != "0":
        print(ans[i:])
        break
else:
    print(0)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
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 LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    if n == 0:
        return 0
    r = []
    i = 0
    while n != 0:
        ii = 2**(i+1)
        if n % ii != 0:
            r.append('1')
            if i % 2 == 0:
                n -= ii // 2
            else:
                n += ii // 2
        else:
            r.append('0')
        i += 1
    return ''.join(r[::-1])




print(main())

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N =int(input().strip())

target = N
output_str = ""

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

if output_str != "" :
    print(output_str)
else:
    print("0")

Submission status: Accepted

Solution code:
N = int(input())
i = 0
str = ""

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

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

print(str)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
if __name__ == "__main__":
    N = int(input())
    for bit in range(0, 1 << 20):
        ans = "0" * 64
        ans = list(ans)
        res = 0

        base = 1
        idx = 0
        tmp_bit = bit
        while (tmp_bit > 0):
            if tmp_bit % 2 != 0:
                res += base
                ans[idx] = '1'
            tmp_bit = tmp_bit >> 1
            base *= 4
            idx += 2
        if N > res:
            continue
        
    
        for x in range(41, 0, -2):
            base = 2 ** x
            base *= -1
            if res + base >= N:
                res += base
                ans[x] = '1'
        if res == N:
            ans = "".join(reversed(ans))
            for i in range(len(ans)):
                if ans[i] == '1':
                    print (ans[i:])
                    exit(0)
            print (0)
            exit(0)

Submission status: Accepted

Solution code:
n=int(input())
ansarr=''
while n != 0:
    q=n//(-2)
    r=n % (-2)
    #print(d,r)
    if(r==-1): # (d+1) * (-2) + 1 = n
        r=1
        q+=1
    ansarr+=str(r)
    n=q
    #print(d,r)
if(ansarr == ''):
    ansarr = '0'
else:
    ansarr = ansarr[::-1]
print(ansarr)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
ret = ''
while n != 0:
  d, r = n // (-2), n % (-2)
  if r == -1: # (d+1) * (-2) + 1 = n
    r = 1
    d += 1
  ret += str(r)
  n = d
if ret == '':
  ret = '0'
else:
  ret = ret[::-1]
print(ret)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n = int(input())

ans=""

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

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = ''
while n:
  x = (n + 40000000000) % 4
  if x == 0:
    s = '00' + s
  if x == 1:
    s = '01' + s
    n -= 1
  if x == 2:
    s = '10' + s
    n += 2
  if x == 3:
    s = '11' + s
    n += 1
  n //= 4
s = s.lstrip('0')
if not s:
  s = '0'
print(s)

Submission status: Accepted

Solution code:
from math import floor, ceil, log

N = int(input())

# O(logN)
def base10to(n, b):
    if n // b > 0:
        return base10to(n // b, b) + str(n % b)
    else:
        return str(n % b)

def calc_base_for_pos_N(N):
    S_base4 = base10to(N, 4) # str

    S_raw = list(map(int, tuple(''.join([digit + '0' for digit in S_base4])[:-1])))[::-1]

    # transformation. takes O(logN)
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        # -2のところだったら
        if position % 2 == 1:
            position += 1
            continue
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 2

    # postprocessing
    if S_raw[-1] == 2:
        S_raw[-1] = 0
        S_raw += [1, 1]
    elif S_raw[-1] == 3:
        S_raw[-1] = 1
        S_raw += [1, 1]
    elif S_raw[-1] == 4:
        S_raw[-1] = 0
        S_raw += [0, 1]

    S = ''.join([str(digit) for digit in S_raw])[::-1]
    return S

if N >= 0:
    print(calc_base_for_pos_N(N))
else:
    pos_N = abs(N)
    pos_S = list(map(int, list(calc_base_for_pos_N(pos_N))))
    pos_S = pos_S[::-1]
    shifted_S = [0] + pos_S
    pos_S = pos_S + [0]
    assert len(pos_S) == len(shifted_S)
    S_raw = [shifted_S[i] + pos_S[i] for i in range(len(pos_S))]
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 1
    # postprocessing
    last_two_digits = S_raw[-2:]
    if last_two_digits == [2, 1]:
        S_raw = S_raw[:-2]
    elif last_two_digits == [3, 1]:
        S_raw[-2:] = [1]
    elif last_two_digits == [1, 2]:
        S_raw[-2:] = [1, 0, 1, 1]
    elif last_two_digits == [2, 2]:
        S_raw[-2:] = [0, 1]
    elif last_two_digits == [3, 2]:
        S_raw[-2:] = [1, 1]
    elif last_two_digits == [4, 1]:
        S_raw[-2:] = [0, 0, 1]
    elif last_two_digits == [4, 2]:
        S_raw = S_raw[:-2]
    S = ''.join([str(digit) for digit in S_raw])[::-1]
    print(S)

Submission status: Accepted

Solution code:
def n_based(n:int, base:int) -> str:
    if n == 0:
        return "0"
    
    ans = ""
    res = n
    
    while abs(res) > 0:
        q = res%base
        if q>=0:
            ans = str(q) + ans
            res //= base
        else:
            q += abs(base)
            ans = str(q) + ans
            res //= base
            res += 1
        
    return ans

N = int(input())
print(n_based(N,-2))

Submission status: Accepted

Solution code:
N = int(input())

ans = []

if N == 0:
    print('0')
else:
    while abs(N) > 0:
        r = N % -2
        if r != 0:
            N -= 1
            ans.append('1')
        else:
            ans.append('0')

        N //= -2

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

Submission status: Accepted

Solution code:
from collections import deque
from sys import stdin, stdout

input = lambda: stdin.readline().rstrip()
write = stdout.write

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

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

main()

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 len(S) != 0 :
    print(S)
else :
    print(0)

Submission status: Accepted

Solution code:
#abc105c
import sys

n=int(raw_input())
if n==0:
 print 0
 sys.exit()
res=''
while n:
 if n%(-2)==0:
  res+='0'
 else:
  res+='1'
 n+=n%(-2)
 n/=(-2)
print res[::-1]

Submission status: Accepted

Solution code:
n = int(input())

mb = []
n = -n
while True:
    mb.insert(0,str(n%2))
    n = -n//2
    if n == 0:
        break
ans = ''.join(mb)    
print(ans)

Submission status: Accepted

Solution code:
a=int(input())
b=''
while a:
 b=str(a&1)+b
 a=-(a//2)
print(b if b else 0)

Submission status: Accepted

Solution code:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)
print(''.join(map(str,b[::-1])))

Submission status: Accepted

Solution code:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)
print(''.join(map(str,b[::-1])))

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 len(S) == 0 :
    print(0)
else :
    print(S)

Submission status: Accepted

Solution code:
N = int(input())

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

ans = ""
while abs(N) > 0:
    X = N % -2
    N //= -2
    N += (X < 0)
    ans += str(abs(X))

print(ans[::-1])

Submission status: Accepted

Solution code:
n = -int(input())
s = ''
while n != 0:
    s += '1' if n & 1 else '0'
    n //= -2
if s == '':
    s = '0'
print(s[::-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N = int(input())

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

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

print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

N = int(input())

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

Submission status: Accepted

Solution code:
import math
N = int(input())
def poss(x, r, result):
    if x == 0:
        return result + '0'
    if x % pow(2, r) != 0:
        x -= pow(-2, r-1)
        result += '1'
    else:
        result += '0'
    return poss(x, r+1, result)

if N == 0:
    print('0')
else:
    r = poss(N, 1, '')[::-1]
    print(r.lstrip('0'))

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())
if N == 0:
    print(0)
    exit(0)

S = ""
while N != 0:
    r = N % (-2)
    N = N // (-2)
    if r < 0:
        r += 2
        N += 1
    S += str(r)
print(S[::-1])

Submission status: Accepted

Solution code:
a=int(input())
b=[]
if a==0:
	print(0)
while a:
	b.append(a&1)
	a-=a&1
	a=int(a/-2)

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

Submission status: Accepted

Solution code:
def calc_bit(x):
    i = idx = 0
    if x < 0:
        x = -x
        i = 2
        idx = 1
    else:
        i = 1
        idx = 0
    p = i
    while True:
        if x <= p:
            return idx
        else:
            i *= 4
            p += i
            idx += 2


ans = ""
N = int(input())
pv = -1
f = False
if N == 0:
    ans = "0"
else:
    while True:
        v = calc_bit(N)
        if pv-v > 1 and f:
            ans += "0"*(pv-v-1)
        ans += "1"
        N -= (-2)**v
        if N == 0:
            if v > 0:
                ans += "0"*v
            break
        f = True
        pv = v
print(ans)

Submission status: Accepted

Solution code:
#C
N=int(input())
def nsin(n):
    if n==0:
        return '0'
    if n==1:
        return '1'  
    return nsin((n-1)/(-2))+'1' if n%2 else nsin(n/(-2))+'0'

print(nsin(N))

Submission status: Accepted

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

N = int(input())

ans = ""
while N != 0:
    # 末尾の桁が偶奇を決めているので、そこが0か1かは判断できる
    if N % 2 == 0:
        ans = "0" + ans
    else:
        # 今の末尾の桁は1だったので、まずはその分を引く
        N -= 1
        ans = "1" + ans
    # -2進数は-2で割れば桁を落とせる(10進数で割る10する感じ)
    N /= -2
# Nが元々0だった場合
if ans == "":
    ans = 0

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
def solve(n):
    if n == 0:
        return '0'

    ans = ''
    p = 0
    d = 0
    while n + p:
        if (n & 1) ^ p:
            ans += '1'
            if d ^ p:
                p ^= 1
        else:
            ans += '0'
        n >>= 1
        d ^= 1

    return ans[::-1]


n = int(input())
print(solve(n))

Submission status: Accepted

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

    N //= -2

print(int(ans))

Submission status: Accepted

Solution code:
n = int(input())

if n == 0:
    print('0')
else:
    ans = ''
    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:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
def f(x):
    if x==0:
        return "0"
    if x%2==1:
        return f((1-x)//2)+"1"
    else:
        return f((-x)//2)+'0'
if N==0:
    print('0')
    sys.exit()
print(f(N)[1:])