QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB Total points: 100
[+14]

# 5095. 九王唱

Statistics

现在是晚上九点,小王即将为群友们献歌一首。

群里总共有 n 位群友,小王也准备了 n+1 首歌。但群友们还没决定好让小王唱哪首。

于是群友准备按照以下规则选取小王最终唱的歌:

  1. 首先从 1n 中选取一个数 p ,表示最先决策的人。初始时, n+1 首歌都在候选歌单中。
  2. 所有人按照 p,p+1,p+2,,n1,n,1,2,,p2,p1 的顺序轮流决策。
    • 在一次决策中,决策者必须从候选歌单中恰好选出一首移除候选歌单。
  3. 显然在所有人都决策完后,候选歌单中只会剩下一首歌,那便是小王最终给群友唱的歌。

n 位群友中的每个人对这 n+1 首歌的看法不一定相同,第 i 个人对第 j 首歌的评价值为 ai,j 。每个人都希望听到小王唱他的评价值尽可能高的歌。

保证对于所有 iai,1,ai,2,,ai,n,ai,n+1 构成一个 1n+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 首歌。

子任务

对于所有数据,满足 1n5000,0seed109

保证对于所有 n>2000 的数据,seed0

子任务编号 特殊性质 分值
1 n8 8
2 n16 12
3 n500 32
4 无特殊性质 48