QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#181888#7178. BishopsUSP_USP_USP#AC ✓20ms9424kbC++204.9kb2023-09-17 03:01:202023-09-17 03:01:21

Judging History

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

  • [2023-09-17 03:01:21]
  • 评测
  • 测评结果:AC
  • 用时:20ms
  • 内存:9424kb
  • [2023-09-17 03:01:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define pb push_back

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

const int INF = 1e12;

struct Dinic {
    struct edge {
        int to, cap, flow;
    };

    vector<vector<int>> g;
    vector<int> lvl;
    vector<edge> e;

    Dinic (int sz) : g (sz), lvl (sz) {}

    void add_edge (int s, int t, int cap) {
        int id = e.size ();
        g[s].push_back(id);
        e.push_back ({t, cap, 0});
        g[t].push_back (++id);
        e.push_back ({s, cap, cap});
    }

    bool bfs (int s, int t) {
        fill (all (lvl), INF);
        lvl[s] = 0;
        queue<int> q;
        q.push (s);
        while (!q.empty () && lvl[t] == INF) {
            int v = q.front ();
            q.pop ();
            for (int id : g[v]) {
                auto [p, cap, flow] = e[id];
                if (lvl[p] != INF || cap == flow) continue;
                lvl[p] = lvl[v] + 1;
                q.push (p);
            }
        }
        return lvl[t] != INF;
    }

    int dfs (int v, int pool, int t, vector<int>  &st) {
        if (!pool) return 0;
        if (v == t) return pool;
        for (; st[v] < (int) g[v].size (); st[v]++) {
            int id = g[v][st[v]];
            auto &[p, cap, flow] = e[id];
            if (lvl[v] + 1 != lvl[p] || cap == flow) continue;
            int f = dfs (p, min (cap - flow, pool), t, st);
            if (f) {
                flow += f;
                e[id ^ 1].flow -= f;
                return f;
            }
        }
        return 0;
    }

    int get_flow (int s, int t) {
        int res = 0;
        vector<int> start (g.size ());
        while (bfs (s, t)) {
            fill (all (start), 0);
            while (int f = dfs (s, INF, t, start))
                res += f;
        }
        return res;
    }
};


void dfs (int n, int m, vector<pair<int, int>> &ans) {
    assert (!(n <= 0 || m <= 0));
    // dbg (n, m, ans.size ());
    if (m == 2 * n && (n & 1)) {
        for (int j = 1; j <= n; j++) ans.pb ({j, 1});
        for (int j = 1; j <= n; j++) ans.pb ({j, m});
        for (int x = 2; x <= n; x += 2) ans.pb ({x, n}), ans.pb ({x, n + 1});
        return;
    }
    if (n == 2 * m && (m & 1)) {
        for (int j = 1; j <= m; j++) ans.pb ({1, j});
        for (int j = 1; j <= m; j++) ans.pb ({n, j});
        for (int x = 2; x <= m; x += 2) ans.pb ({m, x}), ans.pb ({m + 1, x});
        return;
    }
    if (n < m) {
        for (int i = 1; i <= n; i++) ans.pb ({i, m});
        dfs (n, m - n, ans);
    }
    else if (m < n) {
        for (int j = 1; j <= m; j++) ans.pb  ({n, j});
        dfs (n - m, m, ans);
    }
    else {
        assert (n == m);
        for (int i = 1; i < n; i++) ans.pb ({i, m}), ans.pb ({i, 1});
        if (n == 1) ans.pb ({1, 1});
    }
}

int brute (int n, int m) {
    int s = 5 * n + 5 * m, t = s + 1;

    Dinic grafo (5 * n + 5 * m + 2);

    vector<vector<int>> diag (2);
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        diag[0].pb (i - j);
        diag[1].pb (i + j);
    }

    sort (all (diag[0]));
    diag[0].resize (unique (all (diag[0])) - diag[0].begin ());


    sort (all (diag[1]));
    diag[1].resize (unique (all (diag[1])) - diag[1].begin ());

    const int shift = n + m;
    int p = 0;
    map<int, int> M;
    for (auto u : diag[0]) {
        grafo.add_edge (s, p, 1);
        M[u] = p++;
    }
    for (auto u : diag[1]) {
        grafo.add_edge (p, t, 1);
        M[u + shift] = p++;
    }

    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        grafo.add_edge (M[i - j], M[i + j + shift], 1);
    }
    return grafo.get_flow (s, t);
}

void solve (int n, int m) {
    // cin >> n >> m;
    vector<pair<int, int>> ans;
    dfs (n, m, ans);

    // {
    //     vector<int> diag (2 * (n + m));
    //     for (auto [x, y] : ans) {
    //         assert (diag[n + m + x - y] == 0);
    //         diag[n + m + x - y]++;
    //     }
    // }
    // {
    //     vector<int> diag (2 * (n + m));
    //     for (auto [x, y] : ans) {
    //         assert (diag[x + y] == 0);
    //         diag[x + y]++;
    //     }
    // }
    // assert (n + m - 2 <= ans.size ());
    // int matching = brute (n, m);
    // dbg (n, m, ans.size (), matching);
    // assert (ans.size () == matching);
    cout << ans.size () << "\n";
    for (auto [x, y] : ans)
        cout << x << " " << y << "\n";
}

signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    solve (n, m);
    // for (int i = 1; i <= 100; i++) {
    //     for (int j = i; j <= 100; j++) {
	//         solve(i, j);
    //     }
    // }
}

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

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3796kb

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

score: 0
Accepted
time: 20ms
memory: 8100kb

input:

100000 100000

output:

199998
1 100000
1 1
2 100000
2 1
3 100000
3 1
4 100000
4 1
5 100000
5 1
6 100000
6 1
7 100000
7 1
8 100000
8 1
9 100000
9 1
10 100000
10 1
11 100000
11 1
12 100000
12 1
13 100000
13 1
14 100000
14 1
15 100000
15 1
16 100000
16 1
17 100000
17 1
18 100000
18 1
19 100000
19 1
20 100000
20 1
21 100000
2...

result:

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

Test #4:

score: 0
Accepted
time: 20ms
memory: 9156kb

input:

100000 99999

output:

199998
100000 1
100000 2
100000 3
100000 4
100000 5
100000 6
100000 7
100000 8
100000 9
100000 10
100000 11
100000 12
100000 13
100000 14
100000 15
100000 16
100000 17
100000 18
100000 19
100000 20
100000 21
100000 22
100000 23
100000 24
100000 25
100000 26
100000 27
100000 28
100000 29
100000 30
10...

result:

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

Test #5:

score: 0
Accepted
time: 15ms
memory: 8180kb

input:

100000 50000

output:

149998
100000 1
100000 2
100000 3
100000 4
100000 5
100000 6
100000 7
100000 8
100000 9
100000 10
100000 11
100000 12
100000 13
100000 14
100000 15
100000 16
100000 17
100000 18
100000 19
100000 20
100000 21
100000 22
100000 23
100000 24
100000 25
100000 26
100000 27
100000 28
100000 29
100000 30
10...

result:

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

Test #6:

score: 0
Accepted
time: 6ms
memory: 5284kb

input:

1 100000

output:

100000
1 100000
1 99999
1 99998
1 99997
1 99996
1 99995
1 99994
1 99993
1 99992
1 99991
1 99990
1 99989
1 99988
1 99987
1 99986
1 99985
1 99984
1 99983
1 99982
1 99981
1 99980
1 99979
1 99978
1 99977
1 99976
1 99975
1 99974
1 99973
1 99972
1 99971
1 99970
1 99969
1 99968
1 99967
1 99966
1 99965
1 99...

result:

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

Test #7:

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

input:

34535 99889

output:

134423
1 99889
2 99889
3 99889
4 99889
5 99889
6 99889
7 99889
8 99889
9 99889
10 99889
11 99889
12 99889
13 99889
14 99889
15 99889
16 99889
17 99889
18 99889
19 99889
20 99889
21 99889
22 99889
23 99889
24 99889
25 99889
26 99889
27 99889
28 99889
29 99889
30 99889
31 99889
32 99889
33 99889
34 99...

result:

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

Test #8:

score: 0
Accepted
time: 7ms
memory: 5196kb

input:

12231 97889

output:

110119
1 97889
2 97889
3 97889
4 97889
5 97889
6 97889
7 97889
8 97889
9 97889
10 97889
11 97889
12 97889
13 97889
14 97889
15 97889
16 97889
17 97889
18 97889
19 97889
20 97889
21 97889
22 97889
23 97889
24 97889
25 97889
26 97889
27 97889
28 97889
29 97889
30 97889
31 97889
32 97889
33 97889
34 97...

result:

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

Test #9:

score: 0
Accepted
time: 7ms
memory: 5360kb

input:

10000 100000

output:

109998
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31...

result:

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

Test #10:

score: 0
Accepted
time: 6ms
memory: 5276kb

input:

13 99999

output:

100011
1 99999
2 99999
3 99999
4 99999
5 99999
6 99999
7 99999
8 99999
9 99999
10 99999
11 99999
12 99999
13 99999
1 99986
2 99986
3 99986
4 99986
5 99986
6 99986
7 99986
8 99986
9 99986
10 99986
11 99986
12 99986
13 99986
1 99973
2 99973
3 99973
4 99973
5 99973
6 99973
7 99973
8 99973
9 99973
10 99...

result:

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

Test #11:

score: 0
Accepted
time: 10ms
memory: 5228kb

input:

21 99999

output:

100019
1 99999
2 99999
3 99999
4 99999
5 99999
6 99999
7 99999
8 99999
9 99999
10 99999
11 99999
12 99999
13 99999
14 99999
15 99999
16 99999
17 99999
18 99999
19 99999
20 99999
21 99999
1 99978
2 99978
3 99978
4 99978
5 99978
6 99978
7 99978
8 99978
9 99978
10 99978
11 99978
12 99978
13 99978
14 99...

result:

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

Test #12:

score: 0
Accepted
time: 16ms
memory: 9424kb

input:

49999 100000

output:

149998
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31...

result:

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

Test #13:

score: 0
Accepted
time: 10ms
memory: 7560kb

input:

33333 99999

output:

133331
1 99999
2 99999
3 99999
4 99999
5 99999
6 99999
7 99999
8 99999
9 99999
10 99999
11 99999
12 99999
13 99999
14 99999
15 99999
16 99999
17 99999
18 99999
19 99999
20 99999
21 99999
22 99999
23 99999
24 99999
25 99999
26 99999
27 99999
28 99999
29 99999
30 99999
31 99999
32 99999
33 99999
34 99...

result:

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

Test #14:

score: 0
Accepted
time: 12ms
memory: 5288kb

input:

23342 98876

output:

122216
1 98876
2 98876
3 98876
4 98876
5 98876
6 98876
7 98876
8 98876
9 98876
10 98876
11 98876
12 98876
13 98876
14 98876
15 98876
16 98876
17 98876
18 98876
19 98876
20 98876
21 98876
22 98876
23 98876
24 98876
25 98876
26 98876
27 98876
28 98876
29 98876
30 98876
31 98876
32 98876
33 98876
34 98...

result:

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

Test #15:

score: 0
Accepted
time: 12ms
memory: 9060kb

input:

56713 91234

output:

147946
1 91234
2 91234
3 91234
4 91234
5 91234
6 91234
7 91234
8 91234
9 91234
10 91234
11 91234
12 91234
13 91234
14 91234
15 91234
16 91234
17 91234
18 91234
19 91234
20 91234
21 91234
22 91234
23 91234
24 91234
25 91234
26 91234
27 91234
28 91234
29 91234
30 91234
31 91234
32 91234
33 91234
34 91...

result:

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

Test #16:

score: 0
Accepted
time: 16ms
memory: 9016kb

input:

99995 99995

output:

199988
1 99995
1 1
2 99995
2 1
3 99995
3 1
4 99995
4 1
5 99995
5 1
6 99995
6 1
7 99995
7 1
8 99995
8 1
9 99995
9 1
10 99995
10 1
11 99995
11 1
12 99995
12 1
13 99995
13 1
14 99995
14 1
15 99995
15 1
16 99995
16 1
17 99995
17 1
18 99995
18 1
19 99995
19 1
20 99995
20 1
21 99995
21 1
22 99995
22 1
23 ...

result:

ok n: 99995, m: 99995, bishops: 199988

Test #17:

score: 0
Accepted
time: 3ms
memory: 5188kb

input:

12345 54321

output:

66665
1 54321
2 54321
3 54321
4 54321
5 54321
6 54321
7 54321
8 54321
9 54321
10 54321
11 54321
12 54321
13 54321
14 54321
15 54321
16 54321
17 54321
18 54321
19 54321
20 54321
21 54321
22 54321
23 54321
24 54321
25 54321
26 54321
27 54321
28 54321
29 54321
30 54321
31 54321
32 54321
33 54321
34 543...

result:

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

Test #18:

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

input:

90000 92000

output:

181998
1 92000
2 92000
3 92000
4 92000
5 92000
6 92000
7 92000
8 92000
9 92000
10 92000
11 92000
12 92000
13 92000
14 92000
15 92000
16 92000
17 92000
18 92000
19 92000
20 92000
21 92000
22 92000
23 92000
24 92000
25 92000
26 92000
27 92000
28 92000
29 92000
30 92000
31 92000
32 92000
33 92000
34 92...

result:

ok n: 90000, m: 92000, bishops: 181998

Test #19:

score: 0
Accepted
time: 8ms
memory: 5200kb

input:

10000 70000

output:

79998
1 70000
2 70000
3 70000
4 70000
5 70000
6 70000
7 70000
8 70000
9 70000
10 70000
11 70000
12 70000
13 70000
14 70000
15 70000
16 70000
17 70000
18 70000
19 70000
20 70000
21 70000
22 70000
23 70000
24 70000
25 70000
26 70000
27 70000
28 70000
29 70000
30 70000
31 70000
32 70000
33 70000
34 700...

result:

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

Test #20:

score: 0
Accepted
time: 4ms
memory: 5356kb

input:

10000 70001

output:

80000
1 70001
2 70001
3 70001
4 70001
5 70001
6 70001
7 70001
8 70001
9 70001
10 70001
11 70001
12 70001
13 70001
14 70001
15 70001
16 70001
17 70001
18 70001
19 70001
20 70001
21 70001
22 70001
23 70001
24 70001
25 70001
26 70001
27 70001
28 70001
29 70001
30 70001
31 70001
32 70001
33 70001
34 700...

result:

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

Test #21:

score: 0
Accepted
time: 9ms
memory: 5360kb

input:

10000 80000

output:

89998
1 80000
2 80000
3 80000
4 80000
5 80000
6 80000
7 80000
8 80000
9 80000
10 80000
11 80000
12 80000
13 80000
14 80000
15 80000
16 80000
17 80000
18 80000
19 80000
20 80000
21 80000
22 80000
23 80000
24 80000
25 80000
26 80000
27 80000
28 80000
29 80000
30 80000
31 80000
32 80000
33 80000
34 800...

result:

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

Test #22:

score: 0
Accepted
time: 6ms
memory: 5196kb

input:

10000 80001

output:

90000
1 80001
2 80001
3 80001
4 80001
5 80001
6 80001
7 80001
8 80001
9 80001
10 80001
11 80001
12 80001
13 80001
14 80001
15 80001
16 80001
17 80001
18 80001
19 80001
20 80001
21 80001
22 80001
23 80001
24 80001
25 80001
26 80001
27 80001
28 80001
29 80001
30 80001
31 80001
32 80001
33 80001
34 800...

result:

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

Test #23:

score: 0
Accepted
time: 9ms
memory: 5224kb

input:

10000 80002

output:

90000
1 80002
2 80002
3 80002
4 80002
5 80002
6 80002
7 80002
8 80002
9 80002
10 80002
11 80002
12 80002
13 80002
14 80002
15 80002
16 80002
17 80002
18 80002
19 80002
20 80002
21 80002
22 80002
23 80002
24 80002
25 80002
26 80002
27 80002
28 80002
29 80002
30 80002
31 80002
32 80002
33 80002
34 800...

result:

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

Test #24:

score: 0
Accepted
time: 9ms
memory: 5188kb

input:

10000 79999

output:

89998
1 79999
2 79999
3 79999
4 79999
5 79999
6 79999
7 79999
8 79999
9 79999
10 79999
11 79999
12 79999
13 79999
14 79999
15 79999
16 79999
17 79999
18 79999
19 79999
20 79999
21 79999
22 79999
23 79999
24 79999
25 79999
26 79999
27 79999
28 79999
29 79999
30 79999
31 79999
32 79999
33 79999
34 799...

result:

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

Test #25:

score: 0
Accepted
time: 9ms
memory: 5144kb

input:

10000 79998

output:

89996
1 79998
2 79998
3 79998
4 79998
5 79998
6 79998
7 79998
8 79998
9 79998
10 79998
11 79998
12 79998
13 79998
14 79998
15 79998
16 79998
17 79998
18 79998
19 79998
20 79998
21 79998
22 79998
23 79998
24 79998
25 79998
26 79998
27 79998
28 79998
29 79998
30 79998
31 79998
32 79998
33 79998
34 799...

result:

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

Test #26:

score: 0
Accepted
time: 7ms
memory: 5168kb

input:

11111 100000

output:

111110
1 100000
2 100000
3 100000
4 100000
5 100000
6 100000
7 100000
8 100000
9 100000
10 100000
11 100000
12 100000
13 100000
14 100000
15 100000
16 100000
17 100000
18 100000
19 100000
20 100000
21 100000
22 100000
23 100000
24 100000
25 100000
26 100000
27 100000
28 100000
29 100000
30 100000
31...

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed