QOJ.ac

QOJ

Time Limit: 3.0 s Memory Limit: 512 MB Total points: 100

#12711. Kabaleo Lite

Statistics

Kabaleo Lite 是一款棋盘游戏。棋盘由若干堆不同颜色的圆锥形筹码组成。只有每堆筹码最顶端的那枚筹码的颜色是可见的。

每位玩家都有一个唯一的目标颜色和一套彩色筹码。目标颜色对其他玩家是隐藏的,而筹码集合则是可见的。轮到某位玩家时,他会选择自己的一枚筹码并将其放置在棋盘上的某一堆筹码顶端,从而将该堆筹码的可见颜色变为所选筹码的颜色。

在最后一轮结束后,计算棋盘上每种颜色的可见筹码数量。获胜颜色是出现次数最多的颜色。拥有该颜色作为目标颜色的玩家(如果有的话)赢得游戏。如果没有这样的玩家,或者有两种及以上颜色并列出现次数最多,则游戏以平局告终。

你正在进行 Kabaleo Lite 游戏中的最后一手棋。其他玩家也各剩下一枚筹码。你想要确定所有能让你赢得游戏的可能走法。你不知道其他玩家的目标颜色,也无法预测他们的走法,因此你的走法必须保证无论对手如何行动,你都能获胜。

输入格式

第一行包含四个整数 $n, p, c$ 和 $h$,分别表示棋盘上的堆数 ($1 \le n \le 10^6$)、玩家人数 ($1 \le p \le 10^6$)、筹码颜色总数 ($p \le c \le 10^6$) 以及你的目标颜色 ($1 \le h \le c$)。

第二行包含 $n$ 个整数 $b_i$,表示棋盘上每一堆筹码当前的可见颜色 ($1 \le b_i \le c$)。

第三行包含 $p$ 个整数 $l_i$,表示每位玩家手中最后一枚筹码的颜色 ($1 \le l_i \le c$)。玩家按顺序编号为 $1$(你)到 $p$。

输出格式

第一行包含一个整数 $w$,表示获胜走法的数量。

第二行包含 $w$ 个不同的整数 $m_i$,表示为了获胜你应该将筹码放置在哪些堆上。堆的编号从 $1$ 开始,顺序与输入文件中给出的可见颜色顺序一致。你可以在这一行以任意顺序输出这些编号。

请记住,你的走法必须保证无论其他所有玩家如何行动,你都能获胜。

样例

输入格式 1

6 3 4 2
2 1 2 3 2 2
2 1 1

输出格式 1

1
2

说明

注意,如果你将筹码放在第 4 堆,其他玩家可能会将他们的筹码放在第 1 堆和第 3 堆,这会导致平局,因为第一种颜色和第二种颜色的可见筹码数量相同(均为 3 枚)。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.