START203——MEX on Ranges · znzryb

## 思路讲解

其他都想到了，就是这个

**reverse(all(wp));**

需要hack数据才能想到。

其实1 1 之间不会相互影响，但是0 0之间会，把最重要的放在最远，避免互相影响。

```cpp
	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}
```

## AC代码

[https://www.codechef.com/viewsolution/1189976308](https://www.codechef.com/viewsolution/1189976308)



::: 源代码

```cpp
// by Gospel_rock
#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define PB push_back
#define PF push_front
#define EB emplace_back
#define EF emplace_front
#define EM emplace
#define FI first
#define SE second
#define pct __builtin_popcountll
#define ctz __builtin_ctzll
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)
#define minn(vec) *min_element(vec.begin(),vec.end())
#define maxx(vec) *max_element(vec.begin(),vec.end())

using namespace std;
#ifdef LOCAL
template<typename T> void _print(T x) {
	cerr << x;
}
// 可以打印多层数组，但是格式不是很好
template<typename T> void _print(vector<T> v) {
	cerr << "[ ";
	for (T i : v) _print(i), cerr << " ";
	cerr << "]";
}
template<typename T> void _print(set<T> s) {
	cerr << "{ ";
	for (T i : s) _print(i), cerr << " ";
	cerr << "}";
}
template<typename T, typename U> void _print(pair<T, U> p) {
	cerr << "{";
	_print(p.first);
	cerr << ", ";
	_print(p.second);
	cerr << "}";
}
template<typename T, typename U> void _print(map<T, U> m) {
	cerr << "{ ";
	for (auto &p : m) _print(p), cerr << " ";
	cerr << "}";
}
// 打印两层数组，格式好一些
template<typename T> void _print(vector<vector<T >> v) {
	cerr << "{\n"; for (auto i : v) _print(i), cerr << "\n"; cerr << " }";
}
#endif

using  ll = long long;using ull = unsigned long long;
using DB=double;using LD=long double;
// using i128 = __int128;
using pdd = pair<DB,DB>;using plb = pair<ll,bool>;
using pll = pair<ll,ll>;using vll=vector<ll>;using vb=vector<bool>;
using tll = tuple<ll,ll,ll>;using vii=vector<int>;
using vpll = vector<pll>;using vtll = vector<tll>;
using vdb = vector<DB>;using vc=vector<char>;
using arr3 = array<ll,3> ;using arr2 = array<ll,2>;
using CD=complex<double>;
static constexpr ll MAXN=(ll)1e6+10,INF=(ll)1e17+3; // 1e17+3是素数 1e18+9是素数
static constexpr ll mod=(ll)1e9+7; // 998244353;
static constexpr double eps=1e-8;const double pi=acos(-1.0);
ll N,M,Q,X,K,T,lT;

inline void __();
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin>>lT;
	while(lT--)
		__();
	return 0;
}
/*

*/
inline void __(){
	cin>>N;
	string s;
	cin>>s;
//	vll A(N+5);
	deque<ll> A;
	vll wp;
	FOR(i,1,N){
//		if(s[i]=='1') A[i]=i-1;
//		else A[i]=N;
		ll t=N;
		if(s[i]=='1'){
			t=i-1;
			A.PB(t);
			reverse(all(wp));
			for(auto w:wp){
				A.PB(w);
			}
			wp.clear();
		}else{
			t=i-1;
			wp.PB(t);
		}
	}
	FOR(i,0,SZ(wp)-1){
		A.PB(N);
	}
	for(auto a:A){
		cout<<a<<" ";
	}
	cout<<"\n";
}
/*
AC
https://www.codechef.com/viewsolution/1189976308

1
4
11001

既然考虑到了 1 1 的情况，也要考虑0 0 的情况

//		if(i&1){
//			A.PB(t);
//		}else{
//			A.PF(t);
//		}


//	vb suf(N+5);
//	ROF(i,N,0){
//		if(s[i]=='1'){
//			suf[i]=true;
//			continue;
//		}
//		suf[i]=suf[i+1];
//	}
//	FOR(i,1,N){
//		if(s[i]=='1') continue;
//		if(suf[i]){
//			A.PB(i-1);
//		}else{
//			A.PB(N);
//		}
//	}


*/
```


:::


## 心路历程（WA，TLE，MLE……）