QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#740679#8058. Binary vs Ternarydezex#WA 3ms3724kbC++201.8kb2024-11-13 11:05:082024-11-13 11:05:08

Judging History

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

  • [2024-11-13 11:05:08]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3724kb
  • [2024-11-13 11:05:08]
  • 提交

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)