QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #719025 | #8058. Binary vs Ternary | FHQY# | WA | 1ms | 3760kb | C++20 | 2.3kb | 2024-11-06 22:05:34 | 2024-11-06 22:05:38 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int M=1e6+9,inf=1e9;
vector<pair<int,int> > ans;
string ppa;
string sb(string x,int l,int r)
{
string now;
for(int i=l;i<=r;i++)
now+=x[i];
return now;
}
string get(string x)
{
for(auto [l,r] : ans)
{
assert(l>=0&&l<x.size());
assert(r>=0&&r<x.size());
int num=0;
for(int i=l;i<=r;i++)
num*=3,num+=(x[i]-'0');
string th;
while(num)
{
char c=num%2+'0';
th+=c;
num/=2;
}
reverse(th.begin(),th.end());
x=sb(x,0,l-1)+th+sb(x,r+1,x.size()-1);
}
return x;
}
void pri()
{
cout<<ans.size()<<endl;
for(auto [l,r] : ans)
cout<<l+1<<" "<<r+1<<endl;
// cout<<get(ppa)<<endl;
return;
}
void solve()
{
ans.clear();
string a,b;
cin>>a>>b;
ppa=a;
if(b.size()==1||a.size()==1)
{
if(a!=b)
cout<<-1<<endl;
else
cout<<0<<endl;
return;
}
for(int i=0;i<a.size();i++)
{
if(a[i]=='0')
{
ans.push_back({i-1,i});
a[i]='1';
}
}
int cnt=0;
for(auto now : b)
{
if(now=='1')
cnt++;
}
if(cnt==1)
{
int pcnt=a.size();
pcnt-=2;
a="11";
for(int i=1;i<=pcnt;i++)
{
ans.push_back({0,1});
ans.push_back({1,3});
}
ans.push_back({0,1});
ans.push_back({1,2});
a="10";
pcnt=b.size();
pcnt-=2;
for(int i=1;i<=pcnt;i++)
{
ans.push_back({0,1});
ans.push_back({0,1});
}
pri();
return;
}
int pcnt=a.size();
if(pcnt>=cnt)
{
pcnt-=cnt;
for(int i=1;i<=pcnt;i++)
{
ans.push_back({0,1});
ans.push_back({1,3});
}
}
else
{
pcnt=cnt-pcnt;
for(int i=1;i<=pcnt;i++)
{
ans.push_back({0,1});
ans.push_back({0,1});
ans.push_back({1,2});
}
}
// cout<<get(ppa)<<endl;
vector<int> pnum(100,0);
int tcnt=0,tot=0;
for(int i=b.size()-1;i>=0;i--)
{
if(b[i]=='1')
{
pnum[++tot]=tcnt;
tcnt=0;
}
else
tcnt++;
}
for(int i=1;i<=pnum[1];i++)
{
int pos=cnt-i-1;
ans.push_back({pos,pos+1});
ans.push_back({pos,pos+1});
}
for(int i=2;i<=cnt;i++)
{
int pos=cnt-i;
for(int j=1;j<=pnum[i];j++)
{
ans.push_back({pos,pos+1});
ans.push_back({pos,pos+2});
ans.push_back({pos+2,pos+3});
}
}
pri();
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
cin>>T;
while(T--)
solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 14 2 3 5 6 1 2 2 4 1 2 2 4 3 4 3 4 3 4 3 5 5 6 2 3 2 4 4 5 6 1 2 1 2 2 3 1 2 1 2 2 3
result:
ok Haitang Suki (3 test cases)
Test #2:
score: -100
Wrong Answer
time: 1ms
memory: 3564kb
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 11 1 2 2 3 3 4 1 2 2 4 1 2 2 4 1 2 2 4 1 2 2 3 1 1 2 6 1 2 1 2 1 2 2 3 2 3 2 3 6 2 3 3 4 1 2 2 4 1 2 2 4 8 2 3 4 5 1 2 2 4 1 2 2 4 1 2 2 4 3 2 3 1 2 2 4 -1 10 1 2 4 5 1 2 2 4 1 2 2 4 1 2 2 4 1 2 2 3 10 1 2 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 16 1 2 2 3 3 4 4 5 1 2 2 4 1 ...
result:
wrong answer S!=T after all operations (test case 12)