QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175782 | #7178. Bishops | ucup-team1231# | AC ✓ | 170ms | 92896kb | C++14 | 2.6kb | 2023-09-10 23:34:32 | 2023-09-10 23:34:33 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
map<pii,int> M;
vi a[500000],b[500000];
vi adj[500000];
int visited[500000];
int keep[500000];
int main() {
cin.tie(0); cout.tie(0);
#define endl "\n"
ios::sync_with_stdio(0);
int n,m;
cin >> n >> m;
int i;
if (n == 1) {
cout << m << endl;
for (i = 0; i < m; i++) cout << 1 << " " << i+1 << endl;
return 0;
}
else if (m == 1) {
cout << n << endl;
for (i = 0; i < n; i++) cout << i+1 << " " << 1 << endl;
return 0;
}
int c = 0;
for (i = 0; i < m; i++) M[mp(0,i)] = c++;
for (i = 1; i < n-1; i++) M[mp(i,0)] = c++;
for (i = 0; i < m; i++) M[mp(n-1,i)] = c++;
for (i = 1; i < n-1; i++) M[mp(i,m-1)] = c++;
for (auto [p,x]: M) {
a[p.first+p.second].pb(x);
b[p.first-p.second+m].pb(x);
}
for (i = 0; i < 500000; i++) {
if (a[i].size() >= 2) {
adj[a[i][0]].pb(a[i][1]);
adj[a[i][1]].pb(a[i][0]);
}
if (b[i].size() >= 2) {
adj[b[i][0]].pb(b[i][1]);
adj[b[i][1]].pb(b[i][0]);
}
}
int j,ans = 0;
for (i = 0; i < c; i++) {
if (!visited[i] && (adj[i].size() <= 1)) {
int u = i;
vi o;
do {
int f = 0;
visited[u] = 1;
o.pb(u);
for (int v: adj[u]) {
if (!visited[v]) {
u = v;
f = 1;
break;
}
}
if (!f) break;
} while (u != i);
for (j = 0; j < o.size(); j += 2) keep[o[j]] = 1,ans++;
}
}
for (i = 0; i < c; i++) {
if (!visited[i]) {
int u = i;
vi o;
do {
int f = 0;
visited[u] = 1;
o.pb(u);
for (int v: adj[u]) {
if (!visited[v]) {
u = v;
f = 1;
break;
}
}
if (!f) break;
} while (u != i);
for (j = 0; j < o.size(); j += 2) keep[o[j]] = 1,ans++;
}
}
cout << ans << endl;
for (auto [p,x]: M) {
if (keep[x]) cout << p.first+1 << " " << p.second+1 << endl;
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 6ms
memory: 38932kb
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: 9ms
memory: 39392kb
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: 148ms
memory: 91528kb
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: 163ms
memory: 92896kb
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: 94ms
memory: 79972kb
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: 8ms
memory: 40784kb
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: 106ms
memory: 76504kb
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: 104ms
memory: 68976kb
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: 107ms
memory: 69176kb
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: 84ms
memory: 66252kb
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: 95ms
memory: 66772kb
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: 116ms
memory: 79012kb
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: 102ms
memory: 75656kb
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: 118ms
memory: 72784kb
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: 140ms
memory: 79124kb
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: 159ms
memory: 91468kb
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: 59ms
memory: 57968kb
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: 170ms
memory: 88948kb
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: 73ms
memory: 60584kb
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: 74ms
memory: 60960kb
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: 75ms
memory: 63200kb
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: 77ms
memory: 63616kb
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: 77ms
memory: 63408kb
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: 71ms
memory: 63920kb
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: 82ms
memory: 64176kb
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: 85ms
memory: 69488kb
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: 6ms
memory: 39888kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed