QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #709984 | #8058. Binary vs Ternary | frankly6 | RE | 0ms | 3548kb | C++17 | 2.2kb | 2024-11-04 17:46:17 | 2024-11-04 17:46:18 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef pair<int,int> PII;
const int MX=1010;
int T, cnt;
PII op[MX];
int read()
{
int r=0, f=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {r=r*10+ch-'0'; ch=getchar();}
return r*f;
}
int main()
{
// freopen("testdata.in","r",stdin);
T=read();
while(T--)
{
string s1, s2;
// s1 -> 1111 -> s2
cin >> s1;
cin >> s2;
int N=s1.size(); s1=" "+s1;
int M=s2.size(); s2=" "+s2;
// cout << "N=" << N << ", M=" << M << '\n';
if(N==1&&s1[1]=='1'&&M==1&&s2[1]=='1') {cout << "0\n"; continue;}
if((N==1&&s1[1]=='1')||(M==1&&s2[1]=='1')) {cout << "-1\n"; continue;}
cnt=0;
for(int i=1;i<N;i++) // s1 -> 11111
{
// if(s1[i]=='1'&&s1[i+1]=='1') continue;
if(s1[i]=='1'&&s1[i+1]=='0')
{
op[++cnt]={i,i+1};
s1[i+1]='1';
}
}
// cout << "1...1\n";
for(int i=N-2;i>=1;i--)
op[++cnt]={i,i+1};
op[++cnt]={2,N+N-2};
// cout << "shrink done\n";
// cout << "M=" << M << '\n';
for(int i=1,r=2;;)
{
op[++cnt]={i,r};
op[++cnt]={i,r};
r++; i++;
op[++cnt]={i,r};
if(r==M) break;
}
// cout << "extend done\n";
s1=" ";
for(int i=1;i<=M;i++) s1+='1';
for(int i=M;i>=1;i--)
{
if(s1[i]==s2[i]) continue;
else
{
if(s1[i]=='1'&&s2[i]=='0')
{
op[++cnt]={i-1,i};
op[++cnt]={i,i+1};
s1[i]='0';
}
else if(s1[i]=='0'&&s2[i]=='1')
{
op[++cnt]={i-1,i};
s1[i]='1';
}
}
}
cout << cnt << '\n';
for(int i=1;i<=cnt;i++)
{
auto [l,r]=op[i];
cout << l << " " << r << '\n';
}
}
return (0-0);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3548kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 28 2 3 5 6 4 5 3 4 2 3 1 2 2 10 1 2 1 2 2 3 2 3 2 3 3 4 3 4 3 4 4 5 4 5 4 5 5 6 5 6 5 6 6 7 6 7 7 8 4 5 5 6 2 3 3 4 15 2 3 1 2 2 6 1 2 1 2 2 3 2 3 2 3 3 4 3 4 3 4 4 5 4 5 4 5 5 6
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:
9 3 4 4 5 3 4 2 3 1 2 2 8 1 2 1 2 2 3 -1