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 sys

n = int(input())

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

cur = n
S = ""

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

    print(s)

Submission status: Accepted

Solution code:
n=int(input());r=0
while n:
 p,a,k=[(1,1,1),(-2,-2,2)][n<0]
 while abs(n)>abs(a):p*=4;a+=p;k<<=2
 r|=k;n-=p
print(bin(r)[2:])

Submission status: Accepted

Solution code:
N=int(input());r=[0]
def s(n,p=1,a=1,k=0):
 if n<0:p,a,k=-2,-2,1
 while abs(n)>abs(a):p*=4;a+=p;k+=2
 r[0]|=1<<k
 if n-p:s(n-p)
if N:s(N)
print(bin(r[0])[2:])

Submission status: Accepted

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


def solve(n):
    if n == 0:
        return
    if n > 0:
        p, a, k = 1, 1, 0
    else:
        p, a, k = -2, -2, 1
    while abs(n) > abs(a):
        p *= 4
        a += p
        k += 2
    while len(ans) <= k:
        ans.append(0)
    ans[k] = 1
    solve(n - p)


solve(N)
print("".join([str(x) for x in reversed(ans)]))

Submission status: Accepted

Solution code:
N = int(input())


def basem2(n, ans):
    if n == 0:
        if not ans:
            ans.append(0)
        return ans
    if n > 0:
        p, a, k = 1, 1, 0
        while n > a:
            p *= 4
            a += p
            k += 2
        # print(f"n={n} +{p} bit:{k} => {n-p}")
    else:
        assert n < 0
        p, a, k = -2, -2, 1
        while n < a:
            p *= 4
            a += p
            k += 2
        # print(f"n={n} {p} bit:{k} => {n-p}")
    while len(ans) < k + 1:
        ans.append(0)
    ans[k] = 1
    return basem2(n - p, ans)


print("".join([str(x) for x in reversed(basem2(N, []))]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    l=[(-2)**i for i in range(32)]
    S=[0]*34
    for i in range(16):
        S[i*2+2]=S[i*2]+l[i*2]
        S[i*2+3]=S[i*2+1]+l[i*2+1]
    ans=0
    while N!=0:
        for i in range(16):
            if abs(S[i*2+2+(N<0)])>=abs(N):
                ans|=1<<(i*2+(N<0))
                N-=l[i*2+(N<0)]
                break
    print(format(ans,'b'))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# solution
import io
import math

data = int(input())
result=""
counter=1
if data==0:
	result="0"
while data:
	t=counter
	counter*=-2
	if data%counter:
		data-=t
		result+="1"
	else:
		result+="0"
print(result[::-1])

Submission status: Accepted

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

while n!=0 :
    if n%2==0:
        ans+="0"

    else:
        ans+="1"
        if i%2==0:
            n-=1
        else:
            n+=1
    n=n//2
    i+=1
    #print(n,ans)

print(ans[::-1])

Submission status: Accepted

Solution code:
N=int(input())
if N==0:
  print(0)
  exit()
ans=[]
while N!=0:
  tmp=N%(2)
  if tmp<0:
    tmp+=2
  N=(N-tmp)//(-2)
  ans.append(str(tmp))
  
ans=ans[::-1]
Ans=''.join(ans)
print(Ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 6)


def input(): return sys.stdin.readline().rstrip()


N = int(input())
l = deque()
if N == 0:
    print(0)
else:
    while N != 0:
        x = (-2) ** len(l)
        y = (-2) * x
        if abs(N) % abs(y) != 0:
            N -= x
            l.appendleft('1')
        else:
            l.appendleft('0')
    print(''.join(l))

Submission status: Accepted

Solution code:
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


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

    N = ii()
    ret = ""
    while N != 0:
        ret = str(N%2) + ret
        N = -1 * (N//2)
    print(0 if ret == "" else ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7


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

    N = ii()
    ret = ""
    while N != 0:
        ret = str(N%2) + ret
        N = -(N//2)
    print(0 if ret == "" else ret)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from math import floor
N=int(input())
l=[0]*41
ans=""
for i in range(40,-1,-1):
    #print(i,pow(-2,i),N,N/abs(pow(-2,i)))
    n=abs(N/abs(pow(2,i)))
    if n>=1:
        if N/abs(pow(-2,i))<0:#Nは0未満
            N=N+abs(pow(-2,i))
            if i%2==0:
                l[i]=-1
            else:
                l[i]=1
        else:
            N = N - abs(pow(-2, i))
            if i%2==0:
                l[i]=1
            else:
                l[i]=-1
#print(l)
for i in range(40):
    if l[i]==-1:
        l[i]=1
        l[i+1]=l[i+1]+1
    elif l[i]==2:
        l[i]=0
        l[i+1]=l[i+1]-1
    elif l[i]==-2:
        l[i]=0
        l[i+1]=l[i+1]+1
flag=0
#print(l)
for i in range(40,-1,-1):
    if l[i]==1:
        flag=1
        ans="".join((ans,str(l[i])))
    elif flag==1:
        ans = "".join((ans,str(l[i])))
if len(ans)==0:
    ans="0"
print(ans)

Submission status: Accepted

Solution code:
def log2(n):
    i = 1
    r = 0
    if n < 0:
        i = 2
        r = 1
        n = -n
    s = i
    while n > s:
        i *= 4
        s += i
        r += 2
    return r


def resolve():
    n = int(input())
    if n == 0:
        print(0)
        return
    ans = [0] * 40
    while n:
        l = log2(n)
        ans[l] += 1
        n = n - (-2) ** l
    while ans[-1] == 0:
        ans.pop()
    print("".join([str(x) for x in ans[::-1]]))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math, sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import lru_cache
from heapq import heapify, heappop, heappush
from itertools import accumulate, combinations, permutations
input = sys.stdin.readline
mod = 10**9 + 7
ns = lambda: input().strip()
ni = lambda: int(input().strip())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n = ni()
ans = ''
while n != 0:
    r = n % 2
    if r < 0:
        r += 2
    n = (n - r) // (-2)
    ans += str(r)
if ans == '':
    print(0)
else:
    print(ans[::-1])

Submission status: Accepted

Solution code:
import sys

def base_convert(n, b):
  if not n: return 0
  res = ''
  while n:
    n, r = divmod(n, b)
    if r < 0: n += 1; r -= b
    res += str(r)
  return int(res[::-1])

n = int(sys.stdin.readline().rstrip())

def main():
    print(base_convert(n, -2))

if __name__ ==  '__main__':
    main()

Submission status: Accepted

Solution code:
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    # S_0はNが奇数の時1で、そうでないとき0にする必要があります
    # 基本的にはNを-2で割って、割った余りを答えに追加していくような感じ。
    # N = (-2)q + r
    # としたときに、rが0か1になるようにqを調節するということになります。
    # Nが偶数ならr = 0
    # Nが奇数ならr = 1
    # 単にNを2で割るのと変わらない
    # N % 2 の値は0か-1になるので、 -1 になるならそれに２を足す
    str_ = ""
    while n != 0:
        # N を2で割ったあまりを求める
        r = n % 2
        if r < 0:
            r += 2 # nがマイナスだと、rがマイナスになったりするので2を足す
        n = (n-r)// (-2)
        # - 2で割る
        str_ += str(r)
    #向きが逆なので反転
    str_ = str_[::-1]
    if str_ == '':
        str_ = '0'
    print(str_)



if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
N = int(input())
ans = ""
b = -2
while N:
    n = N % b
    if n:
        ans = "".join(["1", ans])
    else:
        ans = "".join(["0", ans])

    N += n
    b *= - 2
print(ans if ans else 0)

Submission status: Accepted

Solution code:
N = int(input())

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

ans = []

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

	n = (n - r) // (-2)
	ans.append(r)

if ans == []:
	ans.append(0)
ans = ans[::-1]

print(*ans, sep='')

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 10
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)

def main():
    n = int(input())
    s = []
    if n == 0:
        print('0')
        return

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

if __name__ =='__main__':
    main()

Submission status: Accepted

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

while (n!=0):
    r = int(n%2)
    if(r<0):
        r += 2
    lst.append(r)
    n = (n-r)/(-2)

if len(lst) ==0:
    print("0")
else:
    for i in range(len(lst)):
        print(lst[-1-i],end="")
    print()

Submission status: Accepted

Solution code:
n = int(input())

ans = ''

a = n
while True:
    if abs(a) % 2 == 1:
        a -= 1
        ans = '1' + ans
    else:
        ans = '0' + ans

    if abs(a) == 0:
        break
    a /= -2

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
while n!=1 and n!=0:
  l.append(abs(n)%2)
  if n>0:
    n=-n
    n//=(-2)
    n=-n
  elif n<0:
    n=abs(n)
    n//=(-2)
    n=-n
l.append(n)
l=l[::-1]
ans=str()
for i in l:
  ans+=str(i)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
digits = []
i = 1
while N != 0:
    if N % pow(2,i) == 0:
        digits.append('0')
    else:
        digits.append('1')
        N -= pow(-2,i-1)
    i += 1

if digits:
    print("".join(reversed(digits)))
else:
    print("0")

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


def check(n):
    if n == 0:
        return ''
    if n % 2 == 0:
        return check(n // (-2)) + '0'
    return check((n - 1) // (-2)) + '1'


n = int(readline())
if n == 0:
    print(0)
else:
    print(check(n))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
  print(0)
  exit(0)
for k in range(100):
    if -2*pow(4,k) +2 < 3*n < pow(4,k) - 1:
        break
l = 2*k

delta = n - (-2*(pow(2,l)-1)//3)

var = delta ^ (2*(pow(2,l)-1)//3)

ans = ''
while var > 0:
    if var&1:
        ans ='1'+ans
    else:
        ans ='0'+ans
    var = var >> 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=[]
while n!=1 and n!=0:
  l.append(abs(n)%2)
  if n>0:
    n=-n
    n//=(-2)
    n=-n
  elif n<0:
    n=abs(n)
    n//=(-2)
    n=-n
l.append(n)
l=l[::-1]
ans=str()
for i in l:
  ans+=str(i)
print(ans)

Submission status: Accepted

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

if ans:
    print("".join(reversed(ans)))
else:
    print("0")

Submission status: Accepted

Solution code:
N = int(input())
p = []
if N > 0:
    for i in range(500):
        if (2**(2*i)-1)/3 < N <= (2**(2*(i+1))-1)/3:
            q = 2*i + 1
if N < 0:
    for i in range(1,500):
        if -(2**(2*i+1)-2)/3 <= N < -(2**(2*i-1)-2)/3:
            q = 2*i
if N == 0:
    q = 1
def cal(n,i):
    if i % 2 != 0:
        if (2**(i-1)-1)/3 < n <= (2**(i+1)-1)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
    elif n == 0:
        p.append(0)
        i = i-1
        if i > 0:
            cal(n,i)
    else:
        if -(2**(i+1)-2)/3 <= n < -(2**(i-1)-2)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
            
    return p
ans = cal(N,q)
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(''.join(ans))

Submission status: Accepted

Solution code:
N = int(input())
p = []
if N > 0:
    for i in range(500):
        if (2**(2*i)-1)/3 < N <= (2**(2*(i+1))-1)/3:
            q = 2*i + 1
if N < 0:
    for i in range(1,500):
        if -(2**(2*i+1)-2)/3 <= N < -(2**(2*i-1)-2)/3:
            q = 2*i
if N == 0:
    q = 1
def cal(n,i):
    if i % 2 != 0:
        if (2**(i-1)-1)/3 < n <= (2**(i+1)-1)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
    elif n == 0:
        p.append(0)
        i = i-1
        if i > 0:
            cal(n,i)
    else:
        if -(2**(i+1)-2)/3 <= n < -(2**(i-1)-2)/3:
            p.append(1)
            n = n - (-2)**(i-1)
            i = i-1
            if i > 0:
                cal(n,i)
        else:
            p.append(0)
            i = i-1
            if i > 0:
                cal(n,i)
            
    return p
ans = cal(N,q)
for i in range(len(ans)):
    ans[i] = str(ans[i])
print(int(''.join(ans)))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())

    a = 0
    for i in range(1, 40, 2):
        a -= 2**i
    b = n - a

    res = 0
    for i in range(40):
        if i%2 == 0:
            if (b>>i) & 1:
                res += 1<<i
        else:
            if ((b>>i) & 1) == 0:
                res += 1<<i

    print('{:b}'.format(res))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())

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

    a = 0
    for i in range(1, 40, 2):
        a -= 2**i
    b = n - a
    res = []
    for i in range(40):
        if i%2 == 0:
            if (b>>i) & 1:
                res.append('1')
            else:
                res.append('0')
        else:
            if (b>>i) & 1:
                res.append('0')
            else:
                res.append('1')

    res = res[::-1]
    for i in range(40):
        if res[i] == '1':
            print(''.join(res[i:]))
            exit()

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson, minimum_spanning_tree
from scipy.sparse import csr_matrix, coo_matrix, lil_matrix
import numpy as np
from functools import reduce

from collections import deque, Counter, defaultdict
from itertools import product, permutations,combinations
from operator import itemgetter
from heapq import heappop, heappush
from bisect import bisect_left, bisect_right, bisect
from fractions import gcd
from math import ceil,floor, sqrt, cos, sin, pi, factorial
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7

def main():
  n = int(readline())
  if n == 0:
    print(0)
    sys.exit()
  ans = ''
  while n!=0:
    if n%2==0:
      ans = '0' + ans
      n = n//(-2)
    else:
      ans = '1' + ans
      n=(n-1)//(-2)
  print(ans)
  
  
  
  
if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
mod = 10 ** 9 + 7
mod2 = 2 ** 61 + 1
from collections import deque
import heapq
from bisect import bisect_left, insort_left, bisect_right

_NUMINT_ALL = list(range(10))


def main():
    ans = solve()

    if ans is True or ans is False:
        YesNo(ans)
    elif ans is not None:
        print(ans)


def solve():
    N = iip(False)
    if N == 0:
        return 0

    n = N # 残りの数で表現すべき数
    result = []
    cur = -2
    for i in range(100):
        if n % cur != 0:
            result.append(1)
            n -= cur/(-2)
        else:
            result.append(0)
        cur *= -2

        if abs(cur) > abs(N) * 10:
            break


    result.reverse()
    r = []
    f = False
    for i in result:
        if f:
            r.append(i)
        elif i == 1:
            r.append(i)
            f = True

    print("".join([str(i) for i in r]))



#####################################################ライブラリ集ここから

def iip(listed=True, num_only=True):  # 数字のinputをlistで受け取る
    if num_only:
        ret = [int(i) for i in input().split()]
    else:
        ret = [int(i) if i in _NUMINT_ALL else i for i in input().split()]

    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def saidai_kouyakusuu(A):  # 最大公約数
    l = len(A)
    while True:
        m = min(A)
        mx = max(A)
        if m == mx:
            return m

        for i in range(l):
            if A[i] % m == 0:
                A[i] = m
            else:
                A[i] %= m


def sort_tuples(l, index):  # タプルのリストを特定のインデックスでソートする
    if isinstance(l, list):
        l.sort(key=lambda x: x[index])
        return l
    else:
        l = list(l)
        return sorted(l, key=lambda x: x[index])


def count_elements(l):  # リストの中身の個数を種類分けして辞書で返す
    d = {}
    for i in l:
        if i in d:
            d[i] += 1
        else:
            d[i] = 1
    return d


def safeget(l, index, default="exception"):  # listの中身を取り出す時、listからはみ出たり
    if index >= len(l):                      # マイナスインデックスになったりするのを防ぐ
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。配列の長さは", len(l), "です"]))
        else:
            return default
    elif index < 0:
        if default == "exception":
            raise Exception("".join(["safegetに不正な値 ", index, "が渡されました。負の値は許可されていません"]))
        else:
            return default
    else:
        return l[index]


def iipt(l, listed=False, num_only=True):  # 縦向きに並んでいるデータをリストに落とし込む(iip利用)
    ret = []
    for i in range(l):
        ret.append(iip(listed=listed, num_only=num_only))
    return ret


def sortstr(s):  # 文字列をソートする
    return "".join(sorted(s))


def iip_ord(startcode="a"):  # 文字列を数字の列に変換する(数字と文字は1:1対応)
    if isinstance(startcode, str):
        startcode = ord(startcode)
    return [ord(i) - startcode for i in input()]


def YesNo(s):  # TrueFalseや1, 0をYesNoに変換する
    if s:
        print("Yes")
    else:
        print("No")


def fprint(s):  # リストを平たくしてprintする(二次元リストを見やすくしたりとか)
    for i in s:
        print(i)


def bitall(N):  # ビット全探索用のインデックスを出力
    ret = []
    for i in range(2 ** N):
        a = []
        for j in range(N):
            a.append(i % 2)
            i //= 2
        ret.append(a)
    return ret

def split_print_space(s):  # リストの中身をスペース区切りで出力する
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):  # リストの中身を改行区切りで出力する
    print("\n".join([str(i) for i in s]))


def soinsuu_bunkai(n):  # 素因数分解
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):  # nCrをmodを使って計算する
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):  #  modnにおける逆元を計算
    return power(n, mod - 2)


def power(n, p, mod_=mod):  # 繰り返し二乗法でn**p % modを計算
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
if N == 0:
    print("0")
else:
    ans = []
    p = 1
    while 2**(p-1) <= abs(N):
        if N%(2**p) > 0:
            ans.append("1")
            N -= (-2)**(p-1)
        else:
            ans.append("0")
        p += 1

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

Submission status: Accepted

Solution code:
#解説参照
#「下の桁と」mod4「のみで決まる」
# 正負考慮しなくてもこれで
ans = []
n = int(input())
if n==0:
    print(0)
    exit()
while n:
    m = n%4
    if m == 0:
        ans.extend(["0","0"])
    elif m==1:
        ans.extend(["1","0"])
    elif m==2:
        ans.extend(["0","1"])
        n+=4
    else:
        ans.extend(["1","1"])
        n+=4
    n//=4
ans.reverse()
if ans[0]=="1":
    print(''.join(ans))
else:
    print(''.join(ans[1:]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

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

if len(ans) == 0:
    ans.append("0")

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

Submission status: Accepted

Solution code:
import sys
import math

def resolve():
    N = int(input())
    mods = []
    target = N
    if N == 0:
        print("0")
        return
    while True:
        if target == 1:
            mods.append("1")
            break
        v = target // (-2)
        c = target % (-2)
        if c == -1:
            v += 1
            c = 1
        mods.append(str(c))
        target = v
    mods.reverse()
    print("".join(mods))

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
N=int(input())

ans_list=[]
sgn=1
for i in range(100):
  if N%2==1:
    ans_list.append("1")
    N-=sgn
  else:
    ans_list.append("0")
    
  N//=2
  sgn*=-1
  if N==0:
    break
  
print("".join(reversed(ans_list)))

Submission status: Accepted

Solution code:
n = int(input())
def encode(k):
	if k==0:
		return '0'
	if k==1:
		return '1'
	if k % 2 == 0:
		string = '{}0'.format(encode(k // (-2)))
		return string
	if k % 2 == 1:
		string = '{}1'.format(encode((k-1) // (-2)))
		return string

print(encode(n))

Submission status: Accepted

Solution code:
import sys

def encode(n:int) -> str:
  if n == 0:
      return '0'

  if n == 1:
      return '1'

  if n % 2 == 1:
      ans = '{}1'.format(encode((n-1) // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')
      return ans

  if n % 2 == 0:
      ans = '{}0'.format(encode(n // (-2)))
      sys.stderr.write('{} for {}'.format(ans, n))
      sys.stderr.write('\n')

      return ans

n = int(input())
ans = encode(n)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())

if n == 0:
    print(0)
    quit()
base = []
while n != 1:
    if n % -2 == 0:
        base.append('0')
        n //= -2
    else:
        base.append('1')
        n -= 1
        n //= -2
base.append('1')
base.reverse()
ans = ''.join(base)
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

"""
[memo]
-9の例
N = ... + (-2)**i + ...の形をしている
1桁目
N = X + (-2)**0 or N = X + 0であり,このときXは必ず2の倍数
よって,N = X + 0 = -9は成り立たないので,N = X + (-2)**0 の形であり,1桁目は1
また,このときN = X + (-2)**0 = -9よりX = -10.
2桁目
X = Y + (-2)**1 or X = Y + 0であり,このときYは必ず4の倍数
よって,X = Y + 0 = -10は成り立たないので, X = Y + (-2)**1の形であり,2桁目は1
また,このときX = Y + (-2)**1 = -10よりY = -8.
3桁目
Y = Z + (-2)**2 or Y = Z + 0であり,このときZは必ず8の倍数
よって,Y = Z + (-2)**2 = -8は成り立たないので, Y = Z + 0の形であり,3桁目は0
また,このときY = Z + 0 = -8よりZ = -8.
4桁目
Z = W + (-2)**3 or Z = W + 0であり,このときWは必ず16の倍数
よって,Z = W + 0 = -8は成り立たないのおで, Z = W + (-2)**3の形であり,4桁目は1
また,このときZ = W + (-2)**3 = -8よりW = 0.
同様にするとこれ以降の桁は常に0なので,答1011
"""
n = I()
ans = ''
m = 2
cnt = 0
x = n
while 1:
    if x % m:
        ans += '1'
        x -= (-2)**(cnt)
    else:
        ans += '0'
    cnt += 1
    m *= 2
    if x == 0:
        break
print(ans[::-1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = ''
m = 2
cnt = 0
x = n
while 1:
    if x % m:
        ans += '1'
        x -= (-2)**(cnt)
    else:
        ans += '0'
    cnt += 1
    m *= 2
    if x == 0:
        break
print(ans[::-1])

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
ans = ''
if n == 0:
    print(0)
    quit()
while 1:
    if n == 0:
        break
    if n % -2:
        ans += '1'
        n -= 1
    else:
        ans += '0'
    n //= -2
print(ans[::-1])

Submission status: Accepted

Solution code:
n = int(input())
s = ''
value = 0
count = 0
while value != n:
    r = n % 2**(count+1)
    if (value + (-2)**count)%(2**(count+1)) == r:
        s += '1'
        value += (-2)**count
    else:
        s += '0'
    count += 1
if n == 0:
    print(0)
else:
    print(int(s[::-1]))

Submission status: Accepted

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

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

print(S[::-1])

Submission status: Accepted

Solution code:
n = int(input())
l = []
c = 1
while n != 0:
    if n % 2**c !=0:
        n -= (-2)**(c-1)
        l.append('1')
    
    else:
        l.append('0')
    
    c += 1

if len(l) == 0:
    print('0')

else:
    print(''.join(reversed(l)))