[ROI 2018] Viruses

Luogu

IDLGP9287

Time1000ms

Memory512MB

DifficultyP3

模拟贪心2018ROI（俄罗斯）

现在有 $n$ 只细胞与 $n$ 个病毒，$i$ 号细胞的初始病毒的序号也为 $i$，每个细胞心中对每位病毒都有一定的易感染度。细胞之间可以互相攻击，如果细胞甲攻击了细胞乙，且乙「对甲现在的病毒的易感染度」比「对自家病毒的易感染度」高，那么乙就会被甲的病毒感染（成为甲的病毒的细胞）。细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。如果存在一种攻击顺序，使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「可行的病毒」。如果对于任意一种攻击顺序，都使得病毒 $i$ 最终拥有一只或以上的细胞，那么我们则称病毒 $i$ 为「稳定的病毒」。现在病毒们想知道，有多少个可行的病毒与稳定的病毒。 ## Input 第一行一个正整数 $n$，表示细胞与病毒的数量。下面 $n$ 行，每行 $n$ 个正整数，表示每名病毒按当前细胞心中的易感染度降序排列后的病毒编号序列。比如输入了 `2 1 3`，则表示该细胞对 $2$ 号病毒的易感染度最高，对 $1$ 号病毒的易感染度第二高，对 $3$ 号病毒的易感染度最差。最后一行一个整数 $p$。 ## Output 第一行，一个整数 $x$。如果 $p=1$，输出稳定的病毒数量；如果 $p=2$，输出可行的病毒的数量。接下来一行， $x$ 个整数，表示这 $x$ 个病毒的编号，按升序排列。 [samples] ## Background 译自 [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T2. [Вирусы](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Viruses](https://codeforces.com/gym/102147/problem/D))。 ## Note 对于所有的数据，$1 \leq n \leq 500$。 | 子任务编号 | $n$ | $p$ | | :-----------: | :-----------: | :-----------: | | $1$ | $1 \leq n \leq 5$ | $p = 1$ | | $2$ | $1 \leq n \leq 500$ | $p = 1$ | | $3$ | $1 \leq n \leq 5$ | $p = 1,2$ | | $4$ | $1 \leq n \leq 50$ | $p = 1,2$ | | $5$ | $1 \leq n \leq 500$ | $p = 1,2$ |

Samples

Input #1

Output #1

2
1 2

Input #2

Output #2

1
3

Input #3

Output #3

3
1 3 4

API Response (JSON)

{
  "problem": {
    "name": "[ROI 2018] Viruses",
    "description": {
      "content": "现在有 $n$ 只细胞与 $n$ 个病毒，$i$ 号细胞的初始病毒的序号也为 $i$，每个细胞心中对每位病毒都有一定的易感染度。 细胞之间可以互相攻击，如果细胞甲攻击了细胞乙，且乙「对甲现在的病毒的易感染度」比「对自家病毒的易感染度」高，那么乙就会被甲的病毒感染（成为甲的病毒的细胞）。 细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。 如果存在一种攻击顺序",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9287"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "现在有 $n$ 只细胞与 $n$ 个病毒，$i$ 号细胞的初始病毒的序号也为 $i$，每个细胞心中对每位病毒都有一定的易感染度。\n\n细胞之间可以互相攻击，如果细胞甲攻击了细胞乙，且乙「对甲现在的病毒的易感染度」比「对自家病毒的易感染度」高，那么乙就会被甲的病毒感染（成为甲的病毒的细胞）。\n\n细胞们可以任意安排攻击顺序。当且仅当没有细胞可以被任意一名病毒感染时，游戏宣告结束。\n\n如果存在一种攻击顺序...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments