QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#679465#8058. Binary vs TernaryShiinaMahiru#RE 0ms3544kbC++172.8kb2024-10-26 17:40:162024-10-26 17:40:17

Judging History

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

  • [2024-10-26 17:40:17]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3544kb
  • [2024-10-26 17:40:16]
  • 提交

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
...

output:


result: