不知道有没有别的思考方法。

注意到评分规则里有一个是 $S(p) \le 1$ 即可获得 $100\%$ 的分数，于是考虑从这里入手。

考虑二分查找的过程，相当于不停得寻找中点，然后把序列劈成两个部分。

所以无论怎么样，中点会被优先遍历到，而形成一个类似完全二叉树 bfs 的结构。 于是我们先把 $b_i=1$ 的点从小到大排序，分别放入这些中点。

然后考虑 $b_i = 0$ 的点，对于一个区间：如果一个数比中点小，但是在中点右边，那显然不合法。反之类似。

然后我们发现每个数的价值是一样的，所以直接贪心即可。

从大到小地将 $b_i=0$ 的点放入剩下没有被填充的位置。这样也恰好保证了最多就只有一个位置会违背 $b_i$ 的约束（最中间的那个点）。

于是做完了，时间复杂度 $O(n \log n)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define FILE(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
#define ll long long
const int N=2e5+5;
string s;
int n,a[N];
vector<int>g,g2;
inline void get(int l,int r,int ql,int qr){
	if(ql>qr||l>r) return;
	if(l==r) return a[l]=g[(ql+qr)>>1],void();
	int mid=(l+r)>>1,mid2=(ql+qr)>>1; a[mid]=g[mid2];
	get(l,mid-1,ql,mid2-1); get(mid+1,r,mid2+1,qr);
}
inline void solve(){
	cin>>n>>s; s=' '+s;
	g.clear(); g2.clear(); memset(a,0,sizeof(a));
	for(int i=1;i<=n;i++) {
		if(s[i]=='1') g.emplace_back(i);
		else g2.emplace_back(i);
	}
	get(1,n,0,(int)g.size()-1);
	for(int i=1;i<=n;i++) {
		if(a[i]) continue;
		a[i]=g2.back(); g2.pop_back();
	}
	for(int i=1;i<=n;i++) cout<<a[i]<<( i==n ? '\n' : ' ');
}
signed main(){
	cin.tie(nullptr)->sync_with_stdio(false);
	int T;cin>>T;
	while(T--) solve();
	return 0;
}