「NnOI R2-T2」Glaciaxion

Luogu

IDLGP9570

Time1000ms

Memory512MB

DifficultyP2

模拟洛谷原创O2优化

冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川，这些冰川被编号为 $1 \sim n$。探测器抵达后的 $ m $ 秒，每秒都会探测到一块冰川融化。当一块冰川第一次融化时，探测器返回 ```N```，否则返回 ```Y```。你需要根据探测器按顺序返回的信息，给出**字典序最小**的冰川融化过程的编号序列。如果不存在这样的编号序列，请输出 ```No solution``` 报告无解。 ## Input 第一行两个整数 $ n,m $。接下来一行 $ m $ 个字符（`N` 或 `Y`，不加分隔），表示探测器按顺序返回的结果。 ## Output 一行一个长度为 $ m $ 的整数序列（空格分隔），表示**字典序最小**的冰川融化过程的编号序列，或输出 ```No solution``` 报告无解。 [samples] ## Note **【样例 1 解释】** 第 1 秒，1 号冰川融化，这是其首次融化，返回 ```N```。第 2 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1 秒融化过，返回 ```Y```。第 3 秒，2 号冰川融化，这是其首次融化，返回 ```N```。第 4 秒，1 号冰川融化，这不是其首次融化，因为已经在第 1,2 秒融化过，返回 ```Y```。 **【数据范围】** 对于 $ 100\% $ 的数据，$ 1 \le n,m \le 10^6 $。 **提示：本题开启捆绑测试。** $$ \def\r{\cr\hline} \def\None{\text{None}} \def\arraystretch{1.5} \begin{array}{c|c|c} \textbf{Subtask} & \textbf{Sp. Constraints} & \textbf{Score}\r \textsf1& n,m\le 8 & 23 \r \textsf2& n,m\le 1000 & 25 \r \textsf3& 探测器返回结果只有一种字符 & 15 \r \textsf4& 保证有解 & 17 \r \textsf5& 无特殊限制 & 20 \r \end{array} $$ ### 题目来源 | 项目 | 人员 | |:-:|:-:| | idea | 船酱魔王 | | data | 船酱魔王 | | check | EstasTonne | | solution | 船酱魔王 |

Samples

Input #1

3 4
NYNY

Output #1

1 1 2 1

Input #2

5 3
YYY

Output #2

No solution

Input #3

5 7
NNNNNYN

Output #3

No solution

API Response (JSON)

{
  "problem": {
    "name": "「NnOI R2-T2」Glaciaxion",
    "description": {
      "content": "冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川，这些冰川被编号为 $1 \\sim n$。 探测器抵达后的 $ m $ 秒，每秒都会探测到一块冰川融化。 当一块冰川第一次融化时，探测器返回 ```N```，否则返回 ```Y```。 你需要根据探测器按顺序返回的信息，给出**字典序最小**的冰川融化过程的编号序列。如果不存在这样的编号序列，请输出 ```No solution``` 报告",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9570"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "冰封的世界可以看作是 $ n $ 块初始时冷冻的冰川，这些冰川被编号为 $1 \\sim n$。\n\n探测器抵达后的 $ m $ 秒，每秒都会探测到一块冰川融化。\n\n当一块冰川第一次融化时，探测器返回 ```N```，否则返回 ```Y```。\n\n你需要根据探测器按顺序返回的信息，给出**字典序最小**的冰川融化过程的编号序列。如果不存在这样的编号序列，请输出 ```No solution``` 报告...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments