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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def Yes(): print("Yes"); return
def No(): print("No"); return

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def Base_10_to_n(X, n):
  if (int(X/n)):
    return Base_10_to_n(int(X/n), n)+[X%n]
  return [X%n]


#############
# Main Code #
#############

N = inputI()


if N >= 0:
  b = Base_10_to_n(N, 2)[::-1]

  ans = [0] * 100
  n = len(b)

  for i in range(n):
    if b[i] == 1:
      if i == 0:
        ans[0] = 1
      else:
        if i%2:
          if ans[i] == 1:
            ans[i] = 0
            continue
          ans[i] += 1
          ans[i+1] += 1
          if ans[i] == 2:
            ans[i] = 0
            ans[i+1] = 1
            ans[i+2] = 1
        else:
          ans[i] += 1
          if ans[i] == 2:
            ans[i] = 0
            ans[i+1] = 1
            ans[i+2] = 1
else:
  b = Base_10_to_n(-N, 2)[::-1]

  ans = [0] * 100
  n = len(b)

  for i in range(n):
    if b[i] == 1:
      if i%2 == 0:
        if ans[i] == 1:
          ans[i] = 0
          continue
        ans[i] += 1
        ans[i+1] += 1
        if ans[i+1] == 2:
          ans[i+1] = 0
          ans[i+2] = 1
          ans[i+3] = 1
      else:
        ans[i] += 1
        if ans[i] == 2:
          ans[i] = 0
          ans[i+1] = 1
          ans[i+2] = 1
  
ans = [str(i) for i in ans]
print(int("".join(ans[::-1])))

Submission status: Accepted

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

def F(N):
  if(N == 0):
    return ''
  
  if(N % 2 == 0):
    return F(N//-2) + '0'
  else:
    return F((N-1)//-2) + '1'

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement, dropwhile
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

def base10to(n, b):  # b < 0 is OK!
    if n == 0:
        return "0"
    ret = []
    while n != 0:
        r = n % b
        if r < 0:
            r += abs(b)
        n = (n-r)//b
        ret.append(str(r))
    return "".join(reversed(ret))

n = I()
print(base10to(n, -2))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def F(x):
    if x == 0:
        return ''
    if x % 2 == 0:
        return F(x//-2) + '0'
    else:
        return F((x-1)//-2) + '1'

N = ir()
answer = F(N)
if N == 0:
    answer = 0
print(answer)

Submission status: Accepted

Solution code:
N = int(input())
i=abs(N)
lis = [0 for i in range(150)]
ind= 0
if i>0:
    while i>0:
        am = i%4
        i = i//4
        if N>0:
            lis[ind]=am
            lis[ind+1]=0
        else:
            lis[ind]=am
            lis[ind+1]=am
        ind+=2

ind=0
for i in range(148):
    #print(lis)
    if lis[i]==2:
        lis[i]=0
        lis[i+1]+=1
        lis[i+2]+=1
    elif lis[i]==3:
        lis[i]=1
        lis[i+1]+=1
        lis[i+2]+=1
    elif lis[i]>=4:
        lis[i+2]+=lis[i]//4
        lis[i]%=4

lis.reverse()
if N!=0:
    fir = lis[50:].index(1)
    map = map(str,lis[fir:])
    tmp = ''.join(map)
    print(int(tmp))
else:
    print(0)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    new_s=""
    i=0
    if n==0:
        print(0)
        sys.exit()
    while n:
        x=(n>>i)&1
        new_s=str(x)+new_s
        n-=x*(-2)**i
        i+=1
    print(new_s)


if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
ans = ''
for _ in range(1000):
    r = N % 2
    if r < 0:
        r += 2
    N = (N-r)//(-2)
    ans = str(r) + ans
print(int(ans))

Submission status: Accepted

Solution code:
#絶対値小さくできるか？
#振動しそうなので
from itertools import dropwhile
from collections import deque
n=int(input())
ans=deque([["",n]])
def bfs(d):
    global ans
    l=len(ans)
    for i in range(l):
        x=ans.popleft()
        new1=[x[0]+"0",x[1]]
        if abs(new1[1])<abs((-2)**d):
            ans.append(new1)
        new2=[x[0]+"1",x[1]-(-2)**d]
        if abs(new2[1])<abs((-2)**d):
            ans.append(new2)
    if d!=0:
        bfs(d-1)
bfs(32)
#全探索

for i in ans:
    if i[1]==0:
        ans=list(dropwhile(lambda x:x=="0",i[0]))
        if len(ans)==0:
            print(0)
        else:
            print("".join(ans))
        break

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = list()
    pow_m2, mod = 1, 2
    S.append(N % mod)
    N -= (N % mod) * pow_m2
    while N != 0:
        pow_m2 *= (- 2)
        mod *= 2
        s = 1 if N % mod > 0 else 0
        S.append(s)
        N -= s * pow_m2
    S.reverse()
    print(''.join(map(str, S)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    L = 1000

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

    s = 1 if N > 0 else -1
    n = abs(N)

    bit = [0] * L

    i = 0
    while n > 0:
        if n % 2:
            bit[i] += 1
            if s > 0 and i % 2 == 1 or s < 0 and i % 2 == 0:
                bit[i+1] += 1
        n //= 2
        i += 1

    for i in range(L-2):
        b = bit[i]
        if b > 1:
            b1 = bit[i+1]
            if b1 > 0:
                if b1 >= b//2:
                    bit[i+1] -= b//2
                    bit[i] = b % 2
                else:
                    bit[i+1] = 0
                    bit[i] -= b1 * 2
            if bit[i] > 1:
                bit[i+2] += bit[i] // 2
                bit[i+1] += bit[i] // 2
                bit[i] = bit[i] % 2

    bit.reverse()
    i = bit.index(1)
    print(*bit[i:],sep='')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

N = int(input())
if not N:
    print(0)
    sys.exit()
    
S = ''

while N:
    r = N%2
    N = N//(-2)+r
    S += str(r)

print(S[::-1])

Submission status: Accepted

Solution code:
import bisect
import heapq  # 優先度付きキュー(最小値取り出し)

inf = 10 ** 15
mod = 10 ** 9 + 7

p = [] # i*2-1番までで取りうる最大の数
m = [] # i*2番までで取りうる最小の数
prep = 0
prem = 0
kaijou = []
for i in range(0,35,2):
    p.append(2**i+prep)
    m.append(2**(i+1)+prem)
    kaijou.append(2**i)
    kaijou.append(2**(i+1))
    prep = 2**i+prep
    prem = 2**(i+1)+prem

def getAns(n,i):

    if i == 0:
        if n == 0:
            return '0'
        if n == 1:
            return '1'
    else:
        if n == 0 or n == 1:
            return ''.join(['0', getAns(n, i-1)])
        elif n > 0:
            ind = bisect.bisect_left(p, n)
            if ind*2 == i:
                n -= kaijou[i]
                return ''.join(['1', getAns(n, i-1)])
            else:
                return ''.join(['0', getAns(n, i-1)])
        else:
            ind = bisect.bisect_left(m, abs(n))
            if ind*2+1 == i:
                n += kaijou[i]
                return ''.join(['1', getAns(n, i-1)])
            else:
                return ''.join(['0', getAns(n, i-1)])


n = int(input())
if n >= 0:
    ind = bisect.bisect_left(p, n)
    print(getAns(n,ind*2))
else:
    ind = bisect.bisect_left(m, abs(n))
    print(getAns(n,ind*2+1))

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    if N == 0:
        return 0
    l = set()
    while N != 0:
        if N > 0:
            r = plus(N)
            l.add(r)
            N -= pow(2, r)
        else:
            r = minus(N)
            l.add(r)
            N += pow(2, r)
    s = [0] * (max(l)+1)
    for i in range(max(l)+1):
        if i in l:
            s[i] = 1
    s.reverse()
    return ''.join(str(i) for i in s)
def plus(N):
    p = 0
    n = 0
    while True:
        p += pow(2, n)
        if p >= N:
            break
        n += 2
    return n
def minus(N):
    p = 0
    n = 1
    while True:
        p -= pow(2, n)
        if p <= N:
            break
        n += 2
    return n

print(main())

Submission status: Accepted

Solution code:
from itertools import product
def main():
    N = int(input())
    if N == 0:
        return 0
    l = set()
    while N != 0:
        if N > 0:
            r = plus(N)
            l.add(r)
            N -= pow(2, r)
        else:
            r = minus(N)
            l.add(r)
            N += pow(2, r)
    s = [0] * (max(l)+1)
    for i in range(max(l)+1):
        if i in l:
            s[i] = 1
    s.reverse()
    return ''.join(str(i) for i in s)
    #for i in product(range(2), repeat=9):
    #    r = 0
    #    for j, v in enumerate(i):
    #        r += v * pow(-2, j)
    #    l.append((r, i))
    #l.sort()
    #for x in l:
    #    print(x)
def plus(N):
    p = 0
    n = 0
    while True:
        p += pow(2, n)
        if p >= N:
            break
        n += 2
    return n
def minus(N):
    p = 0
    n = 1
    while True:
        p -= pow(2, n)
        if p <= N:
            break
        n += 2
    return n

print(main())

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

s = ""

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
  n=int(input())
  if n==0:
    print(0)
    exit()
  s=1 if n>0 else 0
  n=abs(n)
  for j in range(s,31,2):
    if ((n>>j) & 1): #立っているビットのところで処理が走る
      n+=pow(2,j+1)
  print(bin(n)[2:])
if __name__=='__main__':
  main()

Submission status: Accepted

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

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

print(ret)

Submission status: Accepted

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

if s == "":
    print(0)
else:
    print("".join(s[::-1]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#print#!/usr/bin/env python3
#%% for atcoder uniittest use
import sys
input= lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**9)
def pin(type=int):return map(type,input().split())
def tupin(t=int):return tuple(pin(t))
def lispin(t=int):return list(pin(t))
#%%code

#なお、任意の整数 M に対して M の −2 進数表現が一意に定まることが証明できます。
#2桁ごとに見るとよかった（もう実験したよ）
def resolve():
    N,=pin()
    n=N
    ans=[]
    a=["00","01","10","11"]
    b=[0,1,-2,-1]
    t=0
    for t in range(30):
        #print(n)
        n4=n%4
        ans.append(a[n4])
        n-=b[n4]
        n//=4
        if abs(n)==0:break
        
    ans.reverse()
    if ans[0][0]=="0":ans[0]=ans[0][1]
    print(*ans,sep="")
        
#%%submit!
resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def f_10_to_m2(n):
    if n == 0:
        return 0 

    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append(0)
        else:
            digits.append(1)
            n -= base
        i += 1
        base *= -2
    return ''.join(map(str, reversed(digits)))

print(f_10_to_m2(int(input())))

Submission status: Accepted

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

ans = []
d = 40

t = 0
while d >= 0:
    bottom = t+(-2)**d+(-2)*(1-4**(d//2))//(-3)
    top = t+(-2)**d+(1-4**math.ceil(d/2))//(-3)
    if bottom <= N <= top:
        ans.append('1')
        t += (-2)**d
    else:
        ans.append('0')
    d -= 1

print(int(''.join(ans)))

Submission status: Accepted

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

import sys
import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    

    def calc_covered_k(num):
        """
        abs(num) > 0 の時 -> num が -2 進数表記で k + 1 桁で表現される場合 k を返す ([k] に 1 が立つことを表す)
        """
        assert(num != 0)
        if num > 0:
            return (math.ceil(math.log(3 * num + 1, 4)) - 1) * 2
        else:
            return (math.ceil(math.log(3 / 2 * abs(num) + 1, 4)) - 1) * 2 + 1
    
    n = ii()
    if n == 0:
        print(0)
    else:
        k = calc_covered_k(n)
        ans = ['0'] * (k + 1)    # あとで反転する
        ans[k] = '1'
        n -= pow(-2, k)
        while n != 0:
            k = calc_covered_k(n)
            ans[k] = '1'
            n -= pow(-2, k)
        print(''.join(reversed(ans)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
ans = []
while abs(n) > 0:
    ans.append(n%2)
    n = (n - (n % 2)) // -2
print(''.join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
i = 0
ans = []
while abs(n) > 0:
    ans.append(n%2)
    #n = (n - n % (2 * (-1)**i)) // 2
    n = (n - (n % 2)) // -2
    i += 1
print(''.join(map(str, ans[::-1])))

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
i = 0
#for i in range(10):
ans = []
while abs(n) > 0:
    #print(n, n // (2 * (-1)**i), n % (2 * (-1)**i))
    #print(n, n % (2 * (-1)**i), n % 2)
    ans.append(n%2)
    #n = n // (2 * (-1)**i)
    n = (n - n % (2 * (-1)**i)) // 2
    i += 1
#print(n, n % (2 * (-1)**i))
#print(ans[::-1])
print(''.join(map(str, ans[::-1])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p = i % 2
        ans += str(p)
        i = - (i // 2)

    print(ans[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        ans += str(i % 2)
        i = - (i // 2)

    print(ans[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p, q = divmod(i, 2)
        if q:
            ans += "1"
        else:
            ans += "0"
        i = -p

    print(ans[::-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    i = int(input())
    if i == 0:
        print(0)
        exit()

    ans = ""
    while i:
        p, q = divmod(i, 2)
        if q:
            ans = "1" + ans
        else:
            ans = "0" + ans
        i = -p

    print(ans)


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(int(s[::-1]))

Submission status: Accepted

Solution code:
# ABC105C

n = int(input())
def sub(n):
    if n==0:
        return []
    k = 1
    count = 0
    pos = 1
    neg = 0
    while True:
        if (n>0 and pos>=n) or (n<0 and abs(neg)>=abs(n)):
            break
        count += 1
        k *= (-2)
        if k>0:
            pos += k
        else:
            neg += k
#     print(n, pos, neg, k)
    return [count] + (sub(n-k) if n>0 else sub(n-k))
out = sub(n)
if not out:
    print(0)
else:
    s = ["0"] * (max(out)+1)
    for item in out:
        s[item] = "1"
    print("".join(s[::-1]))

Submission status: Accepted

Solution code:
def abc105_c():
    n = int(input())
    # 例外処理
    if n == 0:
        print(0)
        return

    # dを超えない数の商と、余りをとる
    d = n
    bin_arr = []
    while d != 0:
        # dが正の値なら、dを超えない数は、絶対値は小さいほう
        if d > 0:
            _d = d // 2
            bin_arr.append(d % 2)
            d = -1 * _d  # さいごに-1掛ける
        # dが負の値なら、dを超えない数は、絶対値としては大きいほう
        else:
            _d = (abs(d) + 1) // 2
            bin_arr.append(abs(d) % 2)
            d = _d
        #print(d, bin_arr)

    bin_str = ''.join(map(str, reversed(bin_arr)))
    print(bin_str)

abc105_c()

Submission status: Accepted

Solution code:
n = int(input())
gu = [1]
ki = [0]
for i in range(0, 20):
  gu.append(gu[-1] + (-2)**(2 + 2*i))
  ki.append(ki[-1] + (-2)**(1 + 2*i))
ans = []
for i in range(20):
  if gu[-2-i] < n <= gu[-1-i]:
    ans.append('1')
    n-= (gu[-1-i]-gu[-2-i])
  else:
    ans.append('0')
  if ki[-1-i] <= n < ki[-2-i]:
    ans.append('1')
    n -= (ki[-1-i]-ki[-2-i])
  else:
    ans.append('0')
ans.append(str(n))
print(str(int(''.join(ans))))

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N = int(input())

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

    ans = []
    cnt = 0
    while abs(N) >= 1:
        mod_val = N % ((-2) ** (cnt + 1))
        if mod_val == 0:
            ans.append(0)
        else:
            ans.append(1)
            N -= (-2) ** cnt
        cnt += 1

    print(''.join([str(val) for val in ans[::-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" + ans
        N = N // 2
    else:
        ans = "1" + ans
        if i == 1:
            N = (N + 1) // 2
        else:
            N = (N - 1) // 2
    i = 1 - i

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())

    if N==0:
        print(0)
    else:
        nums=[]
        fugou=1  #+or-
        power=1  #2**0
        total=0
        while total!=N:
            m=N%(power*2)
            if m==total%(power*2):
                nums.append(0)
            else:
                nums.append(1)
            total+=nums[-1]*power*fugou
            fugou*=-1
            power*=2

        nums=nums[::-1]
        for i in range(len(nums)):
            print(nums[i],end="")
        print()
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
m=-2
t=0
pos=0
ans=[]
while n!=t:
  if (n-t)%m == 0:
    ans.insert(0,0)
  else:
    ans.insert(0,1)
  t+=ans[0]*(m//-2)
  m=m*(-2)

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

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

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

# 1桁目から見ていって奇数なら1があるはずなので1桁目は1とやっていく
ans = []
i = 1
while N:
    if N % 2 == 0:
        ans.append('0')
    else:
        ans.append('1')
        if i % 2 == 0:
            N += 1
        else:
            N -= 1
    N //= 2
    i += 1

zero = True
for b in reversed(ans):
    if zero and b == 0:
        continue
    elif b == 1:
        zero = False
    print(b, sep='', end='')
print()

Submission status: Accepted

Solution code:

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

print(ans[::-1])

Submission status: Accepted

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

def main():
    N = int(readline())
    if N == 0:
        print(0)
        return
    ans = []
    i = 0
    while N:
        if N % 2 == 0:
            ans.append(0)
            N //= 2
        else:
            ans.append(1)
            if i % 2 == 0:
                N -= 1
            else:
                N += 1
            N //= 2
        i += 1

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations # (string,3) 3回
from collections import deque
from collections import defaultdict
import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    str_ = ""
    while n != 0:
        r = n % 2
        if r < 0:
            r += 2
        n = (n-r)//(-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())
now=1
A=[]
while n!=0:
    if n%(now*2)==0:
        A.append(0)
    else:
        A.append(1)
        n-=now
    now*=-2
A=list(reversed(A))
S=""
for a in A:
    S+=str(a)
if len(S)==0:
    print(0)
else:
    print(S)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

if n == 0:
    print(0)
    
else:
    digits = []
    i = 0
    base = 1
    while n != 0:
        if n % (base*2) == 0:
            digits.append('0')
        else:
            digits.append('1')
            n -= base

        i += 1
        base *= -2##

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    res = []
    coef = 1
    while n:
        if n & 1:
            res.append('1')
            n -= coef
        else:
            res.append('0')
        coef *= -1
        n >>= 1
    res = ''.join(res[::-1]) if res else '0'
    print(res)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    res = []
    digit = 0
    while n:
        if (n >> digit) & 1:
            res.append('1')
            coef = 1 if digit & 1 == 0 else -1
            n -= coef * (1 << digit)
        else:
            res.append('0')
        digit += 1
    res = ''.join(res[::-1]) if res else '0'
    print(res)
resolve()

Submission status: Accepted

Solution code:
n=int(input())

s=[]
if n%2==0:
    s.append(0)
else:
    s.append(1)
nn=n
ii=0
while nn<=-1 or 2<=nn:
    nn=(nn-s[ii])//(-2)
    if nn%2==0:
        s.append(0)
    else:
        s.append(1)
    ii+=1

ss=""
for i in range(len(s)):
    ss=str(s[i])+ss
print(ss)

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 sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    res = []
    while N != 0:
        r = N % 2
        if r < 0:
            r += 2
        N = (N - r) // (-2)
        res += [str(r)]
    res = res[::-1]
    if len(res) == 0:
        print(0)
    else:
        print(''.join(res))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# returns : Nのd進数表記
def base_n_num(N, d):
    p = 1
    ans = []
    if N == 0:
        return [0]
    while N != 0:
        if N % (d**p) == 0:
            ans.append(0)
        else:
            ans.append(1)
            N -= (d**(p-1))
        p += 1
        if N == 0:
            break
    return reversed(ans)

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

    # 下の桁から求める
    ans = base_n_num(n, -2)
    print(''.join(list(map(str, ans))))

solve()