「HOI R1」杂造选构

Luogu

IDLGP10382

Time1000ms

Memory512MB

DifficultyP7

2024Special JudgeO2优化构造Ad-hoc分类讨论洛谷比赛

若一个序列 $a$ 满足以下要求： - $a_i=-1$ 或 $a_i\in [1,n]$。 - 对于每个 $a_i\not=-1$，将 $a_i\to i$ 连边而形成的图不存在环。则称这个序列是合法的。现给定整数 $x$ 与序列 $a$，满足序列 $a$ 所有元素是 $[-1,n]$ 范围内的整数。请你将所有 $a_i=0$ 的位置替换成其他整数，使得 $\sum\limits ^{n} _{i=1} a_i = x$ 且 $a$ 是合法的。若不存在这样一种方案，则报告无解。 ## Input 第一行两个整数 $n$ 和 $x$。第二行 $n$ 个整数，表示 $a$ 序列。保证 $\forall a_i \in [-1,n]$。 ## Output 若无解，则说明你被骗了，因此输出一个字符串 `Rick`。否则输出 $n$ 个整数，表示替换完所有为 $0$ 的元素后的 $a$ 序列。 [samples] ## Background 小 $\iiint$ 跟这个烦人的构造没有任何关系。 ## Note **本题开启捆绑测试。** | Subtask | 分值 | $n \le$ | $x \le$ |特殊性质 | | :----------: | :----------: | :----------: | :----------: | :----------: | | #0 | $13$ | $15$ | $225$|无| | #1 | $24$ | $10^3$ | $10^9$|无| | #2 | $27$ | $10^5$ | $10^{18}$|有| | #3 | $36$ | $10^5$ | $10^{18}$|无| *特殊性质：保证 $\forall a_i =0$。对于所有数据，满足 $1 \le n \le 10^5,-10^{18} \le x \le 10^{18}$。 *** **Special Judge 返回值对应表** - `Accepted.` 答案正确。 - `Oops, your answer is wrong. 1` 答案为无解，选手代码输出有解。 - `Oops, your answer is wrong. 2` 选手输出的 $\sum a_i \not = x$。 - `Oops, your answer is wrong. 3` 选手输出中含有 $0$。 - `Oops, your answer is wrong. 4` 选手输出中含有环。 - `Oops, your answer is wrong. 5` 选手输出在填空的同时将输入的 $a_i \not=0$ 的位置改动了。

Samples

Input #1

6 -6
-1 -1 -1 0 0 0

Output #1

-1 -1 -1 -1 -1 -1

Input #2

6 14
0 1 4 0 1 4

Output #2

-1 1 4 5 1 4

Input #3

6 10
0 0 0 0 0 0

Output #3

-1 -1 4 5 -1 4

Input #4

6 6
1 1 0 0 0 0

Output #4

Rick

Input #5

6 40
0 0 0 0 0 0

Output #5

Rick

API Response (JSON)

{
  "problem": {
    "name": "「HOI R1」杂造选构",
    "description": {
      "content": "若一个序列 $a$ 满足以下要求： - $a_i=-1$ 或 $a_i\\in [1,n]$。 - 对于每个 $a_i\\not=-1$，将 $a_i\\to i$ 连边而形成的图不存在环。 则称这个序列是合法的。 现给定整数 $x$ 与序列 $a$，满足序列 $a$ 所有元素是 $[-1,n]$ 范围内的整数。请你将所有 $a_i=0$ 的位置替换成其他整数，使得 $\\sum\\limits ^{",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10382"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "若一个序列 $a$ 满足以下要求：\n\n- $a_i=-1$ 或 $a_i\\in [1,n]$。\n- 对于每个 $a_i\\not=-1$，将 $a_i\\to i$ 连边而形成的图不存在环。\n\n则称这个序列是合法的。\n\n现给定整数 $x$ 与序列 $a$，满足序列 $a$ 所有元素是 $[-1,n]$ 范围内的整数。请你将所有 $a_i=0$ 的位置替换成其他整数，使得 $\\sum\\limits ^{...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments