[PA 2024] Mrówki

Luogu

IDLGP10349

Time1000ms

Memory1024MB

DifficultyP3

2024PA（波兰）

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda próbna [Mrówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mro/)** 数轴上有 $n$ 只蚂蚁，第 $i$ 只位于点 $x=i$。每只蚂蚁面向右（数轴的正方向）或者向左（数轴正方向的反方向）。蚂蚁小到我们可以认为他们是独立的点。信号发出后，所有蚂蚁开始以相同的单位速度朝它们面向的方向前进。如果两只蚂蚁相撞（位于同一点），它们就会弹开，也就是说，它们都会改变行进方向，继续前进。可以证明，经过一定时间后，不会再发生碰撞。你能编写一个程序，计算出每只蚂蚁会与其他蚂蚁碰撞多少次吗？ ## Input 第一行一个整数 $n\ (1\le n\le 3\times 10^5)$，表示蚂蚁的数量。第二行包含一个长为 $n$ 的字符串，字符串仅包含 `L` 和 `P`。其中第 $i$ 个字符表示蚂蚁 $i$ 面向的方向，如果为 `L`，则初始面向左，如果为 `P`，则初始面向右。 ## Output 输出一行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 只蚂蚁与其他蚂蚁的碰撞次数。 [samples] ## Note 第一只蚂蚁一开始面向左，不会与其他蚂蚁碰撞。最后一只蚂蚁会在 $x=5.5$ 处与第五只蚂蚁相撞，然后开始向右行进，并且再也不会停下来。第三只蚂蚁在 $x=3.5$ 处与第四只蚂蚁碰撞后，开始向左行走。第二只蚂蚁会在 $x=3$ 处碰撞，然后向左转，之后一直走下去。

Samples

Input #1

6
LPPLPL

Output #1

0 1 3 3 2 1

API Response (JSON)

{
  "problem": {
    "name": "[PA 2024] Mrówki",
    "description": {
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda próbna [Mrówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mro/)** 数轴上有 $n$ 只蚂蚁，第 $i$ 只位于点 $x=i$。每只蚂蚁面向右（数轴的正方向）或者向左（数轴正方向的反方向）。蚂",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 1048576
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10349"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda próbna [Mrówki](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mro/)**\n\n数轴上有 $n$ 只蚂蚁，第 $i$ 只位于点 $x=i$。每只蚂蚁面向右（数轴的正方向）或者向左（数轴正方向的反方向）。蚂...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments