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:
import math


def division(a, b):
    if b == 0:
        raise ZeroDivisionError()
    if a == 0:
        return 0, 0
    if a > 0 and b > 0:
        q = math.floor(a / b)
        return q, a - b * q
    if a > 0 and b < 0:
        q = math.ceil(a / b)
        return q, a - b * q
    if a < 0 and b > 0:
        q = math.floor(a / b)
        return q, a - b * q
    if a < 0 and b < 0:
        q = math.ceil(a / b)
        return q, a - b * q


def Ans(N, B):
    ans = ''
    while(N != 0):
        N, r = division(N, B)
        ans += str(r)
    if ans:
        print(ans[::-1])
    else:
        print(0)


if __name__ == '__main__':
    N = int(input())
    Ans(N, -2)

Submission status: Accepted

Solution code:
n = int(input())
s = ''
i = 1
while(n != 0):
  nt = abs(n)
  res = 1 if (nt & abs(i)) else 0
  s = str(res) + s
  n -= res * i
  i *= -2
print(s if len(s) else 0)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())

S = []

while abs(N)>0:
    x = N%2
    S.append(str(x))
    if len(S)%2 ==0:
        N = (N+x)//2
    else:
        N //= 2

S.reverse()

if len(S)==0:
    S=['0']
    
print(''.join(S))

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())

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

if ans == '':
    ans = '0'

print(ans[::-1])

Submission status: Accepted

Solution code:
n = int(input())

def solve(n):

    tmp = 0
    ans = 0
    if n > 0:
        b = bin(n)[2:]
        for i,c in enumerate(b):
            if (len(b)-i)%2 == 0:
                if int(c) == 1:
                    tmp += 11*10**(len(b)-i-1)
            else:
                tmp += int(c)*10**(len(b)-i-1)
    elif n < 0:
        b = bin(abs(n))[2:]
        for i,c in enumerate(b):
            if(len(b)-i)%2 == 1:
                if int(c) == 1:
                    tmp += 11*10**(len(b)-i-1)
            else:
                tmp += int(c)*10**(len(b)-i-1)

    tmp = str(tmp)
    while '2' in tmp:
        ans = 0
        for i,c in enumerate(tmp):
            o = len(tmp)-i-1
            if int(c) >= 2:
                if (ans//(10**(len(tmp)-i)))%10 > 0:
                    ans += (int(c)-2-10)*10**o
                else:
                    ans += (110+int(c)-2)*10**o
            else:
                ans += int(c)*10**(len(tmp)-i-1)
        
        tmp = str(ans)
    
    return tmp


print(solve(n))

Submission status: Accepted

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

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

Submission status: Accepted

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


main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import bisect


"""Template"""


class IP:
    """
    入力を取得するクラス
    """
    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: 数
        """
        return int(input())

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数で合計
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if ((i >> j) & 1) == 1:
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val


"""ここからメインコード"""


def main():
    """クラス呼び出し等行うよ"""
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """この下から書いてね"""

    """コピーコードです。"""
    n = ip.I()
    s = ''
    while True:
        r = n % (-2)
        n //= -2
        if r < 0:
            r += 2
            n += 1
        s += str(r)
        if n == 0: break
    print(s[::-1])


main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import bisect


"""Template"""


class IP:
    """
    入力を取得するクラス
    """
    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        """
        1文字の取得に使います
        :return: 数
        """
        return int(input())

    def IL(self):
        """
        1行を空白で区切りリストにします(int
        :return: リスト
        """
        return list(map(int, self.input().split()))

    def SL(self):
        """
        1行の文字列を空白区切りでリストにします
        :return: リスト
        """
        return list(map(str, self.input().split()))

    def ILS(self, n):
        """
        1列丸々取得します(int
        :param n: 行数
        :return: リスト
        """
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        """
        1列丸々取得します（str
        :param n: 行数
        :return: リスト
        """
        return [self.input() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        """
        Half enumeration
        半分全列挙です
        pの要素の和の組み合わせを作ります。
        ソート、重複削除行います
        :param p: list : 元となるリスト
        :return: list : 組み合わせられた和のリスト
        """
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

    def Bfs2(self, a):
        """
        bit_full_search2
        bit全探索の改良版
        全探索させたら2進数のリストと10進数のリストを返す
        :return: list２つ : １個目 2進数(16桁)  2個目 10進数で合計
        """
        # 参考
        # https://blog.rossywhite.com/2018/08/06/bit-search/
        # https://atcoder.jp/contests/abc105/submissions/4088632
        value = []
        for i in range(1 << len(a)):
            output = []

            for j in range(len(a)):
                if ((i >> j) & 1) == 1:
                    """右からj+1番目のiが1かどうか判定"""
                    # output.append(a[j])
                    output.append(a[j])
            value.append([format(i, 'b').zfill(16), sum(output)])

        value.sort(key=lambda x: x[1])
        bin = [value[k][0] for k in range(len(value))]
        val = [value[k][1] for k in range(len(value))]
        return bin, val


"""ここからメインコード"""


def main():
    # 1文字に省略
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    """コピーコードです。https://atcoder.jp/contests/abc105/submissions/4088632 
    こちらを参考にテストを行っています。"""
    n = ip.I()
    # それぞれ半分全列挙
    list1 = [(-2) ** i for i in r(16)]
    list2 = [(-2) ** (i + 16) for i in r(16)]
    list1_bin, list1_val = id.Bfs2(list1)
    list2_bin, list2_val = id.Bfs2(list2)

    # 2分探索
    ans = 0
    for i in r(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])

        if j < len(list2_val) and list1_val[i] + list2_val[j] == n:
            ans = list2_bin[j] + list1_bin[i]
            break
    print(int(ans))


main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
#template input
import bisect

def IT(): #整数1個
    return int(input())
def IL(): #整数複数
    return [int(_) for _ in input().split()]
def IS(): #文字列複数
    return [_ for _ in input().split()]
def ILS(n): #整数1つ　縦にズラーってなってるやつ
    return [int(input()) for _ in range(n)]
def SLS(n): #文字列　縦にズラーってなってるやつ
    return [input() for _ in range(n)]
def ILSS(n): #整数複数　縦にズラーってなってるやつ
    return [[int(_) for _ in input().split()] for j in range(n)]

#template technique
def bit_full_search2(A):
    #https://blog.rossywhite.com/2018/08/06/bit-search/
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                #output.append(A[j])
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])

    value.sort(key=lambda x:x[1])
    bin = [value[k][0] for k in range(len(value))]
    val = [value[k][1] for k in range(len(value))]
    return bin, val

"""ここからメインコード"""
def main():
    n = IT()
    #それぞれ半分全列挙
    list1 = [(-2) ** i for i in range(16)]
    list2 = [(-2) ** (i + 16) for i in range(16)]
    list1_bin, list1_val = bit_full_search2(list1)
    list2_bin, list2_val = bit_full_search2(list2)

    #2分探索
    ans = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                ans = list2_bin[j] + list1_bin[i]
                break
    print(int(ans))

main()

Submission status: Accepted

Solution code:
N = int(input())

base = -2
l = []
while N:
    a = ((-N)//base)*-1
    r = N-(-2)*a
    l.append(r)
    N = a

if len(l) == 0:
    print(0)
else:
    print(''.join(map(str, reversed(l))))

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
#template input
import bisect

def IT():
    return int(input())
def IL():
    return [int(_) for _ in input().split()]
def SL():
    return [int(_) for _ in input().split()]
def ILS(n):
    return [int(input()) for _ in range(n)]
def SLS(n):
    return [input() for _ in range(n)]
def ILSS(n):
    return [[int(_) for _ in input().split()] for j in range(n)]


"""ここからメインコード"""
def main():
    n = IT()
    ans = ""
    for i in range(32):
      if n % (2 ** (i+1)) != 0:
        n -= n % (2 ** (i+1)) * (-1) ** (i % 2)
        ans += "1"
      else:
        ans += "0"
    print(int(ans[::-1]))
main()

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.readline
#template input
import bisect

def IT():
    return int(input())
def IL():
    return [int(_) for _ in input().split()]
def SL():
    return [int(_) for _ in input().split()]
def ILS(n):
    return [int(input()) for _ in range(n)]
def SLS(n):
    return [input() for _ in range(n)]
def ILSS(n):
    return [[int(_) for _ in input().split()] for j in range(n)]

#template technique
def bit_full_search(ss):
    n = len(ss)
    for i in range(1 << n):
        s = ""
        for j in range(n + 1):
            if ((1 & i >> j) == 1):
                s += ss[j]
        print(s)

def bit_full_search2(A):
    #https://blog.rossywhite.com/2018/08/06/bit-search/
    value = []
    for i in range(1 << len(A)):
        output = []

        for j in range(len(A)):
            if ((i >> j) & 1) == 1:
                #output.append(A[j])
                output.append(A[j])
        value.append([format(i, 'b').zfill(16), sum(output)])
    return value


"""ここからメインコード"""
def main():
    n = IT()
    #それぞれ半分全列挙
    list1 = [(-2) **  i for i in range(16)]
    list2 = [(-2) ** (i + 16) for i in range(16)]

    list1 = bit_full_search2(list1)
    list1.sort(key=lambda x:x[1])
    list1_bin = [list1[i][0] for i in range(len(list1))]
    list1_val = [list1[i][1] for i in range(len(list1))]

    list2 = bit_full_search2(list2)
    list2.sort(key=lambda x:x[1])
    list2_bin = [list2[i][0] for i in range(len(list2))]
    list2_val = [list2[i][1] for i in range(len(list2))]
    ans = 0
    for i in range(len(list1_val)):
        j = bisect.bisect_left(list2_val, n - list1_val[i])
        if j < len(list2_val):
            if list1_val[i] + list2_val[j] == n:
                ans = list2_bin[j] +list1_bin[i]
                break
    print(int(ans))
main()

Submission status: Accepted

Solution code:
N=int(input())

if N%2==0:
  ans='0'
else:
  ans='1'
  N-=1
  
i=2
while abs(N)>0:
  if N%((-2)**i)==0:
    ans='0'+ans
  else:
    ans='1'+ans
    N-=(-2)**(i-1)
  i+=1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

def main(N):
    if N == 0:
        return 0, 0
    if N >= 1:
        for i in range(0, 32, 2):
            if N <= (2**(i+2)-1)//3:
                return N - 2**i, 10**i
    if N <= -1:
        for i in range(1, 34, 2):
            if (-2)*(2**(i+1)-1)//3 <= N:
                return N - (-2)**i, 10**i
    assert False, 'Never reached: N = {}'.format(N)

base2 = 0
while N != 0:
    N, bit = main(N)
    base2 += bit
print(base2)

Submission status: Accepted

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

L = []
M = []

for length in range(1,41):
    if length % 2 == 0:
        l = -2 * pow(4,length//2) // 3
        m = (pow(4,length//2) - 1) // 3
    elif length % 2 == 1:
        l = -2 * (pow(4,(length-1)//2) - 1) // 3
        m = (pow(4,(length+1)//2) - 1) // 3
    L.append(l)
    M.append(m)

identify = []
for i in range(40):
    if i == 0:
        ap_list = [L[0],M[0]]
    elif i % 2 == 1:
        ap_list = [L[i],L[i-1]]
    elif i % 2 == 0:
        ap_list = [M[i-1],M[i]]
    identify.append(ap_list)

bit = [0]*40
for i in range(39,-1,-1):
    left = identify[i][0]
    right = identify[i][1]
    if i % 2 == 0 and left < N <= right:
        bit[39-i] = 1
        N -= pow(-2,i)
    elif i % 2 == 1 and left <= N < right:
        bit[39-i] = 1
        N -= pow(-2,i)

ans = "".join(str(e) for e in bit).lstrip("0")
print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

n = int(input())

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

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

print(ans[::-1])

Submission status: Accepted

Solution code:
N = int(input())
if N == 0:
    print(0)
    exit()
L = []
M = []

def bit_range(bit_length,maximum=0,minimal=0):
    for i in range(bit_length-1,-1,-1):
        if i % 2 == 0:
            maximum += pow(2,i)
        else:
            minimal += pow(-2,i)
    L.append(minimal)
    M.append(maximum)

for i in range(1,41):
    bit_range(i)

identify = []
for i in range(40):
    if i == 0:
        ap_list = [L[0],M[0]]
    elif i % 2 == 1:
        ap_list = [L[i],L[i-1]]
    elif i % 2 == 0:
        ap_list = [M[i-1],M[i]]
    identify.append(ap_list)

bit = [0]*40
for i in range(39,-1,-1):
    left = identify[i][0]
    right = identify[i][1]
    if i % 2 == 0 and left < N <= right:
        bit[39-i] = 1
        N -= pow(-2,i)
    elif i % 2 == 1 and left <= N < right:
        bit[39-i] = 1
        N -= pow(-2,i)

ans = "".join(str(e) for e in bit).lstrip("0")
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
minus_bit = ''
if N == 0:
    minus_bit = '00'
while N != 0:
    mod = N % 4
    if mod == 0:
        minus_bit = minus_bit + '00'
        N = N//4
    elif mod == 1:
        minus_bit = minus_bit + '10'
        N = (N-1)//4
    elif mod == 2:
        minus_bit = minus_bit + '01'
        N = (N+2)//4
    else:
        minus_bit = minus_bit + '11'
        N = (N+1)//4

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

    max_k = 0
    if N < 0:
        min_n = 0
        for k in range(1, 32, 2):
            min_n += (-2) ** k
            if min_n <= N:
                max_k = k
                break
    else:
        max_n = 0
        for k in range(0, 32, 2):
            max_n += 2 ** k
            if N <= max_n:
                max_k = k
                break

    t = 0
    for k in range(1, max_k + 1, 2):
        t += 2 ** k

    n = N + t
    n ^= t

    print(bin(n)[2:])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

Submission status: Accepted

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

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

Submission status: Accepted

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

kmax = 40

def main():
    n = int(input())
    di = []
    for i in range(kmax):
        assert abs(n) % (1 << i) == 0
        d = (abs(n) & (1 << i)) >> i
        assert d in [0, 1]
        n -= (-2) ** i * d
        di.append(d)
    di = reversed(di)
    di = [str(x) for x in di]
    di = "".join(di)
    print(int(di))

main()

Submission status: Accepted

Solution code:
# coding: utf-8


II = lambda: int(input())
MI = lambda: map(int, input().split())


def main():
    N = II()
    if N == 0: return 0
    neg = N < 0
    if neg: N = -N
    bn = bin(N)[2:]
    bl = [int(c) for c in bn[::-1]]
    bl.extend([0] * 10)

    begin = 0 if neg else 1
    for i in range(begin, len(bl), 2):
        if bl[i]:
            bl[i + 1] += 1
        for j in range(i + 1, len(bl)):
            if bl[j] == 2:
                bl[j] = 0
                bl[j + 1] += 1
            else:
                break
    while bl[-1] == 0: bl.pop()
    return "".join(map(str, bl[::-1]))


if __name__ == "__main__":
    print(main())

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
# 105 C
N = int(input())
base = -2
n = N
a = []
#pw = base
while True:
    if n==0: break
    if n%base ==0:  b = 0
    else:    b = 1
    a.append(b)
    #print(n, a)#
    n = (n - b)// base
if a==[]: a = [0]
a.reverse()
for x in a: print(x, end='')

Submission status: Accepted

Solution code:
N = int(input())

if N==0:
    print(0)
else:
    ans = []
    
    while N!=0:
        now = str(N%2)
        ans.append(now)
        N = -1*(N//2)
    ans.reverse()
    print(''.join(ans))

Submission status: Accepted

Solution code:
def adja(i):
    if int(i) != i and i > 0:
        return int(i)+1
    elif int(i) != i and i < 0:
        return int(i)
    else:
        return int(i)
def mod(i):
   return i + 2 * adja(i/p)

N = int(input())
p = -2
ans=[]
while (True):
    r = mod(N)
    N = adja(N / p)
    ans.append(str(r))
    if N == 1 or N == 0 :
        if N == 1:
            ans.append(str(1))
        break
print("".join(ans[::-1]))

Submission status: Accepted

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

def f(x,answer):
    if x == 0:
        return answer
    else:
        i = 0
        sum = 0
        if x >= 0:
            while sum < x:
                sum = sum + 4**(i)
                i = i + 1
            return f(x - 4**(i-1) ,answer + 10**(2*i-2))
        else:
            while sum < abs(x):
                sum = sum + 2*(4**(i))
                i = i + 1
            return f(x + 2*(4**(i-1)) ,answer + 10**(2*i-1) )

ans = f(N,answer)
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
i=0
s=[]
n=N
while 1:
    k=pow(2,i+1)
    d=n%k
    if d!=0:
        s.append(1)
        n=n-pow(-2,i)
    elif n//k!=0:
        s.append(0)
    else:
        break
    i=i+1
while s:
    print(s.pop(),end="")
if N==0:
    print(0,end="")
print("")

Submission status: Accepted

Solution code:
N = int(input())
ans = []
res = N
while res != 1 and res != 0:
    res, tmp = res//(-2), res % (-2)
    if tmp==-1:
        tmp = 1
        res +=1
    ans.append(tmp)
ans.append(res)
print(''.join(map(str, reversed(ans))))

Submission status: Accepted

Solution code:
N = int(input())
ans = []
while N is not 0:
	ans.append(abs(N % (-2)))
	if N % (-2) == 0: N //= (-2)
	else: N = N // (-2) + 1

if ans == []:
	print(0)
else:
	ans.reverse()
	ans = list(map(str, ans))
	print(''.join(ans))

Submission status: Accepted

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

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

A.reverse()
print(''.join(A))

Submission status: Accepted

Solution code:
def get_neg2(n):
    if n == -2:
        return "10"
    if n == -1:
        return "11"
    if n == 0:
        return "0"
    if n == 1:
        return "1"
    if n % 4 == 0:
        return get_neg2(n // 4) + "00"
    if n % 4 == 1:
        return get_neg2((n - 1) // 4) + "01"
    if n % 4 == 2:
        return get_neg2((n + 2) // 4) + "10"
    if n % 4 == 3:
        return get_neg2((n + 1) // 4) + "11"


N = int(input())
print(get_neg2(N))

Submission status: Accepted

Solution code:
N=int(input())

if N == 0:
    print(0)
else:
    m = 2
    s = ""
    sgn = 1
    while N!=0:
        r = N % m
        s += "1" if r != 0 else "0"
        m *= -2
        N = N -r 
    print(s[::-1])

Submission status: Accepted

Solution code:
N=int(input())
if N==0:
    N=0
elif N>0:
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==1:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
else:
    N*=-1
    n=format(N,"b")
    for i in range(10**9):
        if i==len(n):
            break
        elif i%2==0:
            if n[-i-1]=="1":
                N+=2**(i+1)
                n=format(N,"b")
print(int(format(N,"b")))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N = int(input())


def f(n):
    if n == 0:
        return "0"

    if n % 2 == 0:
        return f(n // (-2)) + "0"
    else:
        return f((n - 1) // (-2)) + "1"


ans = f(N)
if ans[0] == "0" and len(ans)>=2:
    ans = ans[1:]
print(ans)

Submission status: Accepted

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

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

while n != 0:
    if n % -2 != 0:
        binary.append('1')
        n //= -2
        n += 1
    else:
        binary.append('0')
        n //= -2
        
binary.reverse()

print(''.join(binary))

Submission status: Accepted

Solution code:
n = int(input())
a = []
b = 0
while n != 0:
    c = (-2) ** b
    if n % (c*(-2)) != 0:
        n -= c
        a.append("1")
    else:
        a.append("0")
    b += 1
ans = "".join(reversed(a))
if ans == "":
  ans = 0
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
quat=[]

addstr=''
if N<0:
    addstr=str(N%2)
    N-=N%2
    N//=-2

while N>0:
    quat.append(N%4)
    N//=4
quat.append(0)

ans = [0]*(2*len(quat)+2)

for i in range(len(quat)):
    if quat[i]<=1:
        ans[2*i]=quat[i]
    elif quat[i]<=3:
        ans[2*i]=quat[i]%2
        ans[2*i+1]=1
        quat[i+1]+=1
    else:
        quat[i+1]+=1

ansstr=''

i=len(ans)-1

while ans[i]==0:
    i-=1
    if i==-1:
        break

while i>=0:
    ansstr += str(ans[i])
    i-=1


if len(ansstr)>0:
    print(ansstr+addstr)
else:
    print(0)

Submission status: Accepted

Solution code:
N = int(input())

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

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

Submission status: Accepted

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

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

print(s[::-1] if s else 0)

Submission status: Accepted

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

def base_minus_two(n):
    if n == 0:
        return ''
    d = n % 2
    return base_minus_two((n-d)//2 * -1) + str(d)
print(base_minus_two(n))
# 1,
# -2, -1
# 4, 5, 2, 3
# -8, -7, -10, -9, -4, -3, -6, -5,
# 16, 17, 14, 15, 20, 21, 18, 19, 8, 9, 6, 7, 12, 13, 10, 11

Submission status: Accepted

Solution code:
n = int(input())
def minustwo(n,l):
    if n == 0:
        if l == []:
            return [0]
        return l
    else:
        odd = n % 2
        l.append(odd)
        return minustwo((-1)*(n-odd)//2,l)
l = minustwo(n,[])
l.reverse()
for c in l:
    print(c, end='')
print()

Submission status: Accepted

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

Submission status: Accepted

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

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

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

    print(''.join(ans))

Submission status: Accepted

Solution code:
s = input()
if s == 0:
	print "0"
	exit()
else:
	m = s
	ans = ''
	while m != 0:
		kk = m%(-2)
		m = m//(-2)
		if kk < 0:
			kk += 2
			m += 1
		ans += str(kk)
	print ans[::-1]

Submission status: Accepted

Solution code:
def rec(num):
    if num == 0:
        return '0'
    elif num == 1:
        return '1'
    else:
        return rec((num-num%2)//-2)+str(num%2)
print(rec(int(input())))

Submission status: Accepted

Solution code:
def hoge(n):
    for i in range(40):
        if(minList[i] <= n and n <= maxList[i]):
            break
    return i

N = int(input().strip())

minList = [0]
maxList = [1]
for d in range(1, 40):
    minList.append(min(minList[-1] + (-2)**d, minList[-1]))
    maxList.append(max(maxList[-1], maxList[-1] + (-2)**d))
    
residual = N
index = hoge(residual)
ans = [0 for i in range(index + 1)]
ans[0] = 1
residual = residual - (-2)**index

while(residual != 0):
    index = hoge(residual)
    ans[len(ans) - 1 - index] = 1
    residual = residual - (-2)**index

if(N == 0):
    ans = [0]
    
print("".join(str(e) for e in ans))

Submission status: Accepted

Solution code:
from math import *

#N = int(input())
N = int(input().strip())

def search_n(N):
    if N == 0 or N == 1:
        return 1
    minN = 0
    maxN = 1
    for i in range(1, 40):
        a1 = minN + (-2)**i
        a2 = maxN + (-2)**i
        minN = min(minN, min(a1, a2))
        maxN = max(maxN, max(a1, a2))
        if N <= maxN and N >= minN:
            return i

result = ['0']
while N != 0 and N != 1:
    n = search_n(N)
    N -= (-2)**n
    if len(result) == 1:
        result = ['0' for i in range(0, n+1)]
    result[n] = '1'

if N==1:
    result[0] = '1'

result.reverse()
print(''.join(result))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N=int(input())

x=[]
if N != 0:
	flag = N // abs(N)
N=abs(N)
while N != 0:
	x.insert(0,N % 2 * flag )
	N //= 2
	flag *= -1
x.insert(0,0)
x.insert(0,0)

# 2 = (-1)*(-2) = (-2+1)*(-2) = (-2)^2+(-2)
for i in range(len(x))[::-1]:
	if x[i] == -1:
		x[i] = 1
		x[i-1] += 1
	if x[i] == 2:
		x[i] = 0
		x[i-1] += 1
		x[i-2] += 1

flag=0
for i in range(len(x)):
	if x[i] == 1 or i == len(x)-1:
		flag=1
	if flag == 1:
		print(x[i],end="")
"""
print()
check=0
count=1
for i in range(len(x))[::-1]:
	check +=  x[i] * count
	count *= -2
print(check)
"""

Submission status: Accepted

Solution code:
num_dec = int(input())
num_bin = ''

while num_dec != 0:
  if num_dec % 2:
    num_dec -= 1
    num_bin += '1'
  else:
    num_bin += '0'
  num_dec /= -2

if num_bin == '':
  num_bin += '0'

print(num_bin[::-1])

Submission status: Accepted

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

    ss = []
    t = 0
    m = 1
    while n != t:
        s = int((n - t) % (abs(m) * 2) != 0)
        ss.append(s)
        if s:
            t += m
        m *= -2
    print(''.join(map(str, reversed(ss))))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
m2 = []

if N == 0:
    print(0)
    
while N != 0:
    if N % -2 != 0:
        m2.append('1')
        N = N // -2 + 1
    else:
        m2.append('0')
        N = N // -2

m2.reverse()

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

Submission status: Accepted

Solution code:
N = int(input())

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

S = ""

cnt = 0
while N != 0:
  if abs(N) % pow(2, cnt + 1) != 0:
    S += "1"
    N -= pow(-2, cnt)
  else:
    S += "0"
  cnt += 1
print(S[::-1])

Submission status: Accepted

Solution code:
n = int(input())
m2 = []
 
if n == 0:
    print(0)
    
while n != 0:
    if n % -2 != 0:
        m2.append('1')
        n = n // -2 + 1
    else:
        m2.append('0')
        n = n // -2
        
m2.reverse()
print(''.join(map(str, m2)))