QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#440161#7178. Bishops0x3b800001AC ✓1184ms65000kbC++142.6kb2024-06-13 10:49:282024-06-13 10:49:30

Judging History

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

  • [2024-06-13 10:49:30]
  • 评测
  • 测评结果:AC
  • 用时:1184ms
  • 内存:65000kb
  • [2024-06-13 10:49:28]
  • 提交

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,我给组数据试试?

詳細信息

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