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):
from math import floor, ceil, log

N = int(input())

# O(logN)
def base10to(n, b):
    if n // b > 0:
        return base10to(n // b, b) + str(n % b)
    else:
        return str(n % b)

def calc_base_for_pos_N(N):
    S_base4 = base10to(N, 4) # str

    S_raw = list(map(int, tuple(''.join([digit + '0' for digit in S_base4])[:-1])))[::-1]

    # transformation. takes O(logN)
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        
        if position % 2 == 1:
            position += 1
            continue
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 2

    # postprocessing
    if S_raw[-1] == 2:
        S_raw[-1] = 0
        S_raw += [1, 1]
    elif S_raw[-1] == 3:
        S_raw[-1] = 1
        S_raw += [1, 1]
    elif S_raw[-1] == 4:
        S_raw[-1] = 0
        S_raw += [0, 1]

    S = ''.join([str(digit) for digit in S_raw])[::-1]
    return S

if N >= 0:
    print(calc_base_for_pos_N(N))
else:
    pos_N = abs(N)
    pos_S = list(map(int, list(calc_base_for_pos_N(pos_N))))
    print(pos_S)
    pos_S = pos_S[::-1]
    shifted_S = [0] + pos_S
    pos_S = pos_S + [0]
    assert len(pos_S) == len(shifted_S)
    S_raw = [shifted_S[i] + pos_S[i] for i in range(len(pos_S))]
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] = 1
        position += 1
    # postprocessing
    last_two_digits = S_raw[-2:]
    if last_two_digits == [2, 1]:
        S_raw = S_raw[:-2]
    elif last_two_digits == [3, 1]:
        S_raw[-2:] = [1]
    elif last_two_digits == [1, 2]:
        S_raw[-2:] = [1, 0, 1, 1]
    elif last_two_digits == [2, 2]:
        S_raw[-2:] = [0, 1]
    elif last_two_digits == [3, 2]:
        S_raw[-2:] = [1, 1]
    elif last_two_digits == [4, 1]:
        S_raw[-2:] = [0, 0, 1]
    elif last_two_digits == [4, 2]:
        S_raw = S_raw[:-2]
    S = ''.join([str(digit) for digit in S_raw])[::-1]
    print(S)


from math import floor, ceil, log

N = int(input())

# O(logN)
def base10to(n, b):
    if n // b > 0:
        return base10to(n // b, b) + str(n % b)
    else:
        return str(n % b)

def calc_base_for_pos_N(N):
    S_base4 = base10to(N, 4) # str

    S_raw = list(map(int, tuple(''.join([digit + '0' for digit in S_base4])[:-1])))[::-1]

    # transformation. takes O(logN)
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        
        if position % 2 == 1:
            position += 1
            continue
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 2

    # postprocessing
    if S_raw[-1] == 2:
        S_raw[-1] = 0
        S_raw += [1, 1]
    elif S_raw[-1] == 3:
        S_raw[-1] = 1
        S_raw += [1, 1]
    elif S_raw[-1] == 4:
        S_raw[-1] = 0
        S_raw += [0, 1]

    S = ''.join([str(digit) for digit in S_raw])[::-1]
    return S

if N >= 0:
    print(calc_base_for_pos_N(N))
else:
    pos_N = abs(N)
    pos_S = list(map(int, list(calc_base_for_pos_N(pos_N))))
    pos_S = pos_S[::-1]
    shifted_S = [0] + pos_S
    pos_S = pos_S + [0]
    assert len(pos_S) == len(shifted_S)
    S_raw = [shifted_S[i] + pos_S[i] for i in range(len(pos_S))]
    position = 0
    while position <= len(S_raw) - 3:
        digit = S_raw[position]
        if digit in {0, 1}:
            position += 1
            continue
        elif digit == 2:
            S_raw[position] = 0
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        elif digit == 3:
            S_raw[position] = 1
            S_raw[position + 1] += 1
            S_raw[position + 2] += 1
        else: #4
            S_raw[position] = 0
            S_raw[position + 2] += 1
        position += 1
    # postprocessing
    last_two_digits = S_raw[-2:]
    if last_two_digits == [2, 1]:
        S_raw = S_raw[:-2]
    elif last_two_digits == [3, 1]:
        S_raw[-2:] = [1]
    elif last_two_digits == [1, 2]:
        S_raw[-2:] = [1, 0, 1, 1]
    elif last_two_digits == [2, 2]:
        S_raw[-2:] = [0, 1]
    elif last_two_digits == [3, 2]:
        S_raw[-2:] = [1, 1]
    elif last_two_digits == [4, 1]:
        S_raw[-2:] = [0, 0, 1]
    elif last_two_digits == [4, 2]:
        S_raw = S_raw[:-2]
    S = ''.join([str(digit) for digit in S_raw])[::-1]
    print(S)
    

Verdicts: Wrong Answer

Accepted