QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#167698#7178. Bishopsucup-team045#AC ✓136ms51728kbC++203.3kb2023-09-07 16:40:262023-09-07 16:40:27

Judging History

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

  • [2023-09-07 16:40:27]
  • 评测
  • 测评结果:AC
  • 用时:136ms
  • 内存:51728kb
  • [2023-09-07 16:40:26]
  • 提交

answer

#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<limits>
using namespace std;
using LL = long long;

const int maxn = 1e6 + 5, maxm = 2e6 + 5;
template<typename flow_t>
struct MaxFlow{

    const flow_t INF = numeric_limits<flow_t>::max() / 2;

    int h[maxn], e[maxm], ne[maxm], idx;
    flow_t f[maxm];
    int cur[maxn], q[maxn], d[maxn];
    int V, S, T;

    void init(int v, int s, int t){
        for(int i = 0; i <= v; i++) h[i] = -1;
        idx = 0;
        V = v, S = s, T = t;
    }
    
    void add(int a, int b, flow_t c, flow_t d = 0){
        e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
        e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx++;
    }
    
    bool bfs(){
        for(int i = 0; i <= V; i++) d[i] = -1;
        int hh = 0, tt = -1;
        q[++tt] = S, d[S] = 0, cur[S] = h[S];
        while(hh <= tt){
            int t = q[hh++];
            for(int i = h[t]; ~i; i = ne[i]){
                int j = e[i];
                if (d[j] == -1 && f[i]){
                    d[j] = d[t] + 1;
                    cur[j] = h[j];
                    if (j == T) return true;
                    q[++tt] = j;
                }
            }
        }
        return false;
    }
    
    flow_t find(int u, flow_t limit){
        if (u == T) return limit;
        flow_t flow = 0;
        // start from cur[u] instead of h[u] <- important
        for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
            int j = e[i];
            cur[u] = i;
            if (d[j] == d[u] + 1 && f[i]){
                flow_t t = find(j, min(f[i], limit - flow));
                if (!t) d[j] = -1;
                else f[i] -= t, f[i ^ 1] += t, flow += t; 
            }
        }
        return flow;
    }
    
    flow_t dinic(){
        flow_t res = 0, flow;
        while(bfs()) while(flow = find(S, INF)) res += flow;
        return res;
    }
};

MaxFlow<int> flow;
int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    
    const int cnt = n + m - 1;
    int s = 0, t = 2 * cnt + 1;
    flow.init(2 * cnt + 1, s, t);
    for(int i = 1; i <= cnt; i++){
        flow.add(s, i, 1);
        flow.add(i + cnt, t, 1);
    }

    auto add = [&](int x, int y){
        int l = x + y - 1;
        int r = m - y + 1 + x - 1;
        flow.add(l, r + cnt, 1);
    };

    for(int i = 1; i <= m; i++){
        add(1, i);
        add(n, i);
    }
    for(int i = 2; i <= n - 1; i++){
        add(i, 1);
        add(i, m);
    }
    flow.dinic();

    auto get = [&](int x, int y){
        int s1 = x + 1;
        int s2 = y - m;
        x = (s1 + s2) / 2;
        y = s1 - x;
        return make_pair(x, y);
    };

    vector<pair<int, int> > ans;
    for(int x = 1; x <= cnt; x++){
        for(int i = flow.h[x]; ~i; i = flow.ne[i]){
            int j = flow.e[i];
            if (j > cnt && j <= 2 * cnt && !flow.f[i]){
                ans.push_back(get(x, j - cnt));
            }
        }
    }
    cout << ans.size() << '\n';
    for(auto [x, y] : ans)
        cout << x << ' ' << y << '\n';

}

这程序好像有点Bug,我给组数据试试?

详细

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

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: 32ms
memory: 41544kb

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: 39ms
memory: 51728kb

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: 19ms
memory: 39008kb

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: 19ms
memory: 28948kb

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: 136ms
memory: 41728kb

input:

34535 99889

output:

134423
1 1
1 2
1 3
4 1
5 1
1 6
1 7
8 1
9 1
1 10
11 1
12 1
1 13
1 14
15 1
16 1
1 17
1 18
1 19
20 1
21 1
1 22
1 23
24 1
25 1
1 26
1 27
28 1
1 29
1 30
31 1
32 1
1 33
1 34
35 1
36 1
37 1
1 38
1 39
40 1
41 1
1 42
1 43
44 1
45 1
1 46
47 1
48 1
1 49
1 50
51 1
52 1
1 53
1 54
1 55
56 1
57 1
1 58
1 59
60 1
61...

result:

ok n: 34535, m: 99889, bishops: 134423

Test #8:

score: 0
Accepted
time: 97ms
memory: 31820kb

input:

12231 97889

output:

110119
1 1
1 2
1 3
4 1
5 1
1 6
1 7
8 1
9 1
1 10
11 1
12 1
1 13
1 14
15 1
16 1
1 17
1 18
19 1
20 1
21 1
1 22
1 23
24 1
25 1
1 26
1 27
28 1
29 1
1 30
31 1
32 1
1 33
1 34
35 1
36 1
1 37
1 38
39 1
40 1
41 1
1 42
1 43
44 1
45 1
1 46
1 47
48 1
1 49
1 50
51 1
52 1
1 53
1 54
55 1
56 1
1 57
1 58
1 59
60 1
61...

result:

ok n: 12231, m: 97889, bishops: 110119

Test #9:

score: 0
Accepted
time: 29ms
memory: 30144kb

input:

10000 100000

output:

109998
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
56 1
57 1
58 1
59 1
60 1
61 1
6...

result:

ok n: 10000, m: 100000, bishops: 109998

Test #10:

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

input:

13 99999

output:

100011
1 1
2 1
3 1
1 4
5 1
6 1
7 1
1 8
9 1
10 1
11 1
1 12
13 1
13 2
1 15
1 16
1 17
13 6
1 19
1 20
1 21
13 10
1 23
1 24
1 25
13 14
13 15
1 28
13 17
13 18
13 19
1 32
13 21
13 22
13 23
1 36
13 25
13 26
1 39
1 40
1 41
13 30
1 43
1 44
1 45
13 34
1 47
1 48
1 49
13 38
13 39
1 52
13 41
13 42
13 43
1 56
13 4...

result:

ok n: 13, m: 99999, bishops: 100011

Test #11:

score: 0
Accepted
time: 39ms
memory: 31684kb

input:

21 99999

output:

100019
1 1
2 1
3 1
1 4
1 5
6 1
7 1
1 8
1 9
10 1
11 1
1 12
1 13
14 1
15 1
1 16
1 17
18 1
19 1
1 20
21 1
21 2
1 23
1 24
21 5
21 6
1 27
1 28
21 9
21 10
1 31
1 32
21 13
21 14
1 35
1 36
21 17
21 18
1 39
1 40
1 41
21 22
21 23
1 44
1 45
21 26
21 27
1 48
1 49
21 30
21 31
1 52
1 53
21 34
21 35
1 56
1 57
21 3...

result:

ok n: 21, m: 99999, bishops: 100019

Test #12:

score: 0
Accepted
time: 30ms
memory: 36544kb

input:

49999 100000

output:

149998
1 1
1 2
1 3
1 4
5 1
6 1
7 1
1 8
1 9
1 10
11 1
12 1
13 1
1 14
1 15
1 16
17 1
18 1
19 1
1 20
1 21
1 22
23 1
24 1
25 1
1 26
1 27
1 28
29 1
30 1
31 1
1 32
1 33
1 34
35 1
36 1
37 1
1 38
1 39
1 40
41 1
42 1
43 1
1 44
1 45
1 46
47 1
48 1
49 1
1 50
1 51
1 52
53 1
54 1
55 1
1 56
1 57
1 58
59 1
60 1
61...

result:

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

Test #13:

score: 0
Accepted
time: 25ms
memory: 35812kb

input:

33333 99999

output:

133331
1 1
2 1
3 1
1 4
5 1
6 1
7 1
1 8
9 1
10 1
11 1
1 12
13 1
14 1
15 1
1 16
17 1
18 1
19 1
1 20
21 1
22 1
23 1
1 24
25 1
26 1
27 1
1 28
29 1
30 1
31 1
1 32
33 1
34 1
35 1
1 36
37 1
38 1
39 1
1 40
41 1
42 1
43 1
1 44
45 1
46 1
47 1
1 48
49 1
50 1
51 1
1 52
53 1
54 1
55 1
1 56
57 1
58 1
59 1
1 60
61...

result:

ok n: 33333, m: 99999, bishops: 133331

Test #14:

score: 0
Accepted
time: 77ms
memory: 34948kb

input:

23342 98876

output:

122216
1 1
1 2
1 3
4 1
5 1
6 1
1 7
1 8
9 1
10 1
11 1
1 12
1 13
14 1
15 1
16 1
1 17
1 18
19 1
20 1
21 1
1 22
1 23
24 1
25 1
26 1
1 27
1 28
29 1
30 1
31 1
1 32
1 33
34 1
35 1
36 1
1 37
1 38
39 1
40 1
41 1
1 42
1 43
44 1
45 1
46 1
1 47
1 48
49 1
50 1
51 1
1 52
1 53
54 1
55 1
56 1
1 57
1 58
59 1
60 1
61...

result:

ok n: 23342, m: 98876, bishops: 122216

Test #15:

score: 0
Accepted
time: 106ms
memory: 34252kb

input:

56713 91234

output:

147946
1 1
2 1
3 1
1 4
1 5
1 6
1 7
8 1
9 1
10 1
1 11
1 12
13 1
14 1
15 1
16 1
1 17
1 18
1 19
20 1
21 1
1 22
1 23
1 24
25 1
26 1
27 1
28 1
1 29
1 30
31 1
32 1
33 1
1 34
1 35
1 36
1 37
38 1
39 1
40 1
1 41
1 42
43 1
44 1
45 1
46 1
1 47
1 48
1 49
50 1
51 1
1 52
1 53
1 54
55 1
56 1
57 1
58 1
1 59
1 60
61...

result:

ok n: 56713, m: 91234, bishops: 147946

Test #16:

score: 0
Accepted
time: 31ms
memory: 41596kb

input:

99995 99995

output:

199988
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: 99995, m: 99995, bishops: 199988

Test #17:

score: 0
Accepted
time: 29ms
memory: 25168kb

input:

12345 54321

output:

66665
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
1 18
1 19
1 20
1 21
1 22
1 23
1 24
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
1 33
1 34
1 35
1 36
1 37
1 38
1 39
1 40
1 41
42 1
43 1
44 1
45 1
46 1
47 1
48 1
1 49
1 50
1 51
1 52
1 53
1 54
1 55
1 56
1 57
58 1
59 1
60 1
61 ...

result:

ok n: 12345, m: 54321, bishops: 66665

Test #18:

score: 0
Accepted
time: 35ms
memory: 43368kb

input:

90000 92000

output:

181998
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: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 33ms
memory: 27980kb

input:

10000 70000

output:

79998
1 1
2 1
3 1
4 1
1 5
1 6
7 1
8 1
9 1
10 1
1 11
1 12
13 1
14 1
15 1
16 1
1 17
1 18
19 1
20 1
21 1
22 1
1 23
1 24
25 1
26 1
27 1
28 1
1 29
1 30
31 1
32 1
33 1
34 1
1 35
1 36
37 1
38 1
39 1
40 1
1 41
1 42
43 1
44 1
45 1
46 1
1 47
1 48
49 1
50 1
51 1
52 1
1 53
1 54
55 1
56 1
57 1
58 1
1 59
1 60
61 ...

result:

ok n: 10000, m: 70000, bishops: 79998

Test #20:

score: 0
Accepted
time: 23ms
memory: 27772kb

input:

10000 70001

output:

80000
1 1
2 1
3 1
4 1
1 5
1 6
1 7
8 1
9 1
10 1
11 1
1 12
1 13
1 14
15 1
16 1
17 1
18 1
1 19
1 20
1 21
22 1
23 1
24 1
25 1
1 26
1 27
1 28
29 1
30 1
31 1
32 1
1 33
1 34
1 35
36 1
37 1
38 1
39 1
1 40
1 41
1 42
43 1
44 1
45 1
46 1
1 47
1 48
1 49
50 1
51 1
52 1
53 1
1 54
1 55
1 56
57 1
58 1
59 1
60 1
1 6...

result:

ok n: 10000, m: 70001, bishops: 80000

Test #21:

score: 0
Accepted
time: 39ms
memory: 30772kb

input:

10000 80000

output:

89998
1 1
1 2
3 1
1 4
6 1
1 7
1 8
9 1
1 10
1 11
12 1
1 13
14 1
15 1
1 16
17 1
1 18
1 19
20 1
1 21
1 22
23 1
1 24
1 25
26 1
1 27
28 1
29 1
1 30
31 1
1 32
1 33
34 1
1 35
1 36
37 1
1 38
1 39
40 1
1 41
42 1
43 1
1 44
45 1
1 46
1 47
48 1
1 49
1 50
51 1
1 52
1 53
54 1
1 55
56 1
57 1
1 58
59 1
1 60
1 61
62...

result:

ok n: 10000, m: 80000, bishops: 89998

Test #22:

score: 0
Accepted
time: 43ms
memory: 30736kb

input:

10000 80001

output:

90000
1 1
1 2
3 1
1 4
5 1
1 6
7 1
1 8
1 9
10 1
1 11
12 1
1 13
14 1
1 15
16 1
17 1
1 18
19 1
1 20
21 1
1 22
23 1
1 24
1 25
26 1
1 27
28 1
1 29
30 1
1 31
32 1
33 1
1 34
35 1
1 36
37 1
1 38
39 1
1 40
1 41
42 1
1 43
44 1
1 45
46 1
1 47
48 1
49 1
1 50
51 1
1 52
53 1
1 54
55 1
1 56
1 57
58 1
1 59
60 1
1 6...

result:

ok n: 10000, m: 80001, bishops: 90000

Test #23:

score: 0
Accepted
time: 14ms
memory: 29872kb

input:

10000 80002

output:

90000
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
1 10
1 11
1 12
1 13
1 14
1 15
1 16
1 17
1 18
1 19
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
1 28
1 29
1 30
1 31
1 32
1 33
1 34
1 35
1 36
1 37
38 1
39 1
40 1
41 1
42 1
43 1
44 1
45 1
1 46
1 47
1 48
1 49
1 50
1 51
1 52
1 53
1 54
1 55
56 1
57 1
58 1
59 1
60 1
61 1
62...

result:

ok n: 10000, m: 80002, bishops: 90000

Test #24:

score: 0
Accepted
time: 33ms
memory: 27960kb

input:

10000 79999

output:

89998
1 1
2 1
3 1
4 1
1 5
1 6
1 7
8 1
9 1
1 10
1 11
1 12
13 1
14 1
15 1
16 1
1 17
1 18
1 19
20 1
21 1
1 22
1 23
1 24
25 1
26 1
27 1
28 1
1 29
1 30
1 31
32 1
33 1
1 34
1 35
1 36
37 1
38 1
39 1
40 1
1 41
1 42
1 43
44 1
45 1
1 46
1 47
1 48
49 1
50 1
51 1
52 1
1 53
1 54
1 55
56 1
57 1
1 58
1 59
1 60
61 ...

result:

ok n: 10000, m: 79999, bishops: 89998

Test #25:

score: 0
Accepted
time: 27ms
memory: 28180kb

input:

10000 79998

output:

89996
1 2
1 3
1 4
1 5
1 6
7 1
8 1
9 1
10 1
1 11
1 12
1 13
1 14
1 15
1 16
17 1
18 1
19 1
20 1
1 21
1 22
1 23
1 24
1 25
1 26
27 1
28 1
29 1
30 1
1 31
1 32
1 33
1 34
1 35
1 36
37 1
38 1
39 1
40 1
1 41
1 42
1 43
1 44
1 45
1 46
47 1
48 1
49 1
50 1
1 51
1 52
1 53
1 54
1 55
1 56
57 1
58 1
59 1
60 1
1 61
1 ...

result:

ok n: 10000, m: 79998, bishops: 89996

Test #26:

score: 0
Accepted
time: 35ms
memory: 34148kb

input:

11111 100000

output:

111110
1 1
2 1
3 1
4 1
5 1
1 6
1 7
1 8
1 9
10 1
11 1
12 1
13 1
14 1
1 15
1 16
1 17
1 18
19 1
20 1
21 1
22 1
23 1
1 24
1 25
1 26
1 27
28 1
29 1
30 1
31 1
32 1
1 33
1 34
1 35
1 36
37 1
38 1
39 1
40 1
41 1
1 42
1 43
1 44
1 45
46 1
47 1
48 1
49 1
50 1
1 51
1 52
1 53
1 54
55 1
56 1
57 1
58 1
59 1
1 60
1 ...

result:

ok n: 11111, m: 100000, bishops: 111110

Test #27:

score: 0
Accepted
time: 0ms
memory: 16100kb

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed