#P17778. 锦木千束不是罪过
锦木千束不是罪过
背景
『心臓が逃げる!』
题目描述
千束和泷奈厌倦了石头剪刀布,所以她们打算设计一个新的手势游戏。该游戏可以形式化如下:
一个游戏可以描述为一个 个点的竞赛图,每个点都有一个颜色,点 的颜色为 ,颜色共 种,编号从 至 ,保证每个颜色均有至少一个节点。
泷奈会首先选择一个颜色,记作 。她的策略是等概率随机地选择颜色为 的某一个点。千束知道泷奈的策略(包括选定颜色和随机出招策略,但不知道具体选择哪一个点),她会选择胜率最大的一个点。
如果点 在竞赛图上指向点 ,那么选 的人就战胜了选 的人。特殊地,若二人选择了同一个点,视作泷奈胜利。
现在给定 与所有点的颜色,泷奈请你给所有边定向,并帮她选择 ,以最大化泷奈的胜率。
注:某人的胜率定义为,在泷奈选好颜色、千束按上述规则选好点后,泷奈可以选择的点中,选了之后能使此人获胜的点数,与泷奈可以选择的总点数之比。
输入格式
第一行输入两个正整数 。
第二行输入 个正整数,第 个数为 。
输出格式
第一行输出两个整数 ,分别表示你构造的方案下千束选点之后,泷奈可以选择的点中选了能使自己获胜的点数,与泷奈可以选择的总点数。
对于第二行至第 行,第 行输出 个 或 ,以空格隔开,其中第 个数为 表示点 战胜点 ,否则表示点 战胜点 。
第 行输出 即泷奈选择的颜色。
若存在多种符合条件的构造方案,输出任意一种均可。
3 2
1 2 1
1 1
1
1 0
2
6 3
1 1 2 2 3 3
1 2
0
0 1
1 0 0
0 1 1 0
1 0 0 1 0
1
提示
【数据范围】
对所有数据,满足 ,。
【样例解释】
样例 #1

在设计的局面下,泷奈只能选点 ,无论千束选择哪一个点,她都会必然会落败,故泷奈的胜率是 。
泷奈可以获胜的点数为 ,她可以选择的点总数为 ,故输出 1 1。
显然不存在更大的胜率。
样例 #2

在设计的局面下,泷奈可能会选点 ,千束只有在选择点 时必然会落败,选其余任意点千束都会有 的胜率,故而千束将会选择点 以外的任何点,泷奈的胜率为 。
泷奈可以获胜的点数为 ,她可以出的点总数为 ,故输出 1 2。
可以证明无法构造出更大的胜率。
去做最想做的事情吧。