#P18420. Shared Memory Switch

Shared Memory Switch

Shared Memory Switch

标准输入、标准输出。

你的任务是为共享内存交换机设计一个最优算法。

共享内存交换机是网络算法中一种简单而非平凡的缓冲架构。本题中有多个输出队列,所有数据包完全相同。每个到达的数据包都指定了一个输出队列;所有输出队列共享一个容量为 BB 的有限缓冲区。

每秒结束时,每个非空队列各发送一个数据包。当缓冲区溢出时,你的算法必须决定丢弃哪个数据包。目标是使最终发送的数据包总数最多,也就是使丢弃的数据包尽量少。

给定 nn 个事件,格式如下:

  • -1:经过一秒。
  • 整数 kk(1≤k≤n1\le k\le n):一个数据包到达第 kk 个队列。

可以认为,输入事件结束后,缓冲区中剩余的数据包也都会发送出去;等价地,输入末尾还有无限多个 -1 事件。

输入格式

第一行两个非负整数 n,Bn,B(n,B≤2⋅105n,B\le2\cdot10^5),分别为事件数量和交换机的共享缓冲区容量。

第二行包含上述格式的 nn 个事件。

输出格式

第一行输出一个整数,表示最多能发送多少个数据包。

第二行输出最终发送的数据包各自对应的原事件编号,从 1 开始。只能输出到包事件的编号,不能输出 -1 事件的编号。这些编号可以按任意顺序输出。

若没有数据包被发送,第一行仍需输出 0,第二行没有编号。n=0n=0 和 B=0B=0 均按原定义允许。

样例 1

14 5
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
9
3 6 8 5 10 4 12 14 2

样例 2

14 4
1 1 1 2 2 2 -1 1 -1 1 -1 1 -1 1
8
3 6 8 5 10 4 12 14