QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#330548#8058. Binary vs Ternaryucup-team1303#RE 1ms3684kbC++142.6kb2024-02-17 16:49:112024-02-17 16:49:11

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 16:49:11]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3684kb
  • [2024-02-17 16:49:11]
  • 提交

answer

#include<bits/stdc++.h>

#define ll long long
#define mk make_pair
#define fi first
#define se second

using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;(c<'0'||c>'9');c=getchar()){if(c=='-')f=-1;}
	for(;(c>='0'&&c<='9');c=getchar())x=x*10+(c&15);
	return x*f;
}

const int mod=998244353;
int ksm(int x,int y,int p=mod){
	int ans=1;
	for(int i=y;i;i>>=1,x=1ll*x*x%p)if(i&1)ans=1ll*ans*x%p;
	return ans%p;
}
int inv(int x,int p=mod){return ksm(x,p-2,p)%p;}
mt19937 rnd(time(0));
int randint(int l,int r){return rnd()%(r-l+1)+l;}
void add(int &x,int v){x+=v;if(x>=mod)x-=mod;}
void Mod(int &x){if(x>=mod)x-=mod;}
int cmod(int x){if(x>=mod)x-=mod;return x;}

void cmax(int &x,int v){x=max(x,v);}
void cmin(int &x,int v){x=min(x,v);}

string A,B;
void solve(){
	cin>>A>>B;
	if(A.size()==1||B.size()==1){
		if(A==B)puts("0");
		else puts("-1");
		return ;
	}
	vector<pair<int,int> >ans;
	auto mov=[&](int l,int r){
		// cout<<"A = "<<A<<" mov "<<l<<" "<<r<<endl;
		assert(0<=l&&l<=r&&r<A.size());
		ans.emplace_back(mk(l+1,r+1));
		if(r==l+1&&A[l]=='1'&&A[r]=='0')A[r]='1';
		else if(r==l+1&&A[l]=='1'&&A[r]=='1'){
			string L;
			for(int i=0;i<l;i++)L+=A[i];
			L+="100";
			for(int i=r+1;i<A.size();i++)L+=A[i];
			A=L;
		}
		else{
			bool chk=1;
			for(int i=l;i<r;i++)chk&=(A[i]=='0');
			// chk&=(A[r]=='1');
			assert(chk);
			string L;
			for(int i=0;i<l;i++)L+=A[i];
			for(int i=r;i<A.size();i++)L+=A[i];
			A=L;
		}
		// cout<<" -> A = "<<A<<endl;
	};
	for(int i=1;i<A.size();i++){
		if(A[i]=='1')continue;
		mov(i-1,i);
	}
	int cnt=0;
	for(int i=0;i<B.size();i++){
		cnt+=(B[i]=='1');
		if(B[i]=='1'&&B[i+1]=='0')cnt++;
	}
	while(A.size()>=cnt){
		mov(0,1);
		assert(A.size()>=4);
		mov(1,3);
	}
	while(A.size()<cnt){
		mov(0,1),mov(0,1),mov(1,2);
	}
	int p=0;
	for(int i=0;i<B.size();i++){
		if(B[i]=='1'){
			int cc=0;
			for(int j=i+1;j<B.size();j++){
				if(B[j]=='1')break;
				cc++;
			}
			if(cc==0){p++;continue;}
			else if(cc==1){
				mov(p,p+1);
				assert(A[p]=='1'&&A[p+1]=='0'&&A[p+2]=='0');
				mov(p+1,p+2);
			}
			else{
				for(int _=1;_<=cc-2;_++){
					mov(p,p+1);
					assert(A[p]=='1'&&A[p+1]=='0'&&A[p+2]=='0');
					mov(p,p+1);
					assert(A[p+1]=='1');
				}
				mov(p,p+1);
				assert(A[p]=='1'&&A[p+1]=='0'&&A[p+2]=='0');
			}
			p++;
			while(p<A.size()&&A[p]=='0')p++;
		}
	}

	cout<<ans.size()<<endl;
	for(auto [l,r]:ans)cout<<l<<" "<<r<<endl;
}

signed main(void){

#ifndef ONLINE_JUDGE
	freopen("in.in","r",stdin);
#endif

	int tt=0;cin>>tt;
	while(tt--)solve();

	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3684kb

input:

3
1
111
110110
1101010
1111
111111

output:

-1
11
2 3
5 6
1 2
1 2
2 3
2 3
3 4
4 5
5 6
6 7
7 8
6
1 2
1 2
2 3
1 2
1 2
2 3

result:

ok Haitang Suki (3 test cases)

Test #2:

score: -100
Runtime Error

input:

1000
11100
111
1
11110
10001
10
1011
1111
10
1110
1100
11
11010
11
110
11
1
10001
10110
10
10
11111
10000
1001
10
1
11
10111
11
10
1
100
11
10100
1
10
101
11
1100
110
11
1110
1
1001
1
11111
10
10010
10
11001
110
1010
10011
1110
10100
1001
1001
101
100
1
1001
11
101
11
101
1001
1
1
1011
1
10
10
1011
...

output:

11
3 4
4 5
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
2 3
-1

result: