QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#440155#7178. Bishops0x3b800001TL 95ms61704kbC++142.4kb2024-06-13 10:41:332024-06-13 10:41:33

Judging History

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

  • [2024-06-13 10:41:33]
  • 评测
  • 测评结果:TL
  • 用时:95ms
  • 内存:61704kb
  • [2024-06-13 10:41:33]
  • 提交

answer

#include <iostream>
#include <queue>

namespace MF {
int n, s, t;
struct Edge {
  int u, v, c, nxt;
} edges[10000007];
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;
    }
  }
  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::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 = 1; i <= n; ++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;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 7948kb

input:

2 5

output:

6
1 3
2 3
1 1
2 1
1 5
2 5

result:

ok n: 2, m: 5, bishops: 6

Test #2:

score: 0
Accepted
time: 1ms
memory: 7720kb

input:

5 5

output:

8
2 1
3 1
4 1
1 5
2 5
3 5
4 5
5 5

result:

ok n: 5, m: 5, bishops: 8

Test #3:

score: 0
Accepted
time: 67ms
memory: 55540kb

input:

100000 100000

output:

199998
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
61 1
6...

result:

ok n: 100000, m: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 95ms
memory: 61704kb

input:

100000 99999

output:

199998
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 61
1 62
...

result:

ok n: 100000, m: 99999, bishops: 199998

Test #5:

score: 0
Accepted
time: 73ms
memory: 41284kb

input:

100000 50000

output:

149998
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 211
1...

result:

ok n: 100000, m: 50000, bishops: 149998

Test #6:

score: 0
Accepted
time: 11ms
memory: 22404kb

input:

1 100000

output:

100000
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 61
1 62
...

result:

ok n: 1, m: 100000, bishops: 100000

Test #7:

score: -100
Time Limit Exceeded

input:

34535 99889

output:


result: