CF219E Parking Lot

市区有一个停车场，共有 $ n $ 个停车位，排成一行。停车位从左到右编号为 $1$ 到 $ n $。 每当有一辆车到达停车场时，管理员会为它选择一个空位置。出于安全考虑，所选位置应尽可能远离已经被占用的位置。即，所占位置距离最近的已占用车位应尽可能远。如果有多个这样的车位，管理员会选择编号最小的那个。如果停车场所有位置都为空，则车辆会被分配到编号为 $1$ 的位置。 我们认为第 $i$ 个和第 $j$ 个停车位之间的距离为 $4·|i-j|$ 米。 给你按时间顺序记录的车辆到达和离开的记录。对于每一条车辆到达的记录，输出该车辆被分配的停车位编号。

第一行包含两个用空格分隔的整数 $ n $ 和 $ m $，表示停车位的数量和记录的数量，满足 $1 \leq n,m \leq 2·10^{5}$。 接下来的 $ m $ 行，每行是一条记录，第 $i$ 行包含两个整数 $ t_{i} $ 和 $ id_{i} $（$1 \leq t_{i} \leq 2; 1 \leq id_{i} \leq 10^{6}$）。如果 $ t_{i}=1 $，表示编号为 $ id_{i} $ 的车辆到达停车场。如果 $ t_{i}=2 $，表示编号为 $ id_{i} $ 的车辆离开停车场。 记录按时间先后顺序排列。所有事件按顺序发生，没有两个事件同时发生。 保证所有记录合法： - 每辆车最多只到达一次、离开一次停车场； - 只有到达过停车场的车辆才会有离开记录； - 任何时刻停车场中的车辆数不超过 $ n $。 你可以认为车辆的编号从 $1$ 到 $10^{6}$，且互不相同。开始时停车场所有车位都是空的。

对于每一条车辆到达的记录，按照车辆到达的顺序，输出该车辆被分配的停车位编号。

由 ChatGPT 5 翻译