QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#172793 | #7178. Bishops | ucup-team1359# | AC ✓ | 29ms | 17204kb | C++14 | 2.3kb | 2023-09-09 20:42:39 | 2023-09-09 20:42:39 |
Judging History
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,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
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