Problem: 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.

Submission attempts (in order):
# coding: utf-8
import sys
import bisect


"""Template"""


class IP:
    
    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        
        return int(input())

    def IL(self):
        
        return list(map(int, self.input().split()))

    def SL(self):
        
        return list(map(str, self.input().split()))

    def ILS(self, n):
        
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        
        return [self.input() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

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

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

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





def main():
    
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    
    n = ip.I()
    
    list1 = [(-2) ** i for i in r(16)]
    list2 = [(-2) ** (i + 16) for i in r(16)]
    list1_bin, list1_val = id.Bfs2(list1)
    list2_bin, list2_val = id.Bfs2(list2)

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

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


main()

# coding: utf-8
import sys
import bisect


"""Template"""


class IP:
    
    def __init__(self):
        self.input = sys.stdin.readline

    def I(self):
        
        return int(input())

    def IL(self):
        
        return list(map(int, self.input().split()))

    def SL(self):
        
        return list(map(str, self.input().split()))

    def ILS(self, n):
        
        return [int(self.input()) for _ in range(n)]

    def SLS(self, n):
        
        return [self.input() for _ in range(n)]


class Idea:
    def __init__(self):
        pass

    def HF(self, p):
        
        return sorted(set(p[i] + p[j] for i in range(len(p)) for j in range(i, len(p))))

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

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

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





def main():
    
    
    r, e = range, enumerate
    ip = IP()
    id = Idea()

    

    
    n = ip.I()
    s = ''
    while True:
        r = n % (-2)
        n //= -2
        if r < 0:
            r += 2
            n += 1
        s += str(r)
        if n == 0: break
    print(s[::-1])


main()


Verdicts: Wrong Answer

Accepted