QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#768149#8058. Binary vs TernaryyangjlWA 1ms3604kbC++204.1kb2024-11-21 01:12:352024-11-21 01:12:36

Judging History

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

  • [2024-11-21 01:12:36]
  • 评测
  • 测评结果：WA
  • 用时：1ms
  • 内存：3604kb
查看
  • [2024-11-21 01:12:35]
  • 提交

answer

/**
 *    author:  yangjl
 *    created: 2024.11.21 00:05:41
**/
#include <bits/stdc++.h>
#ifdef YJL
#include "debug.h"
#else
#define debug(...)0
#endif
using namespace std;
using ll = long long;

template<class T>
istream& operator>>(istream& is, vector<T>& v) {
    for(auto& x : v) {
        is >> x;
    }
    return is;
}

void print(vector<pair<int, int>> ans) {
    assert(ans.size() <= 512);
    cout << ans.size() << "\n";
    for(auto [l, r] : ans) {
        cout << l + 1 << ' ' << r + 1 << "\n";
    }
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int tt;
    cin >> tt;
    while(tt--) {
        string A, B;
        cin >> A >> B;
        if(A == B) {
            print({});
            continue;
        }

        if(A == "1") {
            cout << "-1\n";
            continue;
        }

        vector<pair<int, int>> ans;
        // A -> 11....1 -> 110 -> 11
        for(int i = 1; i < A.size(); ++i) {
            if(A[i] == '0') {
                // 10->11
                A[i] = '1';
                ans.emplace_back(i - 1, i);
            }
        }
        while(true) {
            int i = A.find_last_of('1');
            if(i <= 1) {
                break;
            }
            // 11->100
            A.replace(i - 1, 2, "100");
            ans.emplace_back(i - 1, i);
        }
        if(A.size() > 2) {
            // 0000->0
            ans.emplace_back(2, A.size() - 1);// 110
            ans.emplace_back(1, 2);// 111
            ans.emplace_back(0, 1);// 1001
            ans.emplace_back(1, 3);// 11
            A = "11";
        }

        int second1 = find(B.begin() + 1, B.end(), '1') - B.begin();
        if(second1 == B.size()) {// B = 100...
            int need0 = second1 - 1;
            int add1 = (need0 + 1) / 2 - 1;
            for(int i = 0; i < add1; ++i) {
                ans.emplace_back(0, 1);// 100
                ans.emplace_back(0, 1);// 110
                ans.emplace_back(1, 2);// 111
            }
            for(int i = add1 + 1; i >= 1; --i) {
                ans.emplace_back(i - 1, i);// 11 -> 100
            }
            if(need0 % 2 == 1) {
                ans.emplace_back(1, 2);// 00->0
            }
            print(ans);
            continue;
        }

        // B = 11...
        // B = 10..01...
        for(int i = (int)B.size() - 1; i > second1; --i) {
            ans.emplace_back(0, 1);// 100
            ans.emplace_back(0, 1);// 110
            if(B[i] == '1') {
                ans.emplace_back(1, 2);
            }
        }
        // 11 -> 10..01
        int need0 = second1 - 1;
        if(need0 == 0) {
            print(ans);
            continue;
        }

        int add1 = (need0 + 1) / 2;
        for(int i = 0; i < add1; ++i) {
            ans.emplace_back(0, 1);// 100
            ans.emplace_back(0, 1);// 110
            ans.emplace_back(1, 2);// 111
        }
        for(int i = add1; i >= 1; --i) {
            ans.emplace_back(i - 1, i);// 11 -> 100
        }

        if(need0 % 2 == 1) {
            ans.emplace_back(1, 2);// 00->0
        }
        print(ans);
    }
    return 0;
}
/*

1
10001
10

12
1 2
2 3
3 4 -> 11111
4 5
3 4
2 3 -> 11000000
3 8
2 3 -> 111
1 2
2 4 -> 11
1 2 -> 100
2 3 -> 10


还得打表
constexpr int N = 5;
for(int i = 0; i < 1 << N; ++i) {
        int x = 0;
        for(int j = N - 1; j >= 0; --j) {
            int w = (i >> j & 1);
            x = x * 3 + w;
        }

        string s;
        for(int j = 0; j < N; ++j) {
            int w = (i >> j & 1);
            s += char('0' + w);
        }
        while(s.size() > 1 and s.back() == '0') {
            s.pop_back();
        }
        reverse(s.begin(), s.end());

        string t;
        while(x) {
            t += char('0' + x % 2);
            x /= 2;
        }
        reverse(t.begin(), t.end());
        if(t.empty()) {
            t += '0';
        }
        // debug(s, t);
        if(count(s.begin(), s.end(), '1') > count(t.begin(), t.end(), '1')) {
            debug(s, t);
        }
    }
*/
源文件, 语言: C++20

详细

Test #1:

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

input:

3
1
111
110110
1101010
1111
111111

output:

-1
22
2 3
5 6
5 6
4 5
3 4
2 3
3 10
2 3
1 2
2 4
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
2 3
1 2
1 2
18
3 4
2 3
3 6
2 3
1 2
2 4
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
Wrong Answer
time: 1ms
memory: 3604kb

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:

12
3 4
4 5
4 5
3 4
2 3
3 8
2 3
1 2
2 4
1 2
1 2
2 3
-1
12
1 2
2 3
3 4
4 5
3 4
2 3
3 8
2 3
1 2
2 4
1 2
2 3
13
1 2
3 4
2 3
3 6
2 3
1 2
2 4
1 2
1 2
2 3
1 2
1 2
2 3
6
1 2
1 2
1 2
1 2
1 2
2 3
8
2 3
3 4
3 4
2 3
3 6
2 3
1 2
2 4
9
2 3
4 5
4 5
3 4
2 3
3 8
2 3
1 2
2 4
6
2 3
2 3
3 4
2 3
1 2
2 4
-1
11
1 2
4 5
4 ...

result:

wrong answer S!=T after all operations (test case 13)
English 繁體中文 简体中文

服务器时间: 2024-12-03 07:42:49 | 开源项目