QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #637401 | #8058. Binary vs Ternary | Tolret | WA | 1ms | 3636kb | C++20 | 3.2kb | 2024-10-13 12:38:19 | 2024-10-13 12:38:19 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long int
#define ull unsigned long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
const int maxn=1e6+5;
const int inf=1e18;
string a,b;
char sa[maxn],sb[maxn];
char tmp[maxn];
int lena,lenb;
void solve()
{
cin>>a>>b;
if(a==b)
{
cout<<0<<'\n';
return;
}
bool f1=true,f2=true;
for(auto j:a)
{
if(j=='1')
{
f1=false;
}
}
for(auto j:b)
{
if(j=='1')
{
f2=false;
}
}
if((f1!=f2)||(f1&&f2))
{
cout<<-1<<'\n';return;
}
lena=a.size();lenb=b.size();
for(int i=1;i<=lena;i++)
sa[i]=a[i-1];
for(int i=1;i<=lenb;i++)
sb[i]=b[i-1];
vector<pii>ans;
int pos=0;
for(int i=1;i<=lenb;i++)
{
if(sb[i]=='1')
{
pos=i-1;break;
}
}
if(pos>=lena)
{
cout<<-1<<'\n';return;
}
for(int i=1;i<=pos;i++)
{
if(sa[i]=='1')
{
cout<<-1<<'\n';return;
}
}
int pos2=pos;
for(int i=pos+1;i<=lena;i++)
{
if(sa[i]=='1')
{
pos2=i-1;break;
}
}
if(pos2>=pos+1)
{
ans.pb({pos+1,pos2});
int len=pos2-pos;
for(int i=pos+1;i+len<=lena;i++)
{
sa[i]=sa[i+len];
}
lena-=len;
}
// for(int i=1;i<=lena;i++)
// {
// cout<<sa[i];
// }
// cout<<'\n';
// for(int i=1;i<=lenb;i++)
// {
// cout<<sb[i];
// }
// cout<<'\n';
// cout<<pos<<'\n';
for(int i=pos+1;i<lena;i++)
{
if(sa[i]=='1'&&sa[i+1]=='0')
{
sa[i+1]='1';
ans.pb({i,i+1});
}
}
if(lena!=lenb&&lena==1)
{
cout<<-1<<'\n';return;
}
while(lena<lenb)
{
ans.pb({lena-1,lena});
ans.pb({lena-1,lena});lena++;
ans.pb({lena-1,lena});sa[lena]='1';
}
vector<int>tmpa,tmpb;
for(int i=pos+1;i<=lena;i++)
tmpa.pb(sa[i]-'0');
for(int i=pos+1;i<=lenb;i++)
tmpb.pb(sb[i]-'0');
// for(auto j:tmpa)cout<<j;
// cout<<'\n';
// for(auto j:tmpb)cout<<j;
// cout<<'\n';
while(!tmpb.empty())
{
if(tmpb.back()==tmpa.back())
{
tmpa.pop_back();tmpb.pop_back();continue;
}
else if(tmpa.size()<=1)
{
cout<<-1<<'\n';return;
}
if(tmpb.back()==0)
{
ans.pb({pos+(int)tmpa.size()-1,pos+(int)tmpa.size()});
tmpa.pop_back();
tmpa.pb(0);
tmpb.pop_back();
}
else if(tmpb.back()==1)
{
ans.pb({pos+(int)tmpa.size()-1,pos+(int)tmpa.size()});
tmpa.pop_back();
tmpb.pop_back();
}
}
while(!tmpa.empty())
{
if(tmpa.back()==0)
{
ans.pb({pos+(int)tmpa.size(),pos+(int)tmpa.size()+1});
tmpa.pop_back();
continue;
}
if(tmpa.size()>=2)
{
ans.pb({pos+(int)tmpa.size()-1,pos+(int)tmpa.size()});
ans.pb({pos+(int)tmpa.size(),pos+(int)tmpa.size()+2});
tmpa.pop_back();
}
else
{
ans.pb({pos+(int)tmpa.size(),pos+(int)tmpa.size()+1});
if(lenb>2)
ans.pb({pos+(int)tmpa.size()+1,pos+(int)tmpa.size()+3});//?
else
ans.pb({pos+(int)tmpa.size()+1,pos+(int)tmpa.size()+2});
tmpa.pop_back();
}
}
cout<<ans.size()<<'\n';
for(auto j:ans)
{
cout<<j.fi<<' '<<j.se<<'\n';
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cout<<fixed<<setprecision(10);
int T=1;
cin>>T;
for(int i=1;i<=T;i++)
solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3636kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 17 2 3 5 6 5 6 5 6 6 7 6 7 6 7 5 6 5 6 4 5 4 5 2 3 3 5 1 2 2 4 1 2 2 4 6 3 4 3 4 4 5 4 5 4 5 5 6
result:
ok Haitang Suki (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3580kb
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:
6 3 4 4 5 1 2 2 4 1 2 2 4 -1 13 1 2 2 3 3 4 4 5 4 5 3 4 4 6 2 3 3 5 1 2 2 4 1 2 2 3 1 1 2 11 1 2 1 2 1 2 2 3 2 3 2 3 3 4 3 4 3 4 1 2 2 4 6 2 3 3 4 1 2 2 4 1 2 2 3 8 2 3 4 5 2 3 3 5 1 2 2 4 1 2 2 3 3 2 3 1 2 2 3 -1 12 1 2 4 5 4 5 4 5 3 4 4 6 2 3 3 5 1 2 2 4 1 2 2 3 10 1 2 1 2 1 2 2 3 2 3 2 3 3 4 3 4 ...
result:
wrong answer S!=T after all operations (test case 3)