← 返回题目列表

AtCoder · abc465_c

C. 反向排列

中文机器翻译题面 查看原题

分数: 300 点

问题陈述

给你一个整数 N 和一个字符串 S 长度 N 组成 o 和 x.

有一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。最初, A=(1,2,\ldots,N).

执行以下操作 A 为 k=1,2,\ldots,N 按此顺序。

  • If S_k= o,反转第一个 k 条款 A。具体来说,替换 A 与 (A_k,A_{k-1},\ldots,A_1,A_{k+1},A_{k+2},\ldots,A_N).
  • If S_k= x,什么也不做。

查找 A 所有操作完成后。

约束

  • 2\le N\le 5\times 10^5
  • N 是一个整数。
  • S 是一个长度为的字符串 N 组成 o 和 x.

输入

输入由标准输入按以下格式给出:

N
S

输出

输出以下元素 A 全部操作完成后,以空格分隔。


示例输入 1

5
ooxoo

示例输出 1

5 2 1 3 4

A 每次操作都会发生如下变化:

  • 对于 k=1:反转第一个 1 期限 A. A 变为 (1,2,3,4,5).
  • 对于 k=2:反转第一个 2 条款 A. A 变为 (2,1,3,4,5).
  • 对于 k=3:什么都不做。
  • 对于 k=4:反转第一个 4 条款 A. A 变为 (4,3,1,2,5).
  • 对于 k=5:反转第一个 5 条款 A. A 变为 (5,2,1,3,4).

所有操作完成后, A is A=(5,2,1,3,4).


示例输入 2

7
ooooooo

示例输出 2

7 5 3 1 2 4 6

示例输入 3

15
xooxoxoxoxoxxoo

示例输出 3

15 11 10 7 6 3 1 2 4 5 8 9 12 13 14