{"problem":{"name":"「Wdoi-2」幻胧月睨","description":{"content":"### 简要题意 给定一个长度为 $n$ 的 01 串 $b$，要求构造一个 $n$ 阶排列 $a$，满足，对于 $a_i(2\\le i\\le n)$，记 $m_i=\\max_{j=1}^{i-1}\\{a_j\\}$，则：   - 若 $b_i=1$，则 $a_i>m_i$;   - 否则 $a_i<m_i$。 可以证明，总存在一个数列 $a$ 满足以上条件。 **如果有多组解，输出任意一种。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":128000},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8536"},"statements":[{"statement_type":"Markdown","content":"### 简要题意\n\n给定一个长度为 $n$ 的 01 串 $b$，要求构造一个 $n$ 阶排列 $a$，满足，对于 $a_i(2\\le i\\le n)$，记 $m_i=\\max_{j=1}^{i-1}\\{a_j\\}$，则：\n  - 若 $b_i=1$，则 $a_i>m_i$;\n  - 否则 $a_i<m_i$。\n\n可以证明，总存在一个数列 $a$ 满足以上条件。\n\n**如果有多组解，输出任意一种。**\n\n同时注意到 $b_1$ 的取值是任意的，对数列 $a$ 没有影响。\n\n### 原始题意\n\n铃仙拥有操纵狂气程度的能力，换而言之，就是操纵物体的波长、振幅以及相位。这种能力为主角制造了种种障碍——例如操纵光波，会让弹幕虚虚实实，甚至会出现虚假的自我，对躲避弹幕造成极大的干扰。\n\n以符卡「幻胧月睨」为例。「幻胧月睨」中一共有 $n$ 个弹幕，每个弹幕都会有一个相位，相位非 $0$ 即 $1$。这些弹幕的相位会构成一个长度为 $n$ 的数列 $\\{b_i\\}$。\n\n铃仙会操纵这些弹幕的相位，将其变得千奇百怪。具体而言，被操纵了之后的弹幕的相位是一个长度为 $n$ 的**排列** $\\{a_i\\}$，即 $1 \\sim n$ 的数字都会**不重不漏**地出现在这个序列之中。\n\n为了加大主角躲避弹幕的难度，铃仙会设置一个阈值。对于每一个元素 $a_i$，阈值是其**前缀**的**最大**值，即 $a_1,a_2,\\dots,a_{i-1}$ 中的最大值。若原来的第 $i$ 个弹幕的相位为 $1$，则被操纵后的弹幕的相位要**大于**这个阈值，否则被操纵后的弹幕的相位要**小于**这个阈值。\n\n显然的是，根据铃仙的操纵规则，无论原本的弹幕的相位如何，都是存在可能的操纵方案的。由于主角们失去了记忆，而找回月亮的时间已经所剩不多了，而且弹幕战对时间的把控要求极高。她们找到了你，希望你能够对铃仙原本的弹幕相位，给出**任意一种**操作后的弹幕相位，来为她们的闪避弹幕进行准备。\n\n## Input\n\n**本题有多组数据。**\n\n第一行一个整数 $T$，表示数据组数。\n\n对于每组数据：\n\n- 第一行一个整数 $n$，意义如题述。\n- 第二行一个长度为 $n$ 的 01 串 $b$。\n\n## Output\n\n对于每组数据，输出一行 $n$ 个整数，即你构造的数列 $a$。\n\n**如果有多组解，输出任意一种。**\n\n[samples]\n\n## Background\n\n**Problem Number:** $\\textit{39}$\n\n**背景与题目无关，选手可以直接看下面的「简要题意」。**\n\n那是在竹取物语之后的故事了，幻想乡距离与现实隔绝也已经过去了百年时光。\n\n地上人向月球发起了侵略战争之后，一只名叫**铃仙**的月兔舍弃了同伴，死里逃生，逃到了在幻想乡内的永远亭，来到了辉夜与永琳的身边，生活得安稳而舒适。\n\n又过了数十年，铃仙接收到了来自月球的使唤，被要求强制返回月球。辉夜与永琳商量了下，决定不将铃仙交还予月球。但为了避免造成麻烦，辉夜与永琳决定将满月消失在地上，只留下一轮虚假的月亮。\n\n-----\n\n为了方便调查异变，八云紫运用自己的能力，将整个幻想乡变成了永夜。\n\n被穿梭回异变发生当时的四组主角，共八人。除了依然留有记忆，可以来回穿梭在虚与实的境界的八云紫之外，其他的人缺乏了记忆，重新开始踏上夺回幻想乡的满月的征途。\n\n在慧音的指引之下，她们来到了迷途竹林，在她们的面前，是一只名叫铃仙的月兔。\n\n## Note\n\n### 样例解释\n\n- 对于数据 $1$，显然 $a_2>1,a_3>2$。\n- 对于数据 $2$，显然 $a_2<2,a_3>2$。\n- 对于数据 $3$，显然 $a_2>1,a_3<3,a_4>3$。\\\n  注意到 $a=\\{2,3,1,4\\}$ 同样满足要求。\n\n### 数据范围\n\n$$\n\\def\\arraystretch{1.5}\n\\begin{array}{|c|c|c|c|c|}\\hline\n\\textbf{Subtask} & \\bm{n\\le} & \\textbf{特殊性质} & \\textbf{Subtask 依赖} & \\textbf{分值}\\\\\\hline\n1 & 10 & - & - & 5\\\\\\hline\n2 & 10^5 & \\textbf{A} & - & 5 \\\\\\hline\n3 & 10^5 & \\textbf{B} & - & 20 \\\\\\hline\n4 & 10^5 & - & 1,2,3 &70 \\\\\\hline\n\\end{array}$$\n\n- **特殊性质** $\\textbf{A}$：保证 $b_i$ 都相等。\n- **特殊性质** $\\textbf{B}$：存在整数 $p\\in[2,n]$，使得对于 $1\\le i<p$，有 $b_i=1$；对于 $n\\ge i\\ge p$，有 $b_i=0$。\n\n对于全部数据，满足 $1\\le T\\le 10^4$，$1\\le n\\le 10^5$，$\\forall i\\in[1,n],b_i\\in\\{0,1\\}$。\n\n保证单个测试点内 $\\sum n\\le 5\\times 10^5$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8536","tags":["洛谷原创","Special Judge","O2优化","构造","洛谷月赛"],"sample_group":[["3\n3\n111\n3\n101\n4\n0101","1 2 3\n2 1 3\n1 3 2 4"]],"created_at":"2026-03-03 11:09:25"}}