QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#440161 | #7178. Bishops | 0x3b800001 | AC ✓ | 1184ms | 65000kb | C++14 | 2.6kb | 2024-06-13 10:49:28 | 2024-06-13 10:49:30 |
Judging History
answer
#include <iostream>
#include <queue>
namespace MF {
int n, s, t;
struct Edge {
int u, v, c, nxt;
} edges[20000007];
int ecnt;
int head[1000007];
void _addedge(int u, int v, int c) {
edges[ecnt].u = u, edges[ecnt].v = v, edges[ecnt].c = c;
edges[ecnt].nxt = head[u], head[u] = ecnt, ++ecnt;
}
void addedge(int u, int v, int c) { _addedge(u, v, c), _addedge(v, u, 0); }
int dis[1000007];
int cur[1000007];
bool BFS() {
for (int i = 1; i <= n; ++i) {
dis[i] = +0x3b9aca00;
cur[i] = head[i];
}
std::queue<int> q;
dis[s] = 0, q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int e = head[u]; e != -1; e = edges[e].nxt) {
if (edges[e].c != 0 && dis[u] + 1 < dis[edges[e].v]) {
dis[edges[e].v] = dis[u] + 1, q.push(edges[e].v);
}
}
}
return dis[t] != +0x3b9aca00;
}
int sF;
int dfs(int u, int fl) {
if (u == t) {
sF += fl;
return fl;
}
int rf = fl;
for (int& e = cur[u]; e != -1; e = edges[e].nxt) {
if (edges[e].c != 0 && dis[edges[e].v] == dis[u] + 1) {
int f = dfs(edges[e].v, std::min(fl, edges[e].c));
fl -= f, edges[e].c -= f, edges[e ^ 1].c += f;
if (fl == 0) {
return rf;
}
}
}
return rf - fl;
}
void init(int _n, int _s, int _t) {
n = _n, s = _s, t = _t;
for (int i = 1; i <= n; ++i) {
head[i] = -1;
}
}
int Dinic() {
while (BFS()) {
dfs(s, +0x3b9aca00);
}
return sF;
}
};
int n, m;
int main() {
// std::freopen("bishop.in", "r", stdin);
// std::freopen("bishop.out", "w", stdout);
std::cin.tie(nullptr)->sync_with_stdio(false);
std::cin >> n >> m;
MF::init(n + n + m + m, 1, n + n + m + m);
for (int i = 2; i <= n + m; ++i) {
MF::addedge(1, i, 1);
MF::addedge(i + n + m - 1, n + n + m + m, 1);
}
for (int i : std::vector<int>{1, 2, n - 1, n}) {
if (1 <= i && i <= n) {
for (int j = 1; j <= m; ++j) {
MF::addedge(i + j, i - j + n + m + m, 1);
}
}
}
for (int j : std::vector<int>{1, 2, m - 1, m}) {
if (1 <= j && j <= m) {
for (int i = 3; i <= n - 2; ++i) {
MF::addedge(i + j, i - j + n + m + m, 1);
}
}
}
std::cout << MF::Dinic() << '\n';
for (int i = 0; i < MF::ecnt; ++i) {
if (MF::edges[i].c == 0 && 2 <= MF::edges[i].u && MF::edges[i].u <= n + m && n + m + 1 <= MF::edges[i].v && MF::edges[i].v <= n + n + m + m - 1) {
int P = MF::edges[i].u, M = MF::edges[i].v - n - m - m;
std::cout << (P + M) / 2 << ' ' << (P - M) / 2 << '\n';
}
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 7940kb
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: 2ms
memory: 7940kb
input:
5 5
output:
8 1 2 2 5 4 1 5 1 5 4 5 5 3 1 3 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 64ms
memory: 59756kb
input:
100000 100000
output:
199998 1 2 1 99999 100000 1 100000 2 100000 99999 100000 100000 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 ...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 128ms
memory: 65000kb
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: 112ms
memory: 46340kb
input:
100000 50000
output:
149998 1 2 1 3 1 10 1 11 1 18 1 19 1 26 1 27 1 34 1 35 1 42 1 43 1 50 1 51 1 58 1 59 1 66 1 67 1 74 1 75 1 82 1 83 1 90 1 91 1 98 1 99 1 106 1 107 1 114 1 115 1 122 1 123 1 130 1 131 1 138 1 139 1 146 1 147 1 154 1 155 1 162 1 163 1 170 1 171 1 178 1 179 1 186 1 187 1 194 1 195 1 202 1 203 1 210 1 2...
result:
ok n: 100000, m: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 20ms
memory: 23088kb
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: 1184ms
memory: 39056kb
input:
34535 99889
output:
134423 1 1 1 2 1 3 1 289 1 290 1 291 1 292 1 295 1 296 1 297 1 298 1 303 1 304 1 305 1 306 1 311 1 312 1 313 1 314 1 319 1 320 1 321 1 322 1 327 1 328 1 329 1 330 1 335 1 336 1 397 1 398 1 401 1 402 1 403 1 404 1 409 1 410 1 411 1 412 1 417 1 418 1 419 1 420 1 425 1 426 1 427 1 428 1 433 1 434 1 435...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 590ms
memory: 35864kb
input:
12231 97889
output:
110119 1 1 1 2 1 3 1 97889 2 56 2 57 2 58 2 59 2 60 2 61 2 62 2 63 2 64 2 65 2 66 2 67 2 68 2 69 2 70 2 71 2 72 2 73 2 74 2 75 2 76 2 77 2 78 2 79 2 80 2 81 2 82 2 83 2 84 2 85 2 86 2 87 2 88 2 89 2 90 2 91 2 92 2 93 2 94 2 95 2 96 2 97 2 98 2 99 2 100 2 101 2 102 2 103 2 104 2 105 2 106 2 107 2 108...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 413ms
memory: 35736kb
input:
10000 100000
output:
109998 1 49992 1 49993 1 69988 1 69989 1 69990 1 69991 1 89984 1 89985 1 89986 1 89987 1 89988 1 89989 1 100000 2 1 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 35 2 36 2 37 2 38 2 49 2 50 2 51 2 52 2 53 2 54 2 55 2 56 2 57 2 58 2 65 2 66 2 67 2 68 2 69 2 70 2 73...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 108ms
memory: 29372kb
input:
13 99999
output:
100011 1 1 1 2 1 15 1 17 1 19 1 21 1 23 1 25 1 39 1 41 1 43 1 45 1 47 1 49 1 63 1 65 1 67 1 69 1 71 1 73 1 87 1 89 1 91 1 93 1 95 1 97 1 111 1 113 1 115 1 117 1 119 1 121 1 135 1 137 1 139 1 141 1 143 1 145 1 158 1 159 1 161 1 163 1 165 1 167 1 169 1 182 1 183 1 185 1 187 1 189 1 191 1 193 1 206 1 2...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 110ms
memory: 29336kb
input:
21 99999
output:
100019 1 1 1 2 1 3 1 118 1 119 1 158 1 159 1 198 1 199 1 238 1 239 1 278 1 279 1 318 1 319 1 358 1 359 1 361 1 362 1 398 1 399 1 401 1 402 1 420 1 438 1 439 1 441 1 442 1 444 1 446 1 448 1 450 1 452 1 454 1 456 1 460 1 478 1 479 1 481 1 482 1 483 1 484 1 485 1 486 1 487 1 488 1 489 1 490 1 491 1 492...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 179ms
memory: 42056kb
input:
49999 100000
output:
149998 1 1 1 100000 2 1 2 5 2 6 2 7 2 8 2 9 2 13 2 14 2 15 2 16 2 17 2 22 2 23 2 25 2 26 2 27 2 28 2 29 2 34 2 35 2 37 2 38 2 39 2 40 2 41 2 46 2 47 2 49 2 50 2 51 2 52 2 53 2 58 2 59 2 61 2 62 2 63 2 64 2 65 2 70 2 71 2 73 2 74 2 75 2 76 2 77 2 82 2 83 2 85 2 86 2 87 2 88 2 89 2 94 2 95 2 97 2 98 2...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 65ms
memory: 39304kb
input:
33333 99999
output:
133331 1 1 1 4 1 33335 1 33337 1 33338 1 33339 1 33340 1 33341 1 33342 1 33343 1 33344 1 33345 1 33346 1 33347 1 33348 1 33349 1 33350 1 33351 1 33352 1 33353 1 33354 1 33355 1 33356 1 33357 1 33358 1 33359 1 33360 1 33361 1 33362 1 33363 1 33364 1 33365 1 33366 1 33367 1 33368 1 33369 1 33370 1 333...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 762ms
memory: 36596kb
input:
23342 98876
output:
122216 1 2 1 352 1 353 1 360 1 361 1 362 1 363 1 370 1 371 1 372 1 373 1 380 1 381 1 382 1 383 1 384 1 385 1 386 1 387 1 388 1 389 1 390 1 391 1 392 1 393 1 394 1 395 1 396 1 397 1 398 1 399 1 400 1 401 1 402 1 403 1 404 1 405 1 406 1 407 1 408 1 409 1 410 1 411 1 412 1 413 1 414 1 415 1 416 1 417 1...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 473ms
memory: 39824kb
input:
56713 91234
output:
147946 1 1 1 2 1 3 1 2467 1 2468 1 2474 1 2475 1 2476 1 2477 1 2478 1 2479 1 2480 1 2481 1 2482 1 2483 1 2484 1 2485 1 2486 1 2487 1 2488 1 2489 1 2490 1 2491 1 2492 1 2493 1 2494 1 2495 1 2496 1 2497 1 2498 1 2499 1 2500 1 2501 1 2502 1 2503 1 2504 1 2505 1 2506 1 2507 1 2508 1 2509 1 2510 1 2511 1...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 85ms
memory: 57292kb
input:
99995 99995
output:
199988 1 2 1 99994 99995 1 99995 2 99995 99994 99995 99995 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 ...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 417ms
memory: 22924kb
input:
12345 54321
output:
66665 1 1 1 41 1 42 1 43 1 44 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61 1 62 1 63 1 64 1 65 1 66 1 69 1 70 1 71 1 72 1 5055 1 5056 1 5059 1 5060 1 5061 1 5062 1 5063 1 5064 1 5065 1 5066 1 5067 1 5068 1 5069 1 5070 1 5071 1 5072 1 5073 1 5074 1 17243 1 17244 1 24729 1 24730 1 24737 1 24...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 187ms
memory: 49120kb
input:
90000 92000
output:
181998 1 1 1 2 1 3 1 91999 1 92000 2 47 2 48 2 49 2 50 2 51 2 52 2 53 2 54 2 55 2 56 2 57 2 58 2 59 2 60 2 61 2 62 2 63 2 64 2 65 2 66 2 67 2 68 2 69 2 70 2 71 2 72 2 73 2 74 2 75 2 76 2 77 2 78 2 79 2 80 2 81 2 82 2 83 2 84 2 85 2 86 2 87 2 88 2 89 2 90 2 91 2 92 2 93 2 94 2 95 2 96 2 97 2 98 2 99 ...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 84ms
memory: 25232kb
input:
10000 70000
output:
79998 1 1 1 2 1 3 1 10005 1 10006 1 10008 1 10009 1 10010 1 10011 1 10012 1 10013 1 10014 1 10015 1 10016 1 10017 1 10018 1 10019 1 10020 1 10021 1 10022 1 10023 1 10024 1 10025 1 10027 1 10028 1 10030 1 10031 1 10032 1 10033 1 10034 1 10035 1 10036 1 10037 1 10038 1 10039 1 10040 1 10041 1 10042 1 ...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 164ms
memory: 25472kb
input:
10000 70001
output:
80000 1 1 1 2 1 3 1 10006 1 10007 1 10009 1 10010 1 10011 1 10012 1 10013 1 10014 1 10015 1 10016 1 10017 1 10018 1 10019 1 10020 1 10021 1 10022 1 10024 1 10025 1 10026 1 10027 1 10028 1 10029 1 10030 1 10031 1 10033 1 10034 1 10035 1 10036 1 10037 1 10040 1 10041 1 10042 1 10044 1 10045 1 10046 1 ...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 282ms
memory: 26840kb
input:
10000 80000
output:
89998 1 29998 1 29999 1 49994 1 49995 1 49996 1 49997 1 69990 1 69991 1 69992 1 69993 1 69994 1 69995 1 80000 2 1 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 35 2 36 2 37 2 38 2 39 2 40 2 41 2 42 2 53 2 54 2 55 2 56 2 57 2 58 2 59 2 60 2 61 2 62 2 63 2 64 2 66 2...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 355ms
memory: 31512kb
input:
10000 80001
output:
90000 1 1 1 69997 1 69998 1 80001 2 1 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 35 2 36 2 37 2 38 2 39 2 40 2 41 2 42 2 56 2 57 2 59 2 60 2 61 2 62 2 63 2 66 2 67 2 68 2 69 2 70 2 71 2 72 2 73 2 74 2 75 2 76 2 77 2 78 2 79 2 80 2 81 2 82 2 96 2 97 2 99 2 100 2...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 289ms
memory: 27512kb
input:
10000 80002
output:
90000 1 49998 1 49999 1 69994 1 69995 1 69996 1 69997 1 80002 2 1 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 33 2 34 2 39 2 40 2 41 2 42 2 43 2 44 2 45 2 46 2 59 2 60 2 61 2 62 2 63 2 64 2 65 2 66 2 67 2 68 2 70 2 71 2 75 2 76 2 77 2 78 2 79 2 80 2 81 2 82 2 83...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 308ms
memory: 28376kb
input:
10000 79999
output:
89998 1 1 1 79999 2 1 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 27 2 28 2 29 2 30 2 31 2 32 2 45 2 46 2 47 2 49 2 50 2 52 2 53 2 54 2 55 2 56 2 57 2 58 2 59 2 60 2 61 2 62 2 63 2 64 2 65 2 66 2 67 2 68 2 81 2 82 2 83 2 85 2 86 2 88 2 89 2 90 2 91 2 92 2 93 2 94 2 95 2 96 2 9...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 249ms
memory: 28800kb
input:
10000 79998
output:
89996 1 29998 1 29999 1 49994 1 49995 1 49996 1 49997 1 69990 1 69991 1 69992 1 69993 1 69994 1 69995 1 79998 2 1 2 13 2 14 2 15 2 16 2 17 2 18 2 19 2 20 2 21 2 22 2 23 2 24 2 25 2 26 2 29 2 30 2 31 2 32 2 33 2 34 2 35 2 36 2 47 2 48 2 49 2 50 2 51 2 52 2 53 2 54 2 55 2 56 2 58 2 59 2 61 2 62 2 63 2...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 234ms
memory: 31772kb
input:
11111 100000
output:
111110 1 1 1 2 1 3 1 11119 1 11120 1 11122 1 11123 1 11124 1 11125 1 11126 1 11127 1 11128 1 11129 1 11130 1 11131 1 11132 1 11133 1 11134 1 11135 1 11136 1 11137 1 11138 1 11139 1 11140 1 11141 1 11145 1 11146 1 11147 1 11148 1 11150 1 11151 1 11154 1 11155 1 11156 1 11157 1 11158 1 11159 1 11160 1...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 2ms
memory: 7652kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed