题目描述
众所周知,当上述函数在传入一个单调不递减的数组 p 且 target 在数组 p 中出现过,那么会返回 true。然而,当 p 不存在单调性时则不然。
给定正整数 n 和一个数组 b1,…,bn∈{true,false}。数据保证存在一个正整数 k,使得 n=2k−1。
规定 S(p) 为 i∈{1,…,n} 时 binary_search(n, p, i) 返回值不为 bi 的个数。你的任务是求一个 {1,…,n} 的排列 p,使得 S(p) 尽可能小(具体请见评分规则)。
输入格式
本题有多组数据。
第一行一个正整数 T,表示数据组数。
每组数据的第一行包含一个正整数 n。第二行包含一个长度为 n 的字符串(只含有字符 0
和 1
且无空格)。其中当第 i 个字符为 1
时,则 bi=true,否则 bi=false。
输出格式
输出 T 行,每行输出求得的排列 p。Special Judge 对输出格式要求非常严格,每行行末不能有空格等多余字符。
提示
评分规则
- 当一个子任务中的所有排列 p 均满足 S(p)≤1 时,得分为该子任务总分的 100%。
- 否则当一个子任务中的所有排列 p 均满足 0≤S(p)≤⌈log2n⌉ 时,得分为该子任务总分的 50%。
由于洛谷评分机制,每个测试点的实际得分为上式下取整的结果。例如,当该子任务的总分为 3 且该子任务中的所有排列 p 均满足 0≤S(p)≤⌈log2n⌉ 时,得分为 1 而不是 1.5。
样例 1 解释
前两组数据满足 S(p)=0。
第三组数据中 S(p)=1,因为 binary_search(n, p, 2)=true=b2。
第四组数据中 S(p)=1,因为 binary_search(n, p, 4)=true=b4。
样例 2 解释
两组数据均满足 S(p)=0。
数据规模与约定
本题采用捆绑测试。
- Subtask 1(3 pts):bi=true。
- Subtask 2(4 pts):bi=false。
- Subtask 3(16 pts):1≤n≤7。
- Subtask 4(25 pts):1≤n≤15。
- Subtask 5(22 pts):n=216−1 且 bi 数据随机。
- Subtask 6(30 pts):无特殊限制。
对于 100% 的数据,1≤T≤7000,1≤∑n≤105,∀n∈{n∣n=2k−1,k∈N∗}。
说明
本题译自 eJOI2021 Day 2 A BinSearch。欢迎通过私信或发帖的方式对自行编写的 Special Judge 进行 hack。