QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#740679 | #8058. Binary vs Ternary | dezex# | WA | 3ms | 3724kb | C++20 | 1.8kb | 2024-11-13 11:05:08 | 2024-11-13 11:05:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 70;
int a[N], b[N];
int la, lb;
vector<pair<int, int>> ans;
void init();
bool solve();
void zero_to_one(int pos);
void one_to_zero(int pos);
void add_len(int len);
void dec_len(int len);
int main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
init();
if (!solve())
{
cout << -1 << endl;
continue;
}
cout << ans.size() << endl;
for (auto p : ans)
cout << p.first << " " << p.second << endl;
}
return 0;
}
void init()
{
string sa, sb;
cin >> sa >> sb;
la = sa.size(), lb = sb.size();
for (int i = 0; i < la; i++)
a[i + 1] = sa[i] - '0';
for (int i = 0; i < lb; i++)
b[i + 1] = sb[i] - '0';
ans.clear();
}
bool solve()
{
if (la == 1 && lb == 1 && a[1] == b[1])
return true;
if (la == 1 || lb == 1)
return false;
for (int i = 1; i <= la; i++)
if (a[i] == 0)
zero_to_one(i);
while (la < lb)
{
add_len(la);
la++;
}
while (la > lb)
{
dec_len(la);
la--;
}
for (int i = 1; i <= la; i++)
if (b[i] == 0)
one_to_zero(i);
return true;
}
void zero_to_one(int pos)
{
ans.push_back(make_pair(pos - 1, pos));
a[pos] = 1;
}
void one_to_zero(int pos)
{
ans.push_back(make_pair(pos - 1, pos));
ans.push_back(make_pair(pos, pos + 1));
a[pos] = 0;
}
void add_len(int len)
{
ans.push_back(make_pair(len - 1, len));
zero_to_one(len);
zero_to_one(len + 1);
}
void dec_len(int len)
{
ans.push_back(make_pair(len - 2, len - 1));
ans.push_back(make_pair(len - 1, len + 1));
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3724kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 11 2 3 5 6 5 6 5 6 6 7 2 3 3 4 4 5 5 6 6 7 7 8 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: 3ms
memory: 3568kb
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 3 4 4 6 2 3 3 5 -1 11 1 2 2 3 3 4 3 4 4 6 2 3 3 5 1 2 2 4 1 2 2 3 1 1 2 9 1 2 1 2 1 2 2 3 2 3 2 3 3 4 3 4 4 5 6 2 3 3 4 2 3 3 5 1 2 2 4 8 2 3 4 5 3 4 4 6 2 3 3 5 1 2 2 4 3 2 3 1 2 2 4 -1 10 1 2 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 3 4 4 5 10 1 2 2 3 3 4 4 ...
result:
wrong answer (l,r) is invalid (test case 12)