Approach
Breadth-first search
For ABC389 C — Snake Queue, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 106 lines of Python from the credited upstream file abc389_c.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
12 3 4class Deque:5 def __init__(self, src_arr=[], max_size=300000):6 self.N = max(max_size, len(src_arr)) + 17 self.buf = list(src_arr) + [None] * (self.N - len(src_arr))8 self.head = 09 self.tail = len(src_arr)10 11 def __index(self, i):12 l = len(self)13 if not -l <= i < l:14 raise IndexError("index out of range: " + str(i))15 if i < 0:16 i += l17 return (self.head + i) % self.N18 19 def __extend(self):20 ex = self.N - 121 self.buf[self.tail + 1 : self.tail + 1] = [None] * ex22 self.N = len(self.buf)23 if self.head > 0:24 self.head += ex25 26 def is_full(self):27 return len(self) >= self.N - 128 29 def is_empty(self):30 return len(self) == 031 32 def append(self, x):33 if self.is_full():34 self.__extend()35 self.buf[self.tail] = x36 self.tail += 137 self.tail %= self.N38 39 def appendleft(self, x):40 if self.is_full():41 self.__extend()42 self.buf[(self.head - 1) % self.N] = x43 self.head -= 144 self.head %= self.N45 46 def pop(self):47 if self.is_empty():48 raise IndexError("pop() when buffer is empty")49 ret = self.buf[(self.tail - 1) % self.N]50 self.tail -= 151 self.tail %= self.N52 return ret53 54 def popleft(self):55 if self.is_empty():56 raise IndexError("popleft() when buffer is empty")57 ret = self.buf[self.head]58 self.head += 159 self.head %= self.N60 return ret61 62 def __len__(self):63 return (self.tail - self.head) % self.N64 65 def __getitem__(self, key):66 return self.buf[self.__index(key)]67 68 def __setitem__(self, key, value):69 self.buf[self.__index(key)] = value70 71 def __str__(self):72 return "Deque({0})".format(str(list(self)))73 74 75def main():76 import sys77 78 input = sys.stdin.readline79 80 q = int(input())81 d = Deque([], max_size=300100)82 minus = 083 84 for _ in range(q):85 qi = list(map(int, input().split()))86 87 if qi[0] == 1:88 l = qi[1]89 90 if len(d) == 0:91 d.append((l, l))92 minus = 093 else:94 d.append((l, l + d[-1][1]))95 elif qi[0] == 2:96 li, _ = d.popleft()97 minus += li98 else:99 k = qi[1]100 k -= 1101 print(d[k][1] - d[k][0] - minus)102 103 104if __name__ == "__main__":105 main()106