Approach
Breadth-first search
For ABC217 E — Sorting Queries, 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
- 99 lines of Python from the credited upstream file abc217_e.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 4from heapq import heapify, heappop, heappush5from typing import List, Optional6 7 8class DeletableHeapq:9 """Alternatives to ordered set (set) in C++.10 Landau notation: O(log(n))11 See:12 https:qiita.com/physharp/items/f9229ab879cac9a944d713 https:prd-xxx.hateblo.jp/entry/2019/06/24/23584414 """15 16 def __init__(self, descending_order=False) -> None:17 self.q: List[int] = [] 18 self.p: List[int] = [] 19 self.descending_order = descending_order20 self.sign = -1 if descending_order else 121 22 def build(self, a: List[int]) -> None:23 """Build a priority-queue q from an array."""24 25 if self.descending_order:26 a = [-ai for ai in a]27 28 self.q = a29 heapify(self.q)30 31 def push(self, number: int) -> None:32 """Add a number to the priority-queue."""33 heappush(self.q, number * self.sign)34 35 def erase(self, number: int) -> None:36 """Pseudo-erase a number to the priority-queue."""37 heappush(self.p, number * self.sign)38 self.clean()39 40 def clean(self) -> None:41 """Remove top elements from q, p."""42 43 while self.p and self.q[0] == self.p[0]:44 heappop(self.q)45 heappop(self.p)46 47 def pop(self, exc=None) -> Optional[int]:48 """Pop a top value from the priority-queue."""49 self.clean()50 51 if self.q:52 return heappop(self.q) * self.sign53 return exc54 55 def top(self, exc=None) -> Optional[int]:56 """Get a top value from the priority-queue.57 Landau notation: O(1)58 Note:59 descending_order=False: min value.60 descending_order=True : max value.61 """62 self.clean()63 64 if self.q:65 return self.q[0] * self.sign66 return exc67 68 69def main():70 from collections import deque71 import sys72 73 input = sys.stdin.readline74 75 q = int(input())76 d = deque()77 hq = DeletableHeapq()78 79 for _ in range(q):80 qi = list(map(int, input().split()))81 82 if qi[0] == 1:83 d.append(qi[1])84 elif qi[0] == 2:85 if hq.q:86 h = hq.pop()87 print(h)88 else:89 di = d.popleft()90 print(di)91 else:92 while d:93 di = d.popleft()94 hq.push(di)95 96 97if __name__ == "__main__":98 main()99