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
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

class minus2:
    def __init__(self, arr):
        self.arr = deque(arr)

    def __add__(self, other):
        d = max(len(self), len(other))
        ret = deque([0] * d)
        #print(ret)
        for i in range(1, d+1):
            #print(ret)
            if len(self) >= i:
                ret[-i] += self[-i]
            if len(other) >= i:
                ret[-i] += other[-i]
            if ret[-i] > 1:
                while len(ret) < i+2:
                    ret.appendleft(0)

                delta = ret[-i] // 2
                ret[-i] -= delta * 2
                ret[-i-1] += delta
                ret[-i-2] += delta
            if len(ret) > 1 and ret[0] > 0 and ret[1] > 1:
                delta = max(ret[0], ret[1] // 2)
                ret[0] -= delta
                ret[1] -= delta * 2
                while not ret[0] and len(ret) > 1:
                    ret.popleft()
        '''k = d+1
        while len(ret) >= k:
            print(ret)
            if ret[-k] > 1:
                while len(ret) < k + 2:
                    ret.appendleft(0)
                delta = ret[-k] // 2
                ret[-k] -= delta * 2
                ret[-k - 1] += delta
                ret[-k - 2] += delta
            k += 1'''
        return minus2(ret)

    def __getitem__(self, idx):
        return self.arr[idx]

    def __setitem__(self, i, val):
        self.arr[i] = val

    def __len__(self):
        return len(self.arr)

    def __str__(self):
        return str(self.arr)

def get_val(k, minus = False):
    if minus:
        if k % 2:
            tmp = [0] * (k+1)
            tmp[0] = 1
            return minus2(tmp)
        else:
            tmp = [0] * (k+2)
            tmp[0] = 1
            tmp[1] = 1
            return minus2(tmp)
    else:
        if k % 2:
            tmp = [0] * (k+2)
            tmp[0] = 1
            tmp[1] = 1
            return minus2(tmp)
        else:
            tmp = [0] * (k+1)
            tmp[0] = 1
            return minus2(tmp)

def run():
    N = intread()
    minus = False
    if N < 0:
        minus = True
        N *= -1
    L = N.bit_length()
    ans = minus2([0])
    for k in range(L):
        #print(k)
        #print(ans)
        if (N >> k) & 1:
            #print(k, get_val(k, minus))
            ans += minus2(get_val(k, minus))

    for v in ans:
        print(v, end='')


if __name__ == "__main__":
    #print(math.gcd(0, 10))
    run()

Submission status: Accepted

Solution code:
N = int(input())
start = 0
end = 1
Judge = [(1, 1)]
for i in range(1, abs(N)):
    start_ = start + (-2) ** i
    end_ = end + (-2) ** i
    Judge.append((start_, end_))
    start = min(start, start_)
    end = max(end, end_)
    if start <= N <= end:
        break

n = len(Judge)
A = ['0'] * n

for i in range(n)[::-1]:
    start, end = Judge[i]
    if start <= N <= end:
        A[i] = '1'
        N -= (-2) ** i
print(''.join(A[::-1]))

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
  print(0)
  exit()
a = [1]
p = [1]
m = [0]
hi = [1]
lo = [1]
i = 0
while(True):
  if n >= lo[i] and n<= hi[i]:
    break
  i += 1
  a.append(a[i-1]*-2)
  if i%2==0:
    p.append(p[i-1]+a[i])
    m.append(m[i-1])
  else:
    p.append(p[i-1])
    m.append(m[i-1]+a[i])
  hi.append(a[i]+p[i-1])
  lo.append(a[i]+m[i-1])
ans = []
for j in range(i+1)[::-1]:
  if n >= lo[j] and n<= hi[j]:
    ans.append(1)
    n-=a[j]
  else:
    ans.append(0)
print(*ans,sep="")

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    N = input_int()
    ans = ""
    while N:
        r = N % 2
        if r < 0:
            r += 2
        N = (N - r) // (-2)
        ans += str(r)
    ans = ans[::-1]
    if ans:
        print(ans)
    else:
        print(0)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = ""
if n == 0:
    print(0)
    exit()
    
while True:
    si = n % 2
    if si == -1:
        si = 1
    s += str(si)
    n = (n-si)//(-2)
    if n == 0:
        break
print(s[::-1])

Submission status: Accepted

Solution code:
x=[0]*32
x[0]=1
x[1]=-2
for i in range(2,32):
  x[i]=x[i-2]+(-2)**i
n=int(input())
if n==0:
  print(0)
  exit()
ans=''
for i in range(2,33)[::-1]:
  if i%2:
    l=x[i-2]
    r=x[i-1]
  else:
    l=x[i-1]
    r=x[i-2]
  t=n-(-2)**i
  if l<=t and t<=r:
    n=t
    ans=ans+'1'
  else:
    ans=ans+'0'
ls=['10','11','00','01']
ans=ans+ls[n+2]
for i in range(len(ans)):
  if ans[i]=='1':
    re=i
    break
print(ans[re:])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n = i_input()
    l = []
    cnt = 0
    while True:
        if cnt%2 == 0:
            l.append(n%2)
            n = -(n//2)
            cnt += 1
        else:
            l.append(n%2)
            n = -(n//2)
            cnt += 1
        if n == 0:
            break
        # break
    l.reverse()
    print("".join(map(str,l)))


if __name__=="__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
    print(0)
    exit()
d = []
while n != 0:
    p = n % 2
    d.append(p)
    n = (n - p) * (-1) // 2
for u in reversed(d):
    print(u, end='')
print()

Submission status: Accepted

Solution code:
import sys
 
N = int(sys.stdin.readline())
if N == 0:
    print(0)
    sys.exit()
binN = ""
pN = abs(N)
while N != 0:
    if abs(N % -2) == 1:
        binN += "1"
    else:
        binN += "0"
    N += N%(-2)
    N //= -2
print(binN[::-1])

Submission status: Accepted

Solution code:
N=int(input())
# 1011: -9
# 101  1 + 4 =5
# 10: -2
# 1

def calc(x):
    ans=""
    
    while True:

        if x%2==0:
            ans="0"+ans
        else:
            ans="1"+ans
            x-=1
        if x==0:
            break

        x = x//(-2)
    return ans

a=calc(N)

print(a)

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline())
if N == 0:
    print(0)
    sys.exit()
binN = ""
pN = abs(N)
while N != 0:
    if abs(N % -2) == 1:
        binN += "1"
    else:
        binN += "0"
    N += N%(-2)
    N //= -2
print(binN[::-1])

Submission status: Accepted

Solution code:
N = int(input())


def max_pos_number(n):
    val = 0
    for i in range(n):
        if i % 2 == 0:
            val += 2**i
    return val


def min_pos_number(n):
    val = 0
    for i in range(n):
        if i % 2 == 1:
            val -= 2**i

    return val


n = 1
while True:
    if min_pos_number(n) <= N <= max_pos_number(n):
        break
    n += 1

result = []
for i in range(n-1, -1, -1):
    if i % 2 == 0:
        if N > max_pos_number(i):
            result.append(1)
            N -= (-2) ** i
        else:
            result.append(0)
    else:
        if N < min_pos_number(i):
            result.append(1)
            N -= (-2) ** i
        else:
            result.append(0)
print(''.join([str(x) for x in result]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
a = 2
ans = ""
for i in range(1000):
    if N % a == 0:
        ans = "0"+ans
    else:
        ans = "1"+ans
        if i % 2 == 0:
            N -= 2**i
        else:
            N += 2**i
    a *= 2
    if N == 0:
        break
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
if N == 0:
  print(0); exit()
ans = []
while N !=0:
  #print(ans,N)
  if N%2 == 0:
    ans.append(0)
  else:
    N -= 1
    ans.append(1)
  N//=-2
#print(ans)
ans = reversed(ans)
print(''.join([str(n) for n in ans]))

Submission status: Accepted

Solution code:
N = int(input())
def solve(N):
    if N == 0:
        return '0'
    ans = ''
    while N != 0:
        ans += str(N & 1)
        N >>= 1
        N *= -1
    return ans[::-1]
print(solve(N))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
def po(n,k):
    if k <= 0:
        return 0 <= n <= 1
    if k % 2 == 0 and -2*(2**k-1)//3 <= n <= (2**(k+2)-1)//3:
        return True
    elif k % 2 == 1 and -2*(2**(k+1)-1)//3 <= n <= (2**(k+1)-1)//3:
        return True
    return False

def f(n):
    k = 0
    while True:
        if po(n,k):
            break
        k += 1
    ls = []
    while k >= 0:
        if po(n-(-2)**k, k-1):
            n -= (-2)**k
            ls.append("1")
        else:
            ls.append("0")
        k -= 1
    return "".join(ls)
print(f(N))

Submission status: Accepted

Solution code:
n = int(input())

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

ans = ''

flag = True

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

    n = n // 2
    flag = not flag

print(ans[::-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# C - Base -2 Number
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def positive_solve(n):
    for i in range(1,30):
        if (4**i-1) // 3 >= n:
            tmp = i
            break
    return 2*tmp-2
    
def negative_solve(n):
    for i in range(1,30):
        if (4**i-1)*2 // 3 >= n:
            tmp = i
            break
    return 2*tmp-1

N = int(readline())
A = []
while True:
    if N == 0:
        break
    if N > 0:
        bit = positive_solve(N)
        A.append(bit)
        N -= 2**bit
    else:
        bit = negative_solve(-N)
        A.append(bit)
        N += 2**bit
        
S = len(A)
if S == 0:
    print(0)
else:
    A = sorted(A)
    p = 0
    ans = ''
    for i in range(A[-1]+1):
        if i == A[p]:
            ans += '1'
            p += 1
        else:
            ans += '0'
    print(ans[::-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N=ii()
    if N == 0:
        print(0)
        exit()

    ans = []
    while N != 1:
        # print(N)
        if N % 2 == 0:
            ans.append("0")
            q = N // (-2)
            N = q

        else:
            ans.append("1")
            q = (N-1) // (-2)
            N = q
        

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





if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = int(input())

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

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

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
if N==0:
    print(0)
    exit()
ans = ""
tmp = N
while tmp != 0:
    div, mod = divmod(tmp, -2)
    if mod == -1:
        div += 1
        mod = 1
    ans += str(mod)
    tmp = div

print(ans[::-1])

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    if N == 0:
        print(0)
    ans = ''
    base = 1
    while N != 0:
        if N % (base * -2) == 0:
            ans += '0'
        else:
            ans += "1"
            N -= base
        base *= -2
    ans = list(ans)
    ans.reverse()
    print(''.join(ans))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

n = int(input())

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

ans = ''
while abs(n) > 0:
    r = n%2 
    ans += str(r) 
    n //= 2
    n = -n

if abs(n)%2 == 1:
    print(ans)
else:
    print(ans[::-1])

Submission status: Accepted

Solution code:
def mod(i,j):
    if i%j == 0:
        return [str(0), i//j]
    else:
        return [str(-(i%j)),(i//j)+1]

n = int(input())
w = ""
if n == 0:
    w = 0
else:
    while n != 0:
        i,j = mod(n,-2)
        w = i + w
        n = j
print(w)

Submission status: Accepted

Solution code:
#coding:utf-8

import sys
import bisect

SUM_P = [2**x for x in range(0, 31, 2)]
SUM_M = [2**x for x in range(1, 31, 2)]
for i in range(len(SUM_P)-1):
    SUM_P[i+1] += SUM_P[i]
for i in range(len(SUM_M)-1):
    SUM_M[i+1] += SUM_M[i]


N = int(input())

ret = 0
while N != 0:
    if N > 0:
        idx = bisect.bisect_left(SUM_P, N)
        idx = idx * 2
        N -= 2 ** idx
        ret += 2**idx
    else:
        idx = bisect.bisect_left(SUM_M, abs(N))
        idx = (idx * 2) + 1
        N += 2 ** idx
        ret += 2**idx

print(format(ret, "b"))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n=int(input())

ans=[0]

for i in range(2**20):
  ch=0
  for j in range(20):
    
    if (i>>j)&1:
      ch+=2**(j*2)
  ans.append(ch)
  
ans1=[]
for x in range(2**20):
  ch1=0
  for y in range(20):
    if (x>>y)&1:
      ch1+=(-2)**(y*2+1)
  ans1.append(ch1)
  

for a in ans1:
  if n-a>=0:
    d=bisect.bisect_right(ans,n-a)
    if ans[d-1]==n-a:
      ans_min=a
      ans_plus=ans[d-1]
      break
      
v=1
C=0
while v<=ans_plus:
  v*=4
  C+=2
C-=2
pl_list=[]
while C>-1:
  if ans_plus>=2**C:
    pl_list.append(1)
    ans_plus-=2**C
    C-=2
  else:
    pl_list.append(0)
    C-=2
w=-2
D=1

while ans_min<=w:
  w*=4
  D+=2
D-=2

mi_list=[]
while D>0:
  if ans_min<=(-2)**D:
    mi_list.append(1)
    ans_min-=(-2)**D
    D-=2
  else:
    mi_list.append(0)
    D-=2

ans_str=[]
P=deque(pl_list)
M=deque(mi_list)

while P or M:
  if P:
    x=P.pop()
  else:
    x=0
  if M:
    y=M.pop()
  else:
    y=0
  ans_str.append(str(x))
  ans_str.append(str(y))

ans_str_r=list(reversed(ans_str))
if len(ans_str_r)>1:
  if ans_str_r[0]=='0':
    ans_str_r.remove('0')
  
if n!=0:
  print(''.join(ans_str_r))
else:
  print(0)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n = int(input())

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

ans = []
while n != 0:
    ans.append(n % 2)
    n = - (n // 2)
print(''.join(map(str, reversed(ans))))

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    s = []
    if n==0:
        print(0)
        return
    while n!=1:
        if n%(-2)==-1:
            n = n//(-2)+1
            s.append(1)
        else:
            s.append(0)
            n = n//(-2)
    s.append(n)
    s.reverse()
    print(''.join([str(x) for x in s]))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,S,p=int(input()),[],1
if N==0: print(0)
while N!=0:
    R=N%2
    S.append(R)
    N=(N-p*R)//2
    p*=-1
print(*reversed(S), sep="")

Submission status: Accepted

Solution code:
def main():
	import math
	N = int(input())
	n = math.ceil(math.log(100000000000, 4)) # toriaezu BIG ENOUGH na number
	M = int('10' * n, 2)
	B = format(N + M, 'b')
	print(even_toggle(B))

def even_toggle(b):
	r = []
	for i in range(len(b)):
		if i % 2 == 0:
			r.insert(0, b[-i-1])
		else:
			r.insert(0, str(1 - int(b[-i-1])))
	head_zeroes = 0
	for i in range(len(r)):
		if r[i] == "0":
			head_zeroes += 1
		else:
			break
	return "".join(r[head_zeroes:]) or "0"

main()

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

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

        print(''.join([str(i) for i in reversed(ans)]))

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
N=int(input())

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

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

Submission status: Accepted

Solution code:
N = int(input())
 
def base(x, n):
  ret = []
  while x != 0:
    ret.append( x % abs(n))
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return ret
 
if N == 0:
  print(0)
else:
  print("".join(map(str, reversed(base(N, -2)))))

Submission status: Accepted

Solution code:
import sys
n = int(input())
if n == 0:
    print(0)
    sys.exit()
ans = []
while n != 0:
    if n < 0:
        r = n % -2
        n = -(-n//-2)
        if r < 0:
            r *= -1
    else:
        r = n%2
        n = n//2
        n *= -1 
    ans.append(str(r))
ans = ans[::-1]
print(''.join(ans))

Submission status: Accepted

Solution code:

N = int(input())

def base(x, n):
  ret = []
  while x != 0:
    ret.append( x % abs(n))
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return ret

if N == 0:
  print(0)
else:
  print("".join(map(str, reversed(base(N, -2)))))

Submission status: Accepted

Solution code:
n = int(input())
if n == 0:
  print(0)
  exit()
ans = []
while n>0 or n<0:
  if n == 0:
    break
  else:
    if n%2==0:
      ans.append(0)
      n = n//(-2)
    else:
      ans.append(1)
      n = (n-1)//(-2)
    
print(*ans[::-1], sep='')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
x=[]
g=0
if n==0:
    print(0)
    exit()

if n<0:
    g=1
    n=abs(n)

if n>0:
    while n>0:
        x.insert(0,n%2)
        n=n//2
    m=len(x)
    for i in range(2*m):
        x.insert(0,0)
    m=len(x)
    for i in range(m):
        if i%2==1 and x[-i-1]==1:
            x[-i-2]+=1
        if x[-i-1]==2:
            x[-i-1]=0
            x[-i-2]+=1
    if g==1:
        for i in range(m):
            x[i]*=-1
        for i in range(m):
            if x[-i-1]==-1:
                x[-i-1]=1
                x[-i-2]+=1

    a=[]
    f=0
    for i in range(m):
        if x[i]!=0:
            f=1
        if f==1:
            a.append(x[i])
    m=len(a)
    for i in range(m):
        a[i]=str(a[i])
    print("".join(a))

Submission status: Accepted

Solution code:
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
import bisect as bi
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
n=int(input())
ans=""
now=n
if n==0: print(0);exit()
while now!=0:
    if now%(-2)==-1:
        ans+="1"
        now=(now-1)//(-2)
    else:
        ans+="0"
        now=now//(-2)
print(ans[::-1])

Submission status: Accepted

Solution code:
N=int(input())
# 例外のN=0について
if N==0:
    print(0)
    exit()

a=1
b=0
up=[a]
low=[b]
ct=1
while not b<=N<=a:
    if ct%2==0:
        a+=(-2)**ct
    else:
        b+=(-2)**ct
    ct+=1
    up.append(a)
    low.append(b)
# print(ct)
# print(up)
# print(low)

# 頭の桁から決める
ans=['0']*ct
r=N
for i in range(ct-1):
    # print(low[ct-i-2], up[ct-i-2], r-(-2)**(ct-i-1))
    tmp=r-(-2)**(ct-i-1)
    if low[ct-i-2]<=tmp<=up[ct-i-2]:
        ans[i]='1'
        r=tmp
ans[ct-1]=str(r)
# print(ans)

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

Submission status: Accepted

Solution code:
n = int( input() )

if n == 0:
    print('0')
else:
    sum = 0
    i = 0
    S = []
    while n != 0:

        x = n % (2 ** (i+1))
        if x != 0:
            S.append('1')

            n -= (-2) ** i

        else:
            S.append('0')
        i += 1
    
    S = S[::-1]
    strS = ''.join(S)
    print(strS)

Submission status: Accepted

Solution code:
n = int(input())

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

Submission status: Accepted

Solution code:
n = int(input())

amari = []

while True:
    if n >1 or n<0:
        amari.append(-(n%(-2)))
        n = (n-(-(n%(-2))))//(-2)
    else:
        amari.append(n)
        break

gyaku = amari[::-1]
print(*gyaku,sep="")

Submission status: Accepted

Solution code:
n = int(input())

dp =[0]*40

if n ==0:
    print(0)

elif n >0:
    x = bin(n)
    bx = x[2:]
    lx = len(bx)
    for i in range(lx-1,-1,-1):
        dp[i] = int(bx[lx-1-i])
    for i in range(40):
        if i % 2 ==1 and dp[i]==1:
            dp[i+1] +=1
    while max(dp) >1:
        for i in range(40):
            if dp[i] >=2:
                dp[i] -=2
                if dp[i+1] >0:
                    dp[i+1] -=1
                else:
                    dp[i+1] +=1
                    dp[i+2] +=1
    dpr = list(reversed(dp))
    dprs = list(map(lambda x :str(x),dpr))
    dprj = "".join(dprs)
    print(int(dprj))    

else:
    x = bin(-n)
    bx = x[2:]
    lx = len(bx)
    for i in range(lx-1,-1,-1):
        dp[i] = int(bx[lx-1-i])
    for i in range(40):
        if i % 2 ==0 and dp[i]==1:
            dp[i+1] +=1
    while max(dp) >1:
        for i in range(40):
            if dp[i] >=2:
                dp[i] -=2
                if dp[i+1] >0:
                    dp[i+1] -=1
                else:
                    dp[i+1] +=1
                    dp[i+2] +=1
    dpr = list(reversed(dp))
    dprs = list(map(lambda x :str(x),dpr))
    dprj = "".join(dprs)
    print(int(dprj))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
 
ans = []
for i in range(50):
    if N%2==1:
        ans.append('1')
        if i%2==0:
            N -= 1
        else:
            N += 1
    else:
        ans.append('0')
    N //= 2
    if N==0:
        break
print(''.join(ans[::-1]))

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
from itertools import accumulate
from bisect import bisect_left

if N==0:
    print(0)
elif N>0:
    even = [0, 1]
    for i in range(1, 21):
        even.append(2**(i*2))
    cum = list(accumulate(even))
    idx = bisect_left(cum, N)
    maxi = cum[idx]-cum[idx-1]
    val = N-cum[idx-1]
    ans = ['1']
    up = maxi
    for i in range(maxi.bit_length()-1):
        up //= 2
        if val>up:
            if i%2==0:
                ans.append('0')
            else:
                ans.append('1')
            val -= up
        else:
            if i%2==0:
                ans.append('1')
            else:
                ans.append('0')
    print(''.join(ans))
elif N<0:
    N = -N
    even = [0]
    for i in range(21):
        even.append(2**(i*2+1))
    cum = list(accumulate(even))
    idx = bisect_left(cum, N)
    maxi = cum[idx]-cum[idx-1]
    val = N-cum[idx-1]
    ans = ['1']
    up = maxi
    for i in range(maxi.bit_length()-1):
        up //= 2
        if val>up:
            if i%2==0:
                ans.append('0')
            else:
                ans.append('1')
            val -= up
        else:
            if i%2==0:
                ans.append('1')
            else:
                ans.append('0')
    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()
if N>0:
  S=bin(N)[2:]
  S=list(S[::-1])
  S=list(map(int,S))
  S+=[0]*1000
  i=0
  while True:
    S[i+1]+=S[i]//2
    S[i]=S[i]%2
    if i%2==1:
      S[i+1]=S[i+1]+S[i]
    i+=1
    if i==len(S)-1:
      break
  S=list(map(str,S))
  S=list(reversed(S))
  S="".join(S)
  print(int(S))
else:
  N=abs(N)
  S=bin(N)[2:]
  S=list(S[::-1])
  S=list(map(int,S))
  S+=[0]*1000
  i=0
  while True:
    S[i+1]+=S[i]//2
    S[i]=S[i]%2
    if i%2==0:
      S[i+1]=S[i+1]+S[i]
    i+=1
    if i==len(S)-1:
      break
  S=list(map(str,S))
  S=list(reversed(S))
  S="".join(S)
  print(int(S))

Submission status: Accepted

Solution code:
n=int(input())
if n==0:
    print(0)
    exit()
ans=''
for i in range(50):
    if n%(2**(i+1))!=0:
        n-=(-2)**i
        ans='1'+ans
    else:
        ans='0'+ans
    if n==0:
        break
if ans[0]!='0':
    print(ans)
else:
    print(ans[1:])

Submission status: Accepted

Solution code:
n = int(input())
ans = []
if n == 0:
    print(0)
    exit()
for i in range(10**5):
    if n == 0:
        break
    if n%pow(2,i+1) != 0:
        ans.append('1')
        n -= pow(-2,i)
    else:
        ans.append('0')
    

ans = ans[::-1]
ans_s = ''.join(ans)
print(ans_s)

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    ans = []
    while abs(N) > 0:
        ans.append(N % 2)
        N //= 2
        N *= -1

    if ans:
        ans = ''.join(map(str, reversed(ans)))
    else:
        ans = 0

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
s = []
if N ==0:
    print(0)
    exit()
    
while N:
    r = N%(-2)
    if r<0:
        r+=2
    N = (N-r)//(-2)
    s.append(str(r))

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

Submission status: Accepted

Solution code:
n = int(input())

ans = abs(n)
for i in range(n > 0, 50, 2):
    if ans & (1 << i) == (1 << i):
        ans += (1 << (i + 1))
print(f'{ans:b}')

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    S = []
    twos = 1
    sign = 1
    while N != 0:
        if N%(2*twos) != 0:
            S.append('1')
            if sign < 0:
                N += twos
            else:
                N -= twos
        else:
            S.append('0')
        sign = -sign
        twos *= 2
    if len(S) == 0:
        S = ['0']
    S.reverse()
    print(''.join(S))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def IntBaseConvert(N,K):
    if (type(N) is int) and (type(K) is int):
        if K>=2 and N>=0:
            if N==0:
                return [0]
            else:
                ConvertNum = []
                while N>0:
                    ConvertNum.append(N%K)
                    N = N//K
                return ConvertNum[::-1]
        elif K<=-2:
            if N==0:
                return [0]
            else:
                ConvertNum = []
                while abs(N)>0:
                    ConvertNum.append(N%abs(K))
                    N = (N-N%abs(K))//K
                return ConvertNum[::-1]
        else:
            return []
    else:
        return []
      
ConvertNum = IntBaseConvert(int(input()),-2)
print(''.join(str(T) for T in ConvertNum))

Submission status: Accepted

Solution code:
def BaseM2Num(N):
    if N==0:
        return [0]
    else:
        List = []
        while abs(N)>0:
            if N%2==0:
                N //= (-2)
                List.append(0)
            else:
                N = (N-1)//(-2)
                List.append(1)
        return List[::-1]
      
List = BaseM2Num(int(input()))
print(''.join(str(T) for T in List))