QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#679465 | #8058. Binary vs Ternary | ShiinaMahiru# | RE | 0ms | 3544kb | C++17 | 2.8kb | 2024-10-26 17:40:16 | 2024-10-26 17:40:17 |
Judging History
answer
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
using i64 = long long;
using ll = long long;
using namespace std;
constexpr int N = 2e6 + 10;
string a,b;
vector<pair<int,int>>res;
void fun11to10(int l,int r)
{
res.pb({l,r});
res.pb({l+1,l+2});
string s=a.substr(0,l+1);
string t;
if(r+1<a.size())t=a.substr(r+1,a.size());
a=s+'0'+t;
}
void fun10to11(int l,int r)
{
res.pb({l,r});
string s=a.substr(0,l+1);
string t;
if(r+1<a.size())t=a.substr(r+1,a.size());
a=s+'1'+t;
}
void fun11to111(int l,int r)
{
res.pb({l,r});
res.pb({l,l+1});
res.pb({l+1,l+2});
string s=a.substr(0,r);
string t=a.substr(r,a.size());
a=s+'1'+t;
}
void fun01to1(int l,int r)
{
res.pb({l,r});
string s=a.substr(0,l);
string t=a.substr(r,a.size());
a=s+t;
}
void fun00to0(int l,int r)
{
res.pb({l,r});
string s=a.substr(0,l);
string t;
if(r+1<a.size())t=a.substr(r+1,a.size());
a=s+'0'+t;
}
string A, B;
void check() {
for (auto [l, r] : res) {
string s = A.substr(l, r - l + 1);
int val = 0;
for (auto c : s) {
val = val * 3 + (c - '0');
}
s.clear();
if (val == 0) {
s.push_back('0');
} else
while (val) {
s.push_back(val % 2 + '0');
val /= 2;
}
reverse(s.begin(), s.end());
A = A.substr(0, l) + s + (r + 1 <= A.size() - 1 ? A.substr(r + 1) : "");
}
assert(A == B);
}
void solve(){
cin>>a>>b;
a=" "+a;
b=" "+b;
A = a, B = b;
//00 -0
res.clear();
if(a.size()==2)
{
if(b.size()!=2||b[1]!=a[1])cout<<-1<<endl;
else
{
cout<<0<<endl;
}
return ;
}
if(b.size()==2)
{
cout<<-1<<endl;
return ;
}
for(int i=1;i+1<a.size();i++)
{
if(a[i]=='1'&&a[i+1]=='0')
{
fun10to11(i,i+1);
}
}
//cout<<a<<endl;
for(int i=a.size()-2;i>=1;i--)
{
fun11to10(i,i+1);
}
//cout<<a<<endl;
fun00to0(2,a.size()-1);
//cout<<a<<endl;
fun10to11(1,2);
//cout<<a<<endl;
while(a.size()<b.size())
{
fun11to111(1,2);
}
//cout<<a<<endl;
for(int i=a.size()-2;i>=1;i--)
{
if(a[i]=='1'&&a[i+1]=='1'&&b[i]=='1'&&b[i+1]=='0')
{
fun11to10(i,i+1);
}
}
cout<<res.size()<<endl;
for(auto [l,r]:res)
{
cout<<l<<" "<<r<<endl;
}
check();
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3544kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 35 2 3 5 6 5 6 6 7 4 5 5 6 3 4 4 5 2 3 3 4 1 2 2 3 2 6 1 2 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 6 7 7 8 4 5 5 6 2 3 3 4 20 3 4 4 5 2 3 3 4 1 2 2 3 2 4 1 2 1 2 1 2 2 3 1 2 1 2 2 3 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 ...