[语言月赛202306] 演唱会

Luogu

IDLGB3784

Time1500ms

Memory512MB

DifficultyP2

2023O2优化排序结构体语言月赛

一个特殊的节日，zyl 举办了一场演唱会，他想要规划一下演唱会的曲目。根据同学的要求，他要从 $n$ 首歌（编号 $1\sim n$）中选出 $m$ 首加入演唱会歌单。选择的规则很简单，班上有 $a$ 名学生（不包括 zyl），学号为 $1\sim a$。zyl 会按照学号统计每位同学从每首歌中得到的快乐值，记为 $h_{i,j}$。一首歌的「欢乐度」是它所给予其他所有同学的「快乐值」总和。巧妙的是，由于歌曲风格迥异，**同一个学生一定会从不同的歌中会收获不同的快乐值，且不会有任何两首歌的欢乐度相同**。 zyl 选出欢乐度最高的 $m$ 首歌，并将它们按欢乐度**从大到小**排好序。但 zyl 注意到了她的快乐值... 无论如何，zyl 一定会把她最喜欢的歌放进歌单（她获得快乐值最高的歌即为她最喜欢的歌）！如果她最喜欢的歌之前已经在歌单中，那么 zyl 会把这首歌提到歌单的第一个位置（即，仅将该歌曲的位置变为第一位，其余歌曲的相对位置不变）；但如果不在，zyl 则会把已经选择好的歌单里的最后一首歌给删掉。然后把她最喜欢的曲目放在歌单的最后。现在 zyl 将统计的快乐值数据和她的学号交给你，请你帮他列出演唱会的歌单。 ## Input 输入共 $a + 1$ 行。第一行共四个整数 $n, m, a, b$，分别代表待选的歌的数量，需要选出的歌的数量，班上的人数，她的学号。接下来 $a$ 行，每行 $n$ 个整数，第 $i+1$ 行第 $j$ 个数代表学号为 $i$ 的学生从第 $j$ 首歌收获的快乐值 $h_{i,j}$。 ## Output 输出共一行用空格隔开的 $m$ 个整数，依次代表演唱会的歌单上的歌的编号。 [samples] ## Note ### 样例 1 解释按照欢乐度排序后靠前的两道是 $3, 2$，但由于她最喜欢的歌是 $4$，不在歌单里，于是将 $2$ 从歌单里删除，之后将 $4$ 放在最后。最后的歌单为 $3, 4$。 ### 数据规模与约定对于 $100\%$ 的数据，$1\leq m \leq n \leq 10^5$，$1\leq b \leq a\leq 100$。$0\leq h_{i,j}\leq 10^6$。 | 测试点编号 | $n$ | $m$ | $a$ | $h_{i,j}$ | | :----------: | :----------: | :----------: | :----------: |:----------:| | $1 \sim 2$ | $\leq5$ | $=1$ | $\leq5$ |$\leq 10000$| | $3 \sim 4$ | $\leq1000$ | $=n$ | $\leq100$ |$\leq 10000$| | $5 \sim 6$ | $\leq 1000$ | $\leq 1000$ | $=1$ |$\leq 10000$| | $7 \sim 9$ | $\leq1000$ | $\leq1000$ | $\leq100$ |$\leq 10000$| | $10$ |$\leq 10^5$|$\leq 10^5$|$\leq 100$|$\leq 10^6$|

Samples

Input #1

Output #1

3 4

API Response (JSON)

{
  "problem": {
    "name": "[语言月赛202306] 演唱会",
    "description": {
      "content": "一个特殊的节日，zyl 举办了一场演唱会，他想要规划一下演唱会的曲目。 根据同学的要求，他要从 $n$ 首歌（编号 $1\\sim n$）中选出 $m$ 首加入演唱会歌单。 选择的规则很简单，班上有 $a$ 名学生（不包括 zyl），学号为 $1\\sim a$。zyl 会按照学号统计每位同学从每首歌中得到的快乐值，记为 $h_{i,j}$。一首歌的「欢乐度」是它所给予其他所有同学的「快乐值」总和",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1500,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3784"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个特殊的节日，zyl 举办了一场演唱会，他想要规划一下演唱会的曲目。\n\n根据同学的要求，他要从 $n$ 首歌（编号 $1\\sim n$）中选出 $m$ 首加入演唱会歌单。\n\n选择的规则很简单，班上有 $a$ 名学生（不包括 zyl），学号为 $1\\sim a$。zyl 会按照学号统计每位同学从每首歌中得到的快乐值，记为 $h_{i,j}$。一首歌的「欢乐度」是它所给予其他所有同学的「快乐值」总和...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments