QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175678 | #7178. Bishops | oscaryang | AC ✓ | 317ms | 81388kb | C++14 | 1.6kb | 2023-09-10 21:26:48 | 2023-09-10 21:26:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define mkp make_pair
#define pii pair<int,int>
#define vc vector
#define pb emplace_back
const int N = 5e5+5;
//in&out
inline int read() {
int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch=='-'), ch = getchar();
while(isdigit(ch)) x = (x*10)+(ch^48), ch=getchar(); return w?-x:x;
}
inline void write(int x) { if(x<0) putchar('-'), x = -x; if(x>9) write(x/10); putchar(x%10+'0'); }
inline void writec(int x) { write(x); putchar(32); }
inline void writee(int x) { write(x); putchar(10); }
int n, m, idx;
pii a[N];
vc<pii> ans;
set<pii> S;
map<int, int> A, B;
bool vis[N];
int deg[N];
vc<int> G[N];
inline void add(int x, int y) {
++deg[x]; ++deg[y];
G[x].pb(y); G[y].pb(x);
}
inline void dfs(int x, int fl, int fa, int rt) {
int ed = 0; vis[x] = 1;
for(auto y:G[x]) if(y != fa) {
if(!vis[y]) dfs(y, fl ^ 1, x, rt);
else if(y == rt) ed = 1;
}
if(fl && !ed) ans.pb(a[x]);
}
signed main() {
n = read(), m = read();
for(int i = 1; i <= n; i++) {
if(i == 1 || i == n) {
for(int j = 1; j <= m; j++) S.insert(mkp(i,j));
}
else S.insert(mkp(i, 1)), S.insert(mkp(i, m));
}
for(auto u: S) {
a[++idx] = u;
auto [x, y] = u;
if(A[x + y]) add(A[x + y], idx);
if(B[x - y]) add(B[x - y], idx);
A[x + y] = B[x - y] = idx;
}
for(int i = 1; i <= idx; i++) if(!vis[i] && deg[i] == 1) dfs(i, 1, 0, i);
for(int i = 1; i <= idx; i++) if(!vis[i]) dfs(i, 1, 0, i);
writee(ans.size());
for(auto u:ans) writec(u.first), writee(u.second);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 17800kb
input:
2 5
output:
6 1 5 1 3 1 1 2 5 2 3 2 1
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 0ms
memory: 18264kb
input:
5 5
output:
8 1 1 1 5 5 4 1 2 5 3 1 3 5 2 1 4
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 311ms
memory: 72372kb
input:
100000 100000
output:
199998 1 1 1 100000 100000 99999 1 2 100000 99998 1 3 100000 99997 1 4 100000 99996 1 5 100000 99995 1 6 100000 99994 1 7 100000 99993 1 8 100000 99992 1 9 100000 99991 1 10 100000 99990 1 11 100000 99989 1 12 100000 99988 1 13 100000 99987 1 14 100000 99986 1 15 100000 99985 1 16 100000 99984 1 17 ...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 317ms
memory: 81388kb
input:
100000 99999
output:
199998 1 99999 100000 2 1 99997 100000 4 1 99995 100000 6 1 99993 100000 8 1 99991 100000 10 1 99989 100000 12 1 99987 100000 14 1 99985 100000 16 1 99983 100000 18 1 99981 100000 20 1 99979 100000 22 1 99977 100000 24 1 99975 100000 26 1 99973 100000 28 1 99971 100000 30 1 99969 100000 32 1 99967 1...
result:
ok n: 100000, m: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 241ms
memory: 66328kb
input:
100000 50000
output:
149998 50001 1 1 49999 99998 50000 50003 1 1 49997 99996 50000 50005 1 1 49995 99994 50000 50007 1 1 49993 99992 50000 50009 1 1 49991 99990 50000 50011 1 1 49989 99988 50000 50013 1 1 49987 99986 50000 50015 1 1 49985 99984 50000 50017 1 1 49983 99982 50000 50019 1 1 49981 99980 50000 50021 1 1 499...
result:
ok n: 100000, m: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 65ms
memory: 34488kb
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: 226ms
memory: 62364kb
input:
34535 99889
output:
134423 1 99889 1 30821 34535 3715 34535 72783 1 92461 1 23393 34535 11143 34535 80211 1 85033 1 15965 34535 18571 34535 87639 1 77605 1 8537 34535 25999 34535 95067 1 70177 1 1109 34535 33427 31929 99889 1 62749 6321 1 34535 40855 24501 99889 1 55321 13749 1 34535 48283 17073 99889 1 47893 21177 1 3...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 191ms
memory: 54236kb
input:
12231 97889
output:
110119 1 97889 1 73429 1 48969 1 24509 1 49 12231 12183 12231 36643 12231 61103 12231 85563 97 97889 1 73525 1 49065 1 24605 1 145 12231 12087 12231 36547 12231 61007 12231 85467 193 97889 1 73621 1 49161 1 24701 1 241 12231 11991 12231 36451 12231 60911 12231 85371 289 97889 1 73717 1 49257 1 24797...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 188ms
memory: 50216kb
input:
10000 100000
output:
109998 1 90001 1 70003 1 50005 1 30007 1 10009 9991 1 10000 19990 10000 39988 10000 59986 10000 79984 10000 99982 1 90019 1 70021 1 50023 1 30025 1 10027 9973 1 10000 19972 10000 39970 10000 59968 10000 79966 10000 99964 1 90037 1 70039 1 50041 1 30043 1 10045 9955 1 10000 19954 10000 39952 10000 59...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 175ms
memory: 50540kb
input:
13 99999
output:
100011 13 1 13 25 13 49 13 73 13 97 13 121 13 145 13 169 13 193 13 217 13 241 13 265 13 289 13 313 13 337 13 361 13 385 13 409 13 433 13 457 13 481 13 505 13 529 13 553 13 577 13 601 13 625 13 649 13 673 13 697 13 721 13 745 13 769 13 793 13 817 13 841 13 865 13 889 13 913 13 937 13 961 13 985 13 10...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 161ms
memory: 49780kb
input:
21 99999
output:
100019 21 1 21 41 21 81 21 121 21 161 21 201 21 241 21 281 21 321 21 361 21 401 21 441 21 481 21 521 21 561 21 601 21 641 21 681 21 721 21 761 21 801 21 841 21 881 21 921 21 961 21 1001 21 1041 21 1081 21 1121 21 1161 21 1201 21 1241 21 1281 21 1321 21 1361 21 1401 21 1441 21 1481 21 1521 21 1561 21...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 247ms
memory: 63504kb
input:
49999 100000
output:
149998 49999 1 49999 99997 1 50005 49993 1 49999 99991 1 50011 49987 1 49999 99985 1 50017 49981 1 49999 99979 1 50023 49975 1 49999 99973 1 50029 49969 1 49999 99967 1 50035 49963 1 49999 99961 1 50041 49957 1 49999 99955 1 50047 49951 1 49999 99949 1 50053 49945 1 49999 99943 1 50059 49939 1 49999...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 205ms
memory: 60952kb
input:
33333 99999
output:
133331 33333 1 33333 66665 3 99999 1 33337 33329 1 33333 66661 7 99999 1 33341 33325 1 33333 66657 11 99999 1 33345 33321 1 33333 66653 15 99999 1 33349 33317 1 33333 66649 19 99999 1 33353 33313 1 33333 66645 23 99999 1 33357 33309 1 33333 66641 27 99999 1 33361 33305 1 33333 66637 31 99999 1 33365...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 224ms
memory: 57204kb
input:
23342 98876
output:
122216 1 75535 1 28853 17831 1 23342 41172 23342 87854 1 86557 1 39875 6809 1 23342 30150 23342 76832 1 97579 1 50897 1 4215 23342 19128 23342 65810 9726 98876 1 61919 1 15237 23342 8106 23342 54788 20748 98876 1 72941 1 26259 20425 1 23342 43766 23342 90448 1 83963 1 37281 9403 1 23342 32744 23342 ...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 256ms
memory: 63368kb
input:
56713 91234
output:
147946 56713 1 34522 91234 1 12331 56713 44383 1 81373 32053 1 56713 88765 1 36991 56713 19723 14800 91234 7393 1 56713 64105 1 61651 51775 1 39460 91234 1 17269 56713 39445 1 86311 27115 1 56713 83827 1 41929 56713 14785 19738 91234 2455 1 56713 59167 1 66589 46837 1 44398 91234 1 22207 56713 34507...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 311ms
memory: 72392kb
input:
99995 99995
output:
199988 1 1 1 99995 99995 99994 1 2 99995 99993 1 3 99995 99992 1 4 99995 99991 1 5 99995 99990 1 6 99995 99989 1 7 99995 99988 1 8 99995 99987 1 9 99995 99986 1 10 99995 99985 1 11 99995 99984 1 12 99995 99983 1 13 99995 99982 1 14 99995 99981 1 15 99995 99980 1 16 99995 99979 1 17 99995 99978 1 18 ...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 99ms
memory: 37996kb
input:
12345 54321
output:
66665 1 54321 1 29633 1 4945 12345 7401 12345 32089 9889 54321 1 39521 1 14833 9857 1 12345 22201 12345 46889 1 49409 1 24721 1 33 12345 12313 12345 37001 4977 54321 1 34609 1 9921 12345 2425 12345 27113 12345 51801 1 44497 1 19809 4881 1 12345 17225 12345 41913 65 54321 1 29697 1 5009 12345 7337 12...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 314ms
memory: 75224kb
input:
90000 92000
output:
181998 1 2001 90000 88000 1 6001 90000 84000 1 10001 90000 80000 1 14001 90000 76000 1 18001 90000 72000 1 22001 90000 68000 1 26001 90000 64000 1 30001 90000 60000 1 34001 90000 56000 1 38001 90000 52000 1 42001 90000 48000 1 46001 90000 44000 1 50001 90000 40000 1 54001 90000 36000 1 58001 90000 3...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 117ms
memory: 43288kb
input:
10000 70000
output:
79998 1 60001 1 40003 1 20005 1 7 10000 9994 10000 29992 10000 49990 10000 69988 1 60013 1 40015 1 20017 1 19 10000 9982 10000 29980 10000 49978 10000 69976 1 60025 1 40027 1 20029 1 31 10000 9970 10000 29968 10000 49966 10000 69964 1 60037 1 40039 1 20041 1 43 10000 9958 10000 29956 10000 49954 100...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 118ms
memory: 42928kb
input:
10000 70001
output:
80000 1 70001 1 50003 1 30005 1 10007 9993 1 10000 19992 10000 39990 10000 59988 15 70001 1 50017 1 30019 1 10021 9979 1 10000 19978 10000 39976 10000 59974 29 70001 1 50031 1 30033 1 10035 9965 1 10000 19964 10000 39962 10000 59960 43 70001 1 50045 1 30047 1 10049 9951 1 10000 19950 10000 39948 100...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 135ms
memory: 46780kb
input:
10000 80000
output:
89998 1 70001 1 50003 1 30005 1 10007 9993 1 10000 19992 10000 39990 10000 59988 10000 79986 1 70015 1 50017 1 30019 1 10021 9979 1 10000 19978 10000 39976 10000 59974 10000 79972 1 70029 1 50031 1 30033 1 10035 9965 1 10000 19964 10000 39962 10000 59960 10000 79958 1 70043 1 50045 1 30047 1 10049 9...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 142ms
memory: 47736kb
input:
10000 80001
output:
90000 1 80001 1 60003 1 40005 1 20007 1 9 10000 9992 10000 29990 10000 49988 10000 69986 17 80001 1 60019 1 40021 1 20023 1 25 10000 9976 10000 29974 10000 49972 10000 69970 33 80001 1 60035 1 40037 1 20039 1 41 10000 9960 10000 29958 10000 49956 10000 69954 49 80001 1 60051 1 40053 1 20055 1 57 100...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 137ms
memory: 44036kb
input:
10000 80002
output:
90000 1 70003 1 50005 1 30007 1 10009 9991 1 10000 19990 10000 39988 10000 59986 10000 79984 1 70021 1 50023 1 30025 1 10027 9973 1 10000 19972 10000 39970 10000 59968 10000 79966 1 70039 1 50041 1 30043 1 10045 9955 1 10000 19954 10000 39952 10000 59950 10000 79948 1 70057 1 50059 1 30061 1 10063 9...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 135ms
memory: 46200kb
input:
10000 79999
output:
89998 1 79999 1 60001 1 40003 1 20005 1 7 10000 9994 10000 29992 10000 49990 10000 69988 13 79999 1 60013 1 40015 1 20017 1 19 10000 9982 10000 29980 10000 49978 10000 69976 25 79999 1 60025 1 40027 1 20029 1 31 10000 9970 10000 29968 10000 49966 10000 69964 37 79999 1 60037 1 40039 1 20041 1 43 100...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 126ms
memory: 47548kb
input:
10000 79998
output:
89996 1 69999 1 50001 1 30003 1 10005 9995 1 10000 19994 10000 39992 10000 59990 10000 79988 1 70009 1 50011 1 30013 1 10015 9985 1 10000 19984 10000 39982 10000 59980 10000 79978 1 70019 1 50021 1 30023 1 10025 9975 1 10000 19974 10000 39972 10000 59970 10000 79968 1 70029 1 50031 1 30033 1 10035 9...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 188ms
memory: 53452kb
input:
11111 100000
output:
111110 11111 1 11111 22221 11111 44441 11111 66661 11111 88881 10 100000 1 77789 1 55569 1 33349 1 11129 11093 1 11111 22203 11111 44423 11111 66643 11111 88863 28 100000 1 77807 1 55587 1 33367 1 11147 11075 1 11111 22185 11111 44405 11111 66625 11111 88845 46 100000 1 77825 1 55605 1 33385 1 11165...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 1ms
memory: 17320kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed