QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#172793#7178. Bishopsucup-team1359#AC ✓29ms17204kbC++142.3kb2023-09-09 20:42:392023-09-09 20:42:39

Judging History

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

  • [2023-09-09 20:42:39]
  • 评测
  • 测评结果:AC
  • 用时:29ms
  • 内存:17204kb
  • [2023-09-09 20:42:39]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,m,vis[4][105000],cnt;
//f[0][i]:(1,i)
//f[1][i]:(n,i)
//f[2][1<i<n]:(i,1)
//f[3][1<i<n]:(i,m)
void solve(int x,int y,int op) {//op: choose or not
    int tmpx=0,tmpy=0,ax=0,ay=0,bx=0,by=0,cx=0,cy=0,dx=0,dy=0;
    if (x==1) {
        tmpx=0;tmpy=y;
    } else if (x==n) {
        tmpx=1;tmpy=y;
    } else if (y==1) {
        tmpx=2;tmpy=x;
    } else {
        tmpx=3;tmpy=x;
    }
    if (vis[tmpx][tmpy]) return;
    vis[tmpx][tmpy]=op+1;
    if (op) cnt++;
    //a:(x,y) (n,y+n-x) (x+m-y,m)
    //b:(x,y) (n,y-n+x) (x+y-1,1)
    //c:(x,y) (1,y+1-x) (x+1-y,1)
    //d:(x,y) (1,y+x-1) (x-m+y,m)
    if (x+m-y<=n) {
        ax=x+m-y;ay=m;
    } else {
        ax=n;ay=y+n-x;
    }
    if (x+y-1<=n) {
        bx=x+y-1;by=1;
    } else {
        bx=n;by=y-n+x;
    }
    if (x+1-y>=1) {
        cx=x+1-y;cy=1;
    } else {
        cx=1;cy=y+1-x;
    }
    if (x-m+y>=1) {
        dx=x-m+y;dy=m;
    } else {
        dx=1;dy=y+x-1;
    }
    solve(ax,ay,1-op);
    solve(bx,by,1-op);
    solve(cx,cy,1-op);
    solve(dx,dy,1-op);
}
int main() {
    scanf("%d%d",&n,&m);
    if (!vis[0][1]) solve(1,1,1);
    if (!vis[0][m]) solve(1,m,1);
    if (!vis[1][1]) solve(n,1,1);
    if (!vis[1][m]) solve(n,m,1);
    for (int i=2;i<m;i++) {
        if (vis[0][i]) continue;
        solve(1,i,1);
    }
    for (int i=2;i<m;i++) {
        if (vis[1][i]) continue;
        solve(n,i,1);
    }
    for (int i=2;i<n;i++) {
        if (vis[2][i]) continue;
        solve(i,1,1);
    }
    for (int i=2;i<n;i++) {
        if (vis[3][i]) continue;
        solve(i,m,1);
    }
    printf("%d\n",cnt);
    for (int i=1;i<=m;i++) {
        if (vis[0][i]==2) printf("%d %d\n",1,i);
    }
    for (int i=1;i<=m;i++) {
        if (vis[1][i]==2) printf("%d %d\n",n,i);
    }
    for (int i=2;i<n;i++) {
        if (vis[2][i]==2) printf("%d %d\n",i,1);
    }
    for (int i=2;i<n;i++) {
        if (vis[3][i]==2) printf("%d %d\n",i,m);
    }
    return 0;
}
/*
xox.#.x
.#.#.#o
#.#.#.x
oxo#.#o

x.#.x.x.#.x
.#.#.#.#.#.
x.#.#.#.#.x
.#.#.x.#.#.

2|a,2|b:a+b-2
2|a,2!|b:a+b-1
a=b:a+b-2 (1,1)..(1,b-1) (a,1)..(a,b-1)
2!|a,2!|b,a!=b:a+b-1

x.x.x.#.#.
.#.#.#.#.x
#.#.#.#.#.
.#.#.#.#.x
#.#.#.#.#.
.x.x.#.#.#

x.x.x.
.#.#.#
#.#.#.
.#.#.#
#.#.#.
.x.x.#
*/

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

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 3900kb

input:

2 5

output:

6
1 1
1 3
1 5
2 1
2 3
2 5

result:

ok n: 2, m: 5, bishops: 6

Test #2:

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

input:

5 5

output:

8
1 1
1 2
1 3
1 4
1 5
5 2
5 3
5 4

result:

ok n: 5, m: 5, bishops: 8

Test #3:

score: 0
Accepted
time: 26ms
memory: 5476kb

input:

100000 100000

output:

199998
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 100000, m: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 29ms
memory: 17204kb

input:

100000 99999

output:

199998
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 100000, m: 99999, bishops: 199998

Test #5:

score: 0
Accepted
time: 15ms
memory: 14780kb

input:

100000 50000

output:

149998
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 100000, m: 50000, bishops: 149998

Test #6:

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

input:

1 100000

output:

100000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 1, m: 100000, bishops: 100000

Test #7:

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

input:

34535 99889

output:

134423
1 1
1 2
1 3
1 6
1 7
1 10
1 13
1 14
1 17
1 18
1 19
1 22
1 23
1 26
1 27
1 29
1 30
1 33
1 34
1 38
1 39
1 42
1 43
1 46
1 49
1 50
1 53
1 54
1 55
1 58
1 59
1 62
1 63
1 65
1 66
1 69
1 70
1 74
1 75
1 78
1 79
1 81
1 82
1 85
1 86
1 89
1 90
1 91
1 94
1 95
1 98
1 101
1 102
1 105
1 106
1 110
1 111
1 114
1...

result:

ok n: 34535, m: 99889, bishops: 134423

Test #8:

score: 0
Accepted
time: 15ms
memory: 11232kb

input:

12231 97889

output:

110119
1 1
1 2
1 3
1 6
1 7
1 10
1 13
1 14
1 17
1 18
1 22
1 23
1 26
1 27
1 30
1 33
1 34
1 37
1 38
1 42
1 43
1 46
1 47
1 49
1 50
1 53
1 54
1 57
1 58
1 59
1 62
1 63
1 66
1 67
1 69
1 70
1 73
1 74
1 77
1 78
1 79
1 82
1 83
1 86
1 87
1 89
1 90
1 93
1 94
1 98
1 99
1 102
1 103
1 106
1 109
1 110
1 113
1 114
1...

result:

ok n: 12231, m: 97889, bishops: 110119

Test #9:

score: 0
Accepted
time: 14ms
memory: 6212kb

input:

10000 100000

output:

109998
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 56
1 57
1 58
1 59
1 60
1 61
1 62
1 63
1 64
1 74
1 75
1 76
1 77
1 78
1 79
1 80
1 81
1 82
1 92
1 93
1 94
1 95
1 96
1 97
1 98
1 99
1 100
1 110
1 111
1 112
1 113
1 ...

result:

ok n: 10000, m: 100000, bishops: 109998

Test #10:

score: 0
Accepted
time: 10ms
memory: 10548kb

input:

13 99999

output:

100011
1 1
1 2
1 6
1 10
1 14
1 15
1 17
1 18
1 19
1 21
1 22
1 23
1 25
1 26
1 30
1 34
1 38
1 39
1 41
1 42
1 43
1 45
1 46
1 47
1 49
1 50
1 54
1 58
1 62
1 63
1 65
1 66
1 67
1 69
1 70
1 71
1 73
1 74
1 78
1 82
1 86
1 87
1 89
1 90
1 91
1 93
1 94
1 95
1 97
1 98
1 102
1 106
1 110
1 111
1 113
1 114
1 115
1 11...

result:

ok n: 13, m: 99999, bishops: 100011

Test #11:

score: 0
Accepted
time: 10ms
memory: 10500kb

input:

21 99999

output:

100019
1 1
1 2
1 5
1 6
1 9
1 10
1 13
1 14
1 17
1 18
1 22
1 23
1 26
1 27
1 30
1 31
1 34
1 35
1 38
1 39
1 41
1 42
1 45
1 46
1 49
1 50
1 53
1 54
1 57
1 58
1 62
1 63
1 66
1 67
1 70
1 71
1 74
1 75
1 78
1 79
1 81
1 82
1 85
1 86
1 89
1 90
1 93
1 94
1 97
1 98
1 102
1 103
1 106
1 107
1 110
1 111
1 114
1 115
...

result:

ok n: 21, m: 99999, bishops: 100019

Test #12:

score: 0
Accepted
time: 14ms
memory: 10992kb

input:

49999 100000

output:

149998
1 1
1 2
1 3
1 4
1 8
1 9
1 10
1 14
1 15
1 16
1 20
1 21
1 22
1 26
1 27
1 28
1 32
1 33
1 34
1 38
1 39
1 40
1 44
1 45
1 46
1 50
1 51
1 52
1 56
1 57
1 58
1 62
1 63
1 64
1 68
1 69
1 70
1 74
1 75
1 76
1 80
1 81
1 82
1 86
1 87
1 88
1 92
1 93
1 94
1 98
1 99
1 100
1 104
1 105
1 106
1 110
1 111
1 112
1 ...

result:

ok n: 49999, m: 100000, bishops: 149998

Test #13:

score: 0
Accepted
time: 23ms
memory: 12764kb

input:

33333 99999

output:

133331
1 1
1 2
1 6
1 10
1 14
1 18
1 22
1 26
1 30
1 34
1 38
1 42
1 46
1 50
1 54
1 58
1 62
1 66
1 70
1 74
1 78
1 82
1 86
1 90
1 94
1 98
1 102
1 106
1 110
1 114
1 118
1 122
1 126
1 130
1 134
1 138
1 142
1 146
1 150
1 154
1 158
1 162
1 166
1 170
1 174
1 178
1 182
1 186
1 190
1 194
1 198
1 202
1 206
1 21...

result:

ok n: 33333, m: 99999, bishops: 133331

Test #14:

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

input:

23342 98876

output:

122216
1 1
1 4
1 5
1 6
1 9
1 10
1 11
1 14
1 15
1 16
1 19
1 20
1 21
1 24
1 25
1 26
1 29
1 30
1 31
1 34
1 35
1 36
1 39
1 40
1 41
1 44
1 45
1 46
1 49
1 50
1 51
1 54
1 55
1 56
1 59
1 60
1 61
1 64
1 65
1 66
1 69
1 70
1 71
1 74
1 75
1 76
1 79
1 80
1 81
1 84
1 85
1 86
1 89
1 90
1 91
1 94
1 95
1 96
1 99
1 1...

result:

ok n: 23342, m: 98876, bishops: 122216

Test #15:

score: 0
Accepted
time: 21ms
memory: 10724kb

input:

56713 91234

output:

147946
1 1
1 2
1 3
1 4
1 7
1 8
1 9
1 14
1 15
1 19
1 20
1 21
1 22
1 26
1 27
1 32
1 33
1 34
1 37
1 38
1 39
1 44
1 45
1 49
1 50
1 51
1 52
1 56
1 57
1 62
1 63
1 64
1 67
1 68
1 69
1 74
1 75
1 79
1 80
1 81
1 82
1 86
1 87
1 92
1 93
1 94
1 97
1 98
1 99
1 104
1 105
1 109
1 110
1 111
1 112
1 116
1 117
1 122
1...

result:

ok n: 56713, m: 91234, bishops: 147946

Test #16:

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

input:

99995 99995

output:

199988
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 58
1 59
1 60
1 ...

result:

ok n: 99995, m: 99995, bishops: 199988

Test #17:

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

input:

12345 54321

output:

66665
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 18
1 19
1 20
1 21
1 22
1 23
1 24
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
1 66
1 67
1 68
1 69
1 70
1 71
1 72
1 82
1 83
1 84
1 85
1 86
1 87
1 88
1 97
1 98
1 99
1 100
1 101
1 102
1 103
1 104
1 105
1 113
1 114
1 11...

result:

ok n: 12345, m: 54321, bishops: 66665

Test #18:

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

input:

90000 92000

output:

181998
1 1
1 2
1 4
1 6
1 8
1 10
1 12
1 14
1 16
1 18
1 20
1 22
1 24
1 26
1 28
1 30
1 32
1 34
1 36
1 38
1 40
1 42
1 44
1 46
1 48
1 50
1 52
1 54
1 56
1 58
1 60
1 62
1 64
1 66
1 68
1 70
1 72
1 74
1 76
1 78
1 80
1 82
1 84
1 86
1 88
1 90
1 92
1 94
1 96
1 98
1 100
1 102
1 104
1 106
1 108
1 110
1 112
1 114
...

result:

ok n: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 9ms
memory: 7712kb

input:

10000 70000

output:

79998
1 1
1 2
1 3
1 4
1 7
1 8
1 9
1 14
1 15
1 16
1 19
1 20
1 21
1 26
1 27
1 28
1 31
1 32
1 33
1 38
1 39
1 40
1 43
1 44
1 45
1 50
1 51
1 52
1 55
1 56
1 57
1 62
1 63
1 64
1 67
1 68
1 69
1 74
1 75
1 76
1 79
1 80
1 81
1 86
1 87
1 88
1 91
1 92
1 93
1 98
1 99
1 100
1 103
1 104
1 105
1 110
1 111
1 112
1 11...

result:

ok n: 10000, m: 70000, bishops: 79998

Test #20:

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

input:

10000 70001

output:

80000
1 1
1 5
1 6
1 7
1 12
1 13
1 14
1 19
1 20
1 21
1 26
1 27
1 28
1 33
1 34
1 35
1 40
1 41
1 42
1 47
1 48
1 49
1 54
1 55
1 56
1 61
1 62
1 63
1 68
1 69
1 70
1 75
1 76
1 77
1 82
1 83
1 84
1 89
1 90
1 91
1 96
1 97
1 98
1 103
1 104
1 105
1 110
1 111
1 112
1 117
1 118
1 119
1 124
1 125
1 126
1 131
1 132...

