Submission #56993655

---

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


Q: int = int(input())
deq = DoubleListDeque()
for _ in range(Q):
    qt, x = map(int, input().split())
    if qt == 1:
        deq.appendleft(x)
    elif qt == 2:
        deq.append(x)
    else:
        print(deq[x - 1])

Submission Info

Judge Result