莫名 #29 MLE。

大佬能帮一下这个可怜的蒟蒻吗/ll/kel

#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int dp[1000005][65],n,T;
inline void solve(){
	scanf("%s",s);
	n=strlen(s);
	int sum=0;
	for(int i=0;i<n;i++){
		sum+=(int)(s[i]-'0');
	}
	if(sum==0){
		cout<<-1<<endl;
		return;
	}
	if((sum&(sum-1))==0){
		cout<<n<<endl;
		for(int i=1;i<=n;i++){
			cout<<i<<" "<<i<<endl;
		}
		return;
	}
	vector<pair<int,int>>vctr;
	int l=0;
	while(l<n) {
		if(s[l]=='0'){
			l++;
			continue;
		}
		int r=l;
		while(r<n&&s[r]=='1'){
			r++;
		}
		vctr.push_back(make_pair(l,r));
		l=r;
	}
	int k=vctr.size();
	if(k==1){
		vector<pair<int,int>>ans;
		if(s[0]=='0'){
			ans.push_back(make_pair(0, vctr[0].first));
		}
		ans.push_back(make_pair(vctr[0].first,vctr[0].first+1));
		ans.push_back(make_pair(vctr[0].first+1,vctr[0].second));
		if (s[n-1]=='0'){
			ans.push_back(make_pair(vctr[0].second,n));
		}
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++){
			cout<<ans[i].first+1<<" "<<ans[i].second<<endl;
		}
		return;
	}
	if(k==2&&(vctr[0].second-vctr[0].first==1||vctr[1].second-vctr[1].first==1)){
		vector<pair<int,int>>ans;
		if(s[0]=='0'){
			ans.push_back(make_pair(0,vctr[0].first));
		}
		ans.push_back(vctr[0]);
		ans.push_back(make_pair(vctr[0].second,vctr[1].first));
		ans.push_back(vctr[1]);
		if(s[n-1]=='0'){
			ans.push_back(make_pair(vctr[1].second,n));
		}
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++){
			cout<<ans[i].first+1<<" "<<ans[i].second<<endl;
		}
		return;
	}
	if(sum<32){
		memset(dp,-1,sizeof(dp));
		dp[0][0]=0;
		for(int l=0;l<n;l++){
			if(s[l]=='0'){
				for(int x=0;x<65;x++){
					if(dp[l][x]!=-1){
						dp[l+1][x]=1;
					}
				}
				continue;
			}
			int cur=0;
			for(int r=l;r<n;r++){
				cur*=2;
				if(s[r]=='1'){
					cur++;
				}
				if(cur>=65){
					break;
				}
				for(int x=0;x+cur<65;x++){
					if(dp[l][x]!=-1){
						dp[r+1][x+cur]=r-l+1;
					}
				}
			}
		}
		long long sum=1;
		while(sum<=65&&dp[n][sum]==-1){
			sum*=2;
		}
		if(sum>=65){
			cout<<-1<<endl;
			return;
		}
		vector<pair<int,int>>ans;
		int p=n;
		while(p>0){
			int x=dp[p][sum];
			ans.push_back(make_pair(p-x,p));
			p-=x;
			int y=0;
			for(int i=p;i<p+x;i++){
				y*=2;
				if(s[i]=='1'){
					y++;
				}
			}
			sum-=y;
		}
		reverse(ans.begin(),ans.end());
		assert(sum==0);
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++){
			pair<int,int> t=ans[i];
			cout<<t.first+1<<" "<<t.second<<endl;
		}
		return;
	}
	int t=0;
	while(sum>(1<<t)){
		t++;
	}
	sum=(1<<t)-sum;
	vector<pair<int,int>>ans;
	l=0;
	while(l<n){
		if(sum==0||s[l]=='0'){
			ans.push_back(make_pair(l,l+1));
			l++;
			continue;
		}
		int cur=1;
		int cnt=1;
		int r=l+1;
		while(r<n&&2*cur-cnt<=sum){
			cur*=2;
			if(s[r]=='1'){
				cur++;
				cnt++;
			}
			r++;
		}
		sum-=cur-cnt;
		ans.push_back(make_pair(l,r));
		l=r;
	}
	assert(sum==0);
	cout<<ans.size()<<endl;
	for(int i=0;i<ans.size();i++){
		cout<<ans[i].first+1<<" "<<ans[i].second<<endl;
	}
	return;
}
signed main(){
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}