33OJ
登录 注册

#P17778. 锦木千束不是罪过

锦木千束不是罪过

背景

『心臓が逃げる!』

题目描述

千束和泷奈厌倦了石头剪刀布,所以她们打算设计一个新的手势游戏。该游戏可以形式化如下:

一个游戏可以描述为一个 nn 个点的竞赛图,每个点都有一个颜色,点 ii 的颜色为 cic_i,颜色共 mm 种,编号从 11 至 mm,保证每个颜色均有至少一个节点。

泷奈会首先选择一个颜色,记作 pp。她的策略是等概率随机地选择颜色为 pp 的某一个点。千束知道泷奈的策略(包括选定颜色和随机出招策略,但不知道具体选择哪一个点),她会选择胜率最大的一个点。

如果点 ii 在竞赛图上指向点 jj,那么选 ii 的人就战胜了选 jj 的人。特殊地,若二人选择了同一个点,视作泷奈胜利。

现在给定 n,mn,m 与所有点的颜色,泷奈请你给所有边定向,并帮她选择 pp,以最大化泷奈的胜率。

注:某人的胜率定义为,在泷奈选好颜色、千束按上述规则选好点后,泷奈可以选择的点中,选了之后能使此人获胜的点数,与泷奈可以选择的总点数之比。

输入格式

第一行输入两个正整数 n,mn,m。

第二行输入 nn 个正整数,第 ii 个数为 cic_i。

输出格式

第一行输出两个整数 a,ba,b,分别表示你构造的方案下千束选点之后,泷奈可以选择的点中选了能使自己获胜的点数,与泷奈可以选择的总点数。

对于第二行至第 nn 行,第 ii 行输出 i−1i-1 个 00 或 11,以空格隔开,其中第 jj 个数为 11 表示点 ii 战胜点 jj,否则表示点 jj 战胜点 ii。

第 n+1n+1 行输出 pp 即泷奈选择的颜色。

若存在多种符合条件的构造方案,输出任意一种均可。

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≤m≤n≤50001\le m\le n\le 5000,1≤ci≤m1\le c_i\le m。

【样例解释】

样例 #1

在设计的局面下,泷奈只能选点 22,无论千束选择哪一个点,她都会必然会落败,故泷奈的胜率是 100%100\%。

泷奈可以获胜的点数为 11,她可以选择的点总数为 11,故输出 1 1。

显然不存在更大的胜率。

样例 #2

在设计的局面下,泷奈可能会选点 1,21,2,千束只有在选择点 22 时必然会落败,选其余任意点千束都会有 50%50\% 的胜率,故而千束将会选择点 22 以外的任何点,泷奈的胜率为 50%50\%。

泷奈可以获胜的点数为 11,她可以出的点总数为 22,故输出 1 2。

可以证明无法构造出更大的胜率。


去做最想做的事情吧。