QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#743032#8058. Binary vs TernaryQSteve_PaulTL 2ms3812kbC++233.4kb2024-11-13 18:00:102024-11-13 18:00:12

Judging History

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

  • [2024-11-13 18:00:12]
  • 评测
  • 测评结果：TL
  • 用时：2ms
  • 内存：3812kb
查看
  • [2024-11-13 18:00:10]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = __int128;

void solve()
{
    string s;
    string t;
    cin >> s >> t;
    if (s.length() == 1 || t.length() == 1)
    {
        if (s == t)
            cout << 0 << "\n";
        else
            cout << -1 << "\n";
        return;
    }
    s = " " + s;
    t = " " + t;
    vector<pair<int, int>> ans;
    auto change = [&](int l, int r) {
        i64 tmp = 0;
        for (int i = l; i <= r; i++)
        {
            tmp *= 3;
            tmp += s[i] - '0';
        }
        string ss = s.substr(0, l);
        vector<int> num;
        do
        {
            num.emplace_back(tmp & 1);
            tmp >>= 1;
        } while (tmp);
        reverse(num.begin(), num.end());
        for (auto bit : num)
            ss.push_back(bit + '0');
        ss.append(s.substr(r + 1));
        s = ss;
        ans.push_back({l, r});
    };
    for (int i = 1; i < s.length();)
    {
        if (s[i] == '1') {
            i++;
            continue;
        }
        int j = i;
        for (; j < s.length() && s[j] == '0'; j++)
            ;
        if (j >= s.length())
            break;
        if (j == i)
            continue;
        change(i, j);
        i = j;
    }
    for (int i = (int)s.length() - 1; i >= 1; i--)
    {
        if (i == 1)
            break;
        if (s[i] == '0')
            continue;
        change(i - 1, i);
        change(i, i + 1);
    }
    change(2, s.length() - 1);
    int cnt = 0;
    for (const char &ch : t)
        cnt += (ch == '1');
    cnt--;
    auto copy10 = [&](int i) {
        change(i, i + 1);
        change(i, i + 1);
        change(i, i + 2);
        change(i + 1, i + 2);
        change(i, i + 2);
    };

    if (t.back() == '1')
    {
        cnt--;
        for (int i = 1; cnt--; i += 2)
            copy10(i);
        int idx = s.length() - 2;
        change(idx, idx + 1);
        change(idx, idx + 1);
        change(idx, idx + 2);
        change(idx + 1, idx + 2);
        for (int j = 1; j < (int)t.length() - 1;)
        {
            int cnt0 = 0;
            int k;
            for (k = j + 1; k < t.length() && t[k] != '1'; k++)
                cnt0++;

            int i = j;
            if (cnt0 == 0)
                change(i + 1, i + 2);
            else
            {
                cnt0--;
                while (cnt0--)
                {
                    change(i, i + 1);
                    change(i, i + 1);
                }
            }
            j = k;
        }
    }
    else
    {
        for (int i = 1; cnt--; i += 2)
            copy10(i);

        for (int j = 1; j < (int)t.length();)
        {
            int cnt0 = 0;
            int k;
            for (k = j + 1; k < t.length() && t[k] != '1'; k++)
                cnt0++;

            int i = j;
            if (cnt0 == 0)
                change(i + 1, i + 2);
            else
            {
                cnt0--;
                while (cnt0--)
                {
                    change(i, i + 1);
                    change(i, i + 1);
                }
            }
            j = k;
        }
    }
    cout << ans.size() << "\n";
    for (auto [l, r] : ans)
        cout << l << " " << r << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

3
1
111
110110
1101010
1111
111111

output:

-1
24
3 4
3 4
4 5
2 3
3 4
1 2
2 3
2 5
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
3 5
5 6
5 6
5 7
6 7
5 7
2 3
36
3 4
4 5
2 3
3 4
1 2
2 3
2 4
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
3 5
5 6
5 6
5 7
6 7
5 7
7 8
7 8
7 9
8 9
7 9
9 10
9 10
9 11
10 11
2 3
3 4
4 5
5 6
6 7

result:

ok Haitang Suki (3 test cases)

Test #2:

score: 0
Accepted
time: 2ms
memory: 3812kb

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:

16
2 3
3 4
1 2
2 3
2 5
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
2 3
3 4
-1
4
2 5
1 2
2 3
2 2
23
2 3
2 3
3 4
1 2
2 3
2 3
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
3 5
5 6
5 6
5 7
6 7
2 3
3 4
4 5
13
2 2
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
3 5
2 3
3 4
8
1 2
2 3
2 4
1 2
1 2
1 3
2 3
2 3
11
3 4
2 3
3 4
1 2
2 3
2 4
1...

result:

ok Haitang Suki (1000 test cases)

Test #3:

score: 0
Accepted
time: 2ms
memory: 3784kb

input:

1000
1110
110
1
11
1110
110
101
111
100
1001
10
110
1001
10011
10
11010
100
111
1101
1001
1
111
1
1
11
1
1011
1101
1
11
111
10
100
1110
1001
10
10
11
1
10
11
11
111
1100
10100
11001
10
110
1001
101
1
10011
100
10
10110
111
1100
110
11010
11
1000
1101
1010
1
1100
100
11010
1
1011
1
11001
1110
11
1110...

output:

11
2 3
3 4
1 2
2 3
2 4
1 2
1 2
1 3
2 3
1 3
2 3
-1
11
2 3
3 4
1 2
2 3
2 4
1 2
1 2
1 3
2 3
1 3
2 3
15
2 3
1 2
2 3
2 2
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
2 3
3 4
7
2 3
1 2
1 2
1 3
2 3
1 2
1 2
7
2 2
1 2
1 2
1 3
2 3
1 3
2 3
16
2 4
1 2
2 3
2 2
1 2
1 2
1 3
2 3
1 3
3 4
3 4
3 5
4 5
1 2
1 2
5 6
12
2 2
1 2
1 ...

result:

ok Haitang Suki (1000 test cases)

Test #4:

score: -100
Time Limit Exceeded

input:

1000
11110010
11110001
11010110
1001
11011110
1001110
111101100
111111100
110
101111001
10000100
10
1100100
101010
100
1000
1011110
110101
1001
10001111
100011111
1001111011
1110100
1010
1001100001
1000
11
101101
1000001111
11100
101001101
1
11
111001111
100101101
10
1
10111
1111000111
1101
10111
11...

output:

result:
English 繁體中文 简体中文

伺服器時間: 2024-12-03 07:26:38 | 開源專案