Submission #56992471

---

Source Code Expand

class DoubleListDeque:
    __slots__ = ("front", "back")

    def __init__(self, init_arr: list = None) -> None:
        init_arr = init_arr or []
        mid = len(init_arr)
        self.front = init_arr[:mid][::-1]
        self.back = init_arr[mid:]

    def _rebalance(self) -> None:
        source, target = (
            (self.front, self.back) if not self.back else (self.back, self.front)
        )
        mid = len(source) >> 1
        target.extend(source[: mid + 1][::-1])
        del source[: mid + 1]

    def append(self, val) -> None:
        self.back.append(val)

    def appendleft(self, val) -> None:
        self.front.append(val)

    def pop(self):
        if not self:
            raise IndexError("pop from empty deque")
        if not self.back:
            self._rebalance()
        return self.back.pop()

    def popleft(self):
        if not self:
            raise IndexError("popleft from empty deque")
        if not self.front:
            self._rebalance()
        return self.front.pop()

    def __getitem__(self, i: int):
        l = len(self)
        if i < -l or l <= i:
            raise IndexError("deque index out of range")
        i = i if i >= 0 else i + l
        if i < len(self.front):
            return self.front[~i]
        else:
            return self.back[i - len(self.front)]

    def __setitem__(self, i: int, val):
        l = len(self)
        if i < -l or l <= i:
            raise IndexError("deque index out of range")
        i = i if i >= 0 else i + l
        if i < len(self.front):
            self.front[~i] = val
        else:
            self.back[i - len(self.front)] = val

    def __len__(self) -> int:
        return len(self.front) + len(self.back)

    def __str__(self) -> str:
        return f"Deque({self._tolist()})"

    def _tolist(self) -> list:
        return self.front[::-1] + self.back


import sys


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


N, Q = map(int, input().split())
deq = DoubleListDeque([(i, 0) for i in range(1, N + 1)])
d = {"U": (0, 1), "R": (1, 0), "D": (0, -1), "L": (-1, 0)}
for _ in range(Q):
    qt, x = input().split()
    if qt == "1":
        deq.pop()
        dx, dy = d[x]
        nx, ny = deq[0][0] + dx, deq[0][1] + dy
        deq.appendleft((nx, ny))
    else:
        print(*deq[int(x) - 1])

Submission Info

Judge Result