现在是晚上九点,小王即将为群友们献歌一首。
群里总共有 n 位群友,小王也准备了 n+1 首歌。但群友们还没决定好让小王唱哪首。
于是群友准备按照以下规则选取小王最终唱的歌:
- 首先从 1 到 n 中选取一个数 p ,表示最先决策的人。初始时, n+1 首歌都在候选歌单中。
- 所有人按照 p,p+1,p+2,…,n−1,n,1,2,…,p−2,p−1 的顺序轮流决策。
- 在一次决策中,决策者必须从候选歌单中恰好选出一首移除候选歌单。
- 显然在所有人都决策完后,候选歌单中只会剩下一首歌,那便是小王最终给群友唱的歌。
n 位群友中的每个人对这 n+1 首歌的看法不一定相同,第 i 个人对第 j 首歌的评价值为 ai,j 。每个人都希望听到小王唱他的评价值尽可能高的歌。
保证对于所有 i , ai,1,ai,2,…,ai,n,ai,n+1 构成一个 1 到 n+1 的排列。
所有群友都绝顶聪明,均会按照最优策略决策。
现在你想知道,对于 p=1,2,3,…,n ,最终小王会唱哪首歌?
输入格式
第一行两个整数 n,seed 。
若 seed=0 ,则接下来 n 行中每行 n+1 个用空格分隔的整数。其中第 i 行的第 j 个整数表示 ai,j 。
否则不需要后续任何输入,可使用以下代码,调用 gen(n,seed)
来生成 a :
#include<bits/stdc++.h>
const int MAXN=5010;
int a[MAXN][MAXN];
void gen(int n,int seed){
std::mt19937 rnd(seed);
for(int i=1;i<=n;++i){
for(int j=1;j<=n+1;++j){
a[i][j]=j;
std::swap(a[i][j],a[i][rnd()%j+1]);
}
}
}
输出格式
一行 n 个整数,用空格分隔。其中第 i 个表示当 p=i 时小王所唱的歌。
样例数据
样例 1 输入
2 0 1 2 3 1 3 2
样例 1 输出
3 2
样例 1 解释
我们以 p=1 为例。
初始时候选歌单为 {1,2,3}
首先 1 号群友将 2 移出候选歌单,候选歌单变为 {1,3} 。
接着 2 号群友将 1 移出候选歌单,候选歌单变为 {3} 。
最终,小王将唱第 3 首歌。
子任务
对于所有数据,满足 1≤n≤5000,0≤seed≤109 。
保证对于所有 n>2000 的数据,seed≠0 。
子任务编号 | 特殊性质 | 分值 |
---|---|---|
1 | n≤8 | 8 |
2 | n≤16 | 12 |
3 | n≤500 | 32 |
4 | 无特殊性质 | 48 |