QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#739672#8058. Binary vs TernaryshengZzzAC ✓22ms3852kbC++172.8kb2024-11-12 22:39:232024-11-12 22:39:25

Judging History

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

  • [2024-11-12 22:39:25]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:3852kb
  • [2024-11-12 22:39:23]
  • 提交

answer

#include<bits/stdc++.h>
#define mk make_pair
using namespace std;
const int N=500;
vector<pair<int,int> > ans;
void change1(int l) {//  11 -> 111
    pair<int,int> t;
    t.first=l; t.second=l+1; ans.push_back(t);
    t.first=l; t.second=l+1; ans.push_back(t);
    t.first=l+1; t.second=l+2; ans.push_back(t);
}

void change2(int l) {//11 -> 110
    pair<int,int> t;
    t.first=l; t.second=l+1; ans.push_back(t);
    t.first=l; t.second=l+1; ans.push_back(t);
}

void change3(int l) {// 111 -> 11
    pair<int,int> t;
    t.first=l; t.second=l+1; ans.push_back(t);
    t.first=l+1; t.second=l+3; ans.push_back(t);
}

void change4(int l,int sm) {//11 -> 1 0(sm) 1
    if(sm==0) return;
    pair<int,int> t;
    t.first=l; t.second=l+1; ans.push_back(t);
    t.first=l; t.second=l+2; ans.push_back(t);
    t.first=l+1; t.second=l+2; ans.push_back(t);
    for(int i=2;i<=sm;i++) {
        t.first=l; t.second=l+1;  ans.push_back(t);
        t.first=1; t.second=l+1; ans.push_back(t);
    }
}

char s[N],t[N];
int n,m;
bool cmd(char *a,char *b) {
    if(n!=m) return 1;
    for(int i=1;i<=n;i++)
        if(a[i]!=b[i]) return 1;
    return 0;
}
void solve() {
    scanf("%s%s",s+1,t+1); int sum=0;
    n=strlen(s+1); m=strlen(t+1);
    if(cmd(s+1,t+1)==0) {cout<<"0\n"; return;}
    if(n==1 || m==1) {cout<<"-1\n"; return;}
    for(int i=n,lst=0;i>=1;i--) {
        while(s[i]=='0') i--;
        if(!lst) {
            if(i==n) { sum+=1; lst=n; continue;}
            if(i!=n-1) {
                pair<int,int> t;
                t.first=i+1; t.second=n; ans.push_back(t);
            }
            pair<int,int> t; t.first=i; t.second=i+1;
            ans.push_back(t); sum+=2; lst=i;
        } else {
            pair<int,int> t;
            t.first=i+1; t.second=lst; ans.push_back(t);
            if(i+1==lst) ans.pop_back();
            lst=i; sum++;
        }
    }

    for(int i=3;i<=sum;i++) change3(1);

    int ed=2; while(ed<=m && t[ed]=='0') ed++;
    if(ed==m+1) {
        for(int i=3;i<=m;i++) {
            pair<int,int> t;
            t.first=1,t.second=2; ans.push_back(t);
            t.first=1,t.second=2; ans.push_back(t);
        }
        pair<int,int> t;
        t.first=1,t.second=2; ans.push_back(t);
        t.first=2,t.second=3; ans.push_back(t);

        cout<<ans.size()<<"\n";
        for(auto it:ans) cout<<it.first<<" "<<it.second<<"\n";
        return;
    }
    for(int i=m;i>ed;i--) {
        if(t[i]=='0') change2(1);
        else change1(1);
    }
    change4(1,ed-2);
    cout<<ans.size()<<"\n";
    for(auto it:ans) cout<<it.first<<" "<<it.second<<"\n";
}

void init() {
    ans.clear();
}

int main() {
    int T;scanf("%d",&T);
    while(T--) {
        init(); solve();
    }
    return 0;
}

/*
10000
1001
*/

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

3
1
111
110110
1101010
1111
111111

output:

-1
20
5 6
3 4
1 2
2 4
1 2
2 4
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
16
1 2
2 4
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: 0
Accepted
time: 1ms
memory: 3832kb

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:

9
4 5
3 4
1 2
2 4
1 2
2 4
1 2
1 2
2 3
-1
3
2 5
1 2
2 3
9
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
4
3 4
2 3
1 2
2 4
6
4 5
3 4
1 2
2 4
1 2
2 4
3
2 3
1 2
2 4
-1
8
4 5
2 3
1 2
2 4
1 2
2 4
1 2
2 3
10
1 2
1 2
1 2
2 3
1 2
1 2
2 3
1 2
1 2
2 3
7
2 5
1 2
1 2
1 3
2 3
1 2
1 2
-1
9
1 2
1 2
...

result:

ok Haitang Suki (1000 test cases)

Test #3:

score: 0
Accepted
time: 1ms
memory: 3836kb

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:

7
3 4
1 2
2 4
1 2
2 4
1 2
1 2
-1
7
3 4
1 2
2 4
1 2
2 4
1 2
1 2
4
2 3
1 2
1 2
2 3
7
2 3
1 2
1 2
1 3
2 3
1 2
1 2
3
1 2
1 2
1 2
9
2 4
1 2
1 2
2 3
1 2
1 3
2 3
1 2
1 2
8
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
5
2 3
1 2
1 2
1 2
2 3
8
3 4
1 2
2 4
1 2
1 3
2 3
1 2
1 2
-1
0
-1
8
2 3
1 2
2 4
1 2
1 2
2 3
1 2
1 2
-1
4
...

result:

ok Haitang Suki (1000 test cases)

Test #4:

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

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:

25
7 8
5 7
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
2 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
2 3
16
7 8
5 6
3 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 3
2 3
1 2
1 2
25
7 8
3 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
2 3
1 2
1 2
2 3
1 2
1 3
2 3
1 2
1 2
32
8 9
7 8
5 6
1 2
2 4
1 2
...

result:

ok Haitang Suki (1000 test cases)

Test #5:

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

input:

1000
11
10
1111101
10
1011010001
1101010100
101110
101101001
110
110
100001
1111
10
1001100
1101101000
1
1
1110
11
1110000
110111010
1001000
110100000
1
1110101001
10
11111
1001101
110
1110
111
11
11000
1
111111
1
101111111
1100100100
101101100
1111110
10001
1001
1100110100
100
1001
101001
100011000...

output:

2
1 2
2 3
11
6 7
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 3
28
7 10
5 6
2 3
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
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
1 2
26
5 6
2 3
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
2 3
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
2 3
1 2
1 3
2 3
0
7
2 6
1 2
1 2
2 3
...

result:

ok Haitang Suki (1000 test cases)

Test #6:

score: 0
Accepted
time: 3ms
memory: 3648kb

input:

1000
1010100001
1101101111
1000001111
1100000010
1101001000
1111011000
1011010000
1101111100
1000011000
1001010110
1100010110
1001001000
1000111110
1101100000
1101011010
1111000101
1110111001
1000000010
1111110000
1001100000
1000010111
1010101110
1110101000
1111100001
1110110101
1011100001
110111101...

output:

29
6 10
4 5
2 3
1 2
2 4
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
1 2
1 2
2 3
1 2
1 2
2 3
1 2
1 2
24
2 7
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
30
8 10
7 8
5 7
3 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1...

result:

ok Haitang Suki (1000 test cases)

Test #7:

score: 0
Accepted
time: 3ms
memory: 3688kb

input:

1000
1010010100
1100011110
1111100001
1110100100
1001011000
1001011110
1110100101
1000001010
1110010010
1110110010
1010001000
1110011110
1010101110
1100011011
1000000100
1100100001
1010001011
1111101100
1001110101
1010001011
1001001010
1010010111
1011001010
1110001111
1000001000
1111001011
100111101...

output:

31
9 10
8 9
7 8
4 6
2 3
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
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
1 2
1 2
1 2
1 2
28
6 10
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
2 3
31
8 10
7 8
5 6
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
...

result:

ok Haitang Suki (1000 test cases)

Test #8:

score: 0
Accepted
time: 11ms
memory: 3648kb

input:

1000
10001101010010010010011111000100011110010111010011100110011
101100010110011111000010101
101111101000100010010101
10100101000010100001101000001101010111
1101110100111100111110101101101000110101010010011100
1110100100101011000011
1100001100101011010000111010111000000101
11101000100000101000001111...

output:

134
56 58
52 54
47 49
45 46
41 42
38 40
31 34
27 30
20 22
17 19
14 16
11 13
9 10
7 8
2 5
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2...

result:

ok Haitang Suki (1000 test cases)

Test #9:

score: 0
Accepted
time: 11ms
memory: 3732kb

input:

1000
100000000110011000110010101
11110000
10010001001001111000110110001001011101011110
111011111001100111101101000011111110
1011110110011110110011000111010011111000100110011010101000000
1101001
1001010
10101110110001101010001000111001000111011000110111111110
11101001110000011100
10100010111000000110...

output:

36
26 27
24 25
21 23
16 19
12 14
2 10
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
2 3
1 2
1 2
2 3
144
43 44
39 40
37 38
33 34
30 32
26 29
23 24
18 21
12 14
9 11
5 8
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4...

result:

ok Haitang Suki (1000 test cases)

Test #10:

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

input:

1000
11111100001000000001110111011111001010011110100001100001011
1111001111111111100011111011011101100110000011010010
110010011001001110101
1011101100
1110
110111111010010011110010101101000101111000111111111010111111000
10101101101010001100111
11110001001011110010
1111010110010101010001011
111
10011...

output:

198
57 58
52 56
46 50
44 45
38 40
36 37
33 35
27 28
23 24
12 20
7 11
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2...

result:

ok Haitang Suki (1000 test cases)

Test #11:

score: 0
Accepted
time: 11ms
memory: 3852kb

input:

1000
111100011011111100101110101
11111011000101100110001011101011
10011001010101110111011111111110
11010100000
11001100100011101000101111011011
10011101010110110
101011000011
101110100101101010000111010010101101
1110111110000101110100101101
1101110111100000110001001011000001111101010011
111111100110...

output:

115
26 27
24 25
20 21
17 19
10 11
5 8
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
1 2
2 3
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
1 2
2 3
1 2
1 2
2 3
1 2
1 2
1 2
1 2
2 3
1 2
1 2
1 2
1 2
1 2
1 2
1 ...

result:

ok Haitang Suki (1000 test cases)

Test #12:

score: 0
Accepted
time: 11ms
memory: 3652kb

input:

1000
11000001100100011000100101001101100011100100110010111011000
1111101101110
1000001011101111011010011001001100011000
11001110110101100011001011000111110111010000111010010
100101011
1011010011111100
100
11101000000110100100110100110001100111110111110010001001010
11110000011100011110010100000011100...

output:

96
57 59
56 57
54 55
50 51
47 49
43 45
40 42
34 37
31 32
27 29
25 26
22 24
18 21
13 16
10 12
3 8
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2...

result:

ok Haitang Suki (1000 test cases)

Test #13:

score: 0
Accepted
time: 18ms
memory: 3732kb

input:

1000
1110101101011010111111111001001001101101001111100001000010110001
1111100111110101010011010111100100111110001111111100010100010010
1101011000001010101000000011111111101101010111100011110011100011
1110010001100011111001000000111111111111000010001100000100000010
10111101100001101001001011010001101...

output:

244
61 64
58 59
53 57
48 52
41 43
39 40
36 37
32 34
29 31
26 28
16 17
14 15
11 12
9 10
6 7
4 5
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2...

result:

ok Haitang Suki (1000 test cases)

Test #14:

score: 0
Accepted
time: 22ms
memory: 3648kb

input:

1000
1010011000110100110000001111001100100010111111101001000101111100
1111001000000001111001010110011101110101000010000001010011001010
1001100100100101111101011111011010100111000001100101001110001010
1010101100010001100001111010010110011101010001011101010110110011
11101011110000111111101011111011001...

output:

228
63 64
62 63
57 58
53 56
50 52
48 49
40 41
36 39
33 35
29 31
19 25
15 17
13 14
8 11
4 6
2 3
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2...

result:

ok Haitang Suki (1000 test cases)

Test #15:

score: 0
Accepted
time: 19ms
memory: 3840kb

input:

1000
1011111000111010111001111001000011101001100011100000101110000101
1001100010000111101011001010000101100110101101010100101011001010
1001101111000001100111110111011111110011101010101101010110011100
1100101011100110001011000111111101001001111100110010100101001110
11111101100001101001110111010011001...

output:

229
63 64
58 62
54 55
48 53
42 45
38 40
36 37
29 33
26 28
20 22
16 17
14 15
8 11
2 3
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4...

result:

ok Haitang Suki (1000 test cases)

Test #16:

score: 0
Accepted
time: 22ms
memory: 3724kb

input:

1000
1001101101110101111101001110000111110100010100101111101001011001
1110001000100001001001001111111100101101101000100100111000001011
1000001000001110101011111011011111011101011100001101101111100001
1100111111001100100010010101001000101000101100100011101001111011
10110101000000011111000111111110000...

output:

239
62 64
59 60
56 58
54 55
48 49
45 47
43 44
39 42
37 38
28 32
23 25
21 22
15 16
13 14
9 10
6 7
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4...

result:

ok Haitang Suki (1000 test cases)

Test #17:

score: 0
Accepted
time: 22ms
memory: 3776kb

input:

1000
1101011111000011000110010000110000111110001000101110100110001110
1100101111001111100011111011001111000110100110110001010111101011
1010110111100001110110101111101000000111010111010101010110010111
1010011010011111001010111101100011110100111111100100111011101101
11100011010101001001001001110100000...

output:

235
63 64
58 61
54 56
52 53
48 49
44 47
40 43
31 35
25 29
22 24
17 20
11 15
5 6
3 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
1 2
2 4
...

result:

ok Haitang Suki (1000 test cases)

Extra Test:

score: 0
Extra Test Passed