QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331757#8058. Binary vs Ternaryucup-team197#WA 2ms3624kbC++204.0kb2024-02-18 18:46:092024-02-18 18:46:09

Judging History

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

  • [2024-02-18 18:46:09]
  • 评测
  • 测评结果：WA
  • 用时：2ms
  • 内存：3624kb
查看
  • [2024-02-18 18:46:09]
  • 提交

answer

#include <iostream> 
#include <algorithm>
#include <array>
#include <map>
#include <set>
#include <numeric>
#include <vector>
#include <string>

using namespace std;

string a, b;
vector<pair<int, int>> ans;
int cnt_1_a = 0;
int cnt_1_b = 0;
int leading_a, leading_b;

void output(){
    cout << ans.size() << "\n";
    for(auto [l, r]: ans)
        cout << l << " " << r << "\n";
    ans.clear();
}

void turn_11(){
    int pos = -1;
    for(int i = a.size() - 2; i >= 0; --i){
        if(a[i] == '1' && a[i + 1] == '1'){
            pos = i;
            break;
        }
        if(a[i] == '1' && a[i + 1] == '0'){
            ans.push_back({i + 1, i + 2});
            a[i + 1] = '1';
            pos = i;
            break;
        }
    }

    if(pos == -1){
        cout << "-1\n";
        return;
    }

    while(a.size() > pos + 2){
        if(a[pos + 2] == '0'){
            ans.push_back({pos + 1 + 1, pos + 2 + 1});
            a[pos + 2] = '1';
        }
        ans.push_back({pos + 1, pos + 2});
        ans.push_back({pos + 2, pos + 4});
        a.erase(a.begin() + pos + 2);
    }

    while(pos != leading_a){
        if(a[pos - 1] == '0'){
            ans.push_back({pos, pos + 1});
            a.erase(a.begin() + pos - 1);
            --pos;
            continue;
        }
        ans.push_back({pos, pos + 1});
        ans.push_back({pos + 1, pos + 3});
        a.erase(a.begin() + pos - 1);
        --pos;
    }
}

void expand(){
    int pos = leading_a;
    for(int i = b.size() - 1; i >= leading_b + 1; --i){
        if(b[i] == '1'){
            ans.push_back({pos + 1, pos + 2});
            ans.push_back({pos + 1, pos + 2});
            ans.push_back({pos + 2, pos + 3});
        }
        else{
            ans.push_back({pos + 1, pos + 2});
            ans.push_back({pos + 1, pos + 2});
        }
    }

    if(b.size() == leading_b) return;

    if(b[leading_b] == '1'){
        ans.push_back({pos + 1, pos + 2});
        ans.push_back({pos + 2, pos + 4});
    }
    else{
        ans.push_back({pos + 1, pos + 2});
        ans.push_back({pos + 2, pos + 4});
    }

    output();
}

void solve_real(){
    leading_a = 0, leading_b = 0;
    {
        for(int i = 0; i < a.size(); ++i){
            if(a[i] == '1') break;
            leading_a = i + 1;
        }
        for(int i = 0; i < b.size(); ++i){
            if(b[i] == '1') break;
            leading_b = i + 1;
        }

        if(leading_a < leading_b){
            cout << "-1\n";
            return;
        }

        ans.push_back({1, leading_a - leading_b + 1});
        a.erase(0, leading_a - leading_b);
        leading_a = leading_b;
    }

    // cout << "turn 11" << endl;
    turn_11();
    // cout << endl << a <<  " " << b << " a b" << endl;
    // cout << "expand" << endl;
    expand();
    // cout << endl << a << " " << b << "after" << endl;
    // cout << "after" << endl;
}

void solve(){
    cin >> a >> b;
    ans.clear();

    cnt_1_a = cnt_1_b = 0;
    for(char c: a)
        cnt_1_a += c == '1';
    for(char c: b)
        cnt_1_b += c == '1';

    if(!cnt_1_a){
        if(cnt_1_b || b.size() > a.size()){
            cout << "-1\n";
            return;
        }
        while(a.size() > b.size()){
            ans.push_back({a.size() - 1, a.size()});
            a.pop_back();
        }
        output();
        return;
    }

    if(!cnt_1_b){
        cout << "-1\n";
        return;
    }

    if(cnt_1_a == 1 && a.back() == '1'){
        if(cnt_1_b != cnt_1_a || b.back() != '1' || b.size() > a.size()){
            cout << "-1\n";
            return;
        }
        while(a.size() > b.size()){
            ans.push_back({1, 2});
            a.pop_back();
            a.pop_back();
            a += "1";
        }
        output();
        return;
    }

    solve_real();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;

    while(t--)
        solve();
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

3
1
111
110110
1101010
1111
111111

output:

-1
26
1 1
5 6
4 5
5 7
3 4
2 3
3 5
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
1 2
1 2
2 3
1 2
2 4
22
1 1
2 3
3 5
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
1 2
1 2
2 3
1 2
2 4

result:

ok Haitang Suki (3 test cases)

Test #2:

score: -100
Wrong Answer
time: 2ms
memory: 3616kb

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:

17
1 1
3 4
4 5
3 4
4 6
2 3
3 5
1 2
2 4
1 2
1 2
2 3
1 2
1 2
2 3
1 2
2 4
-1
14
1 1
1 2
2 3
1 2
2 4
2 3
1 2
2 4
1 2
2 4
1 2
1 2
1 2
2 4
15
1 1
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
2 4
12
1 1
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
2 3
1 2
2 4
12
1 1
2 3
3 4
2 3
3 5
1 2
2 4
1 2
1 2
2 3
1 2
2 4
12...

result:

wrong answer (l,r) is invalid (test case 13)
English 繁體中文 简体中文

服务器时间: 2024-12-05 11:19:46 | 开源项目