result:

ok n: 10000, m: 70001, bishops: 80000

Test #21:

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

input:

10000 80000

output:

89998
1 1
1 2
1 4
1 5
1 7
1 8
1 10
1 13
1 16
1 18
1 19
1 21
1 22
1 24
1 27
1 30
1 32
1 33
1 35
1 36
1 38
1 41
1 44
1 46
1 47
1 49
1 50
1 52
1 55
1 58
1 60
1 61
1 63
1 64
1 66
1 69
1 72
1 74
1 75
1 77
1 78
1 80
1 83
1 86
1 88
1 89
1 91
1 92
1 94
1 97
1 100
1 102
1 103
1 105
1 106
1 108
1 111
1 114
1 ...

result:

ok n: 10000, m: 80000, bishops: 89998

Test #22:

score: 0
Accepted
time: 9ms
memory: 9944kb

input:

10000 80001

output:

90000
1 1
1 2
1 4
1 6
1 8
1 9
1 11
1 13
1 15
1 18
1 20
1 22
1 24
1 25
1 27
1 29
1 31
1 34
1 36
1 38
1 40
1 41
1 43
1 45
1 47
1 50
1 52
1 54
1 56
1 57
1 59
1 61
1 63
1 66
1 68
1 70
1 72
1 73
1 75
1 77
1 79
1 82
1 84
1 86
1 88
1 89
1 91
1 93
1 95
1 98
1 100
1 102
1 104
1 105
1 107
1 109
1 111
1 114
1 ...

result:

ok n: 10000, m: 80001, bishops: 90000

Test #23:

score: 0
Accepted
time: 10ms
memory: 5840kb

input:

10000 80002

output:

90000
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10
1 20
1 21
1 22
1 23
1 24
1 25
1 26
1 27
1 28
1 38
1 39
1 40
1 41
1 42
1 43
1 44
1 45
1 46
1 56
1 57
1 58
1 59
1 60
1 61
1 62
1 63
1 64
1 74
1 75
1 76
1 77
1 78
1 79
1 80
1 81
1 82
1 92
1 93
1 94
1 95
1 96
1 97
1 98
1 99
1 100
1 110
1 111
1 112
1 113
1 1...

result:

ok n: 10000, m: 80002, bishops: 90000

Test #24:

score: 0
Accepted
time: 7ms
memory: 8180kb

input:

10000 79999

output:

89998
1 1
1 2
1 3
1 7
1 8
1 9
1 10
1 14
1 15
1 19
1 20
1 21
1 22
1 26
1 27
1 31
1 32
1 33
1 34
1 38
1 39
1 43
1 44
1 45
1 46
1 50
1 51
1 55
1 56
1 57
1 58
1 62
1 63
1 67
1 68
1 69
1 70
1 74
1 75
1 79
1 80
1 81
1 82
1 86
1 87
1 91
1 92
1 93
1 94
1 98
1 99
1 103
1 104
1 105
1 106
1 110
1 111
1 115
1 1...

result:

ok n: 10000, m: 79999, bishops: 89998

Test #25:

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

input:

10000 79998

output:

89996
1 1
1 6
1 7
1 8
1 9
1 10
1 16
1 17
1 18
1 19
1 20
1 26
1 27
1 28
1 29
1 30
1 36
1 37
1 38
1 39
1 40
1 46
1 47
1 48
1 49
1 50
1 56
1 57
1 58
1 59
1 60
1 66
1 67
1 68
1 69
1 70
1 76
1 77
1 78
1 79
1 80
1 86
1 87
1 88
1 89
1 90
1 96
1 97
1 98
1 99
1 100
1 106
1 107
1 108
1 109
1 110
1 116
1 117
1...

result:

ok n: 10000, m: 79998, bishops: 89996

Test #26:

score: 0
Accepted
time: 6ms
memory: 11296kb

input:

11111 100000

output:

111110
1 1
1 6
1 7
1 8
1 9
1 15
1 16
1 17
1 18
1 24
1 25
1 26
1 27
1 33
1 34
1 35
1 36
1 42
1 43
1 44
1 45
1 51
1 52
1 53
1 54
1 60
1 61
1 62
1 63
1 69
1 70
1 71
1 72
1 78
1 79
1 80
1 81
1 87
1 88
1 89
1 90
1 96
1 97
1 98
1 99
1 105
1 106
1 107
1 108
1 114
1 115
1 116
1 117
1 123
1 124
1 125
1 126
1...

result:

ok n: 11111, m: 100000, bishops: 111110

Test #27:

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

input:

1 1

output:

1
1 1

result:

ok n: 1, m: 1, bishops: 1

Extra Test:

score: 0
Extra Test Passed