QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#172243#7178. Bishopsucup-team228#AC ✓82ms24824kbC++204.9kb2023-09-09 18:22:462023-09-09 18:22:47

Judging History

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

  • [2023-09-09 18:22:47]
  • 评测
  • 测评结果:AC
  • 用时:82ms
  • 内存:24824kb
  • [2023-09-09 18:22:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct HopcroftKarp {
    static const int N = 2e5 + 10;
    vector<int> adj_left[N];
    int matchL[N] = {};
    int matchR[N] = {};
    int root[N], prev[N], qq[N];

    void add_edge(int u, int v) {
        adj_left[u].push_back(v);
    }
    void init(int L, int R) {
        for (int i = 1; i <= L; i++) {
            adj_left[i].clear();
            matchL[i] = 0;
        }
        for (int i = 1; i <= R; i++) {
            matchR[i] = 0;
        }
    }
    void init_matching(int L, int R) {
        for (int i = 1; i <= L; i++) {
            matchL[i] = 0;
        }
        for (int i = 1; i <= R; i++) {
            matchR[i] = 0;
        }
    }
    int maxmatching(int L, int R) {
        int sz = 0;
        for (bool updated = true; updated; ) {
            updated = false;
            for (int i = 1; i <= L; i++) {
                root[i] = -1;
                prev[i] = -1;
                qq[i] = 0;
            }
            int qi = 0, qj = 0;
            for (int i = 1; i <= L; i++) {
                if (matchL[i] == 0) {
                    qq[qj++] = i, root[i] = i, prev[i] = i;
                }
            }
            while (qi < qj) {
                int u = qq[qi++];
                if (matchL[root[u]] != 0) {
                    continue;
                }
                for (int v : adj_left[u]) {
                    if (matchR[v] == 0) {
                        while (v != 0) {
                            matchR[v] = u, swap(matchL[u], v), u = prev[u];
                        }
                        updated = true;
                        sz++;
                        break;
                    }
                    if (prev[matchR[v]] == -1) {
                        v = matchR[v], prev[v] = u, root[v] = root[u], qq[qj++] = v;
                    }
                }
            }
        }
        return sz;
    }
};

HopcroftKarp hk;

struct Kek {
    int l, r, id;
    bool operator<(const Kek& ot) const{
        return tie(r, l, id) < tie(ot.r, ot.l, ot.id);
    }
};

const int inf = 1e9;
const int N = 2e5 + 10;
int mn[N], mx[N];
Kek a[N];

int f(int x, int mod) {
    return ((x % mod) + mod) % mod;
}

vector<pair<int, int>> solve(int n, int m) {
    for (int i = 2; i <= n + m; i++) {
        mn[i] = inf;
        mx[i] = -inf;
    }
    for (int i = 1; i <= n; i++) {
        for (int j : {1, m}) {
            mn[i + j] = min(mn[i + j], i - j);
            mx[i + j] = max(mx[i + j], i - j);
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i : {1, n}) {
            mn[i + j] = min(mn[i + j], i - j);
            mx[i + j] = max(mx[i + j], i - j);
        }
    }
    for (int i = 2; i <= n + m; i++) {
        a[i] = {mn[i], mx[i], i};
    }
    sort(a + 2, a + n + m + 1);
    set<int> s[2];
    for (int i = 1 - m; i <= n - 1; i++) {
        s[f(i, 2)].insert(i);
    }
    vector<pair<int, int>> ans;
    for (int i = 2; i <= n + m; i++) {
        int t = a[i].id & 1;
        auto it = s[t].lower_bound(a[i].l);
        if (it != s[t].end() && *it <= a[i].r) {
            int sum = a[i].id;
            int dif = *it;
            int x = (sum + dif) / 2;
            int y = (sum - dif) / 2;
            ans.emplace_back(x, y);
            s[t].erase(it);
        }
    }
    return ans;
}

int slow(int n, int m) {
    hk.init(n + m, n - 1 + m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            hk.add_edge(i + j, i - j + m);
        }
    }
    return hk.maxmatching(n + m, n - 1 + m);
}

bool check(const vector<pair<int, int>>& vec) {
    set<int> sum, dif;
    for (auto [i, j] : vec) {
        if (sum.count(i + j)) {
            return false;
        }
        if (dif.count(i - j)) {
            return false;
        }
        sum.insert(i + j);
        dif.insert(i - j);
    }
    return true;
}

void stress() {
    mt19937 rnd;
    while (true) {
        int n = rnd() % 30 + 1;
        int m = rnd() % 30 + 1;
        auto ans = solve(n, m);
        int res = slow(n, m);
        if (ans.size() == res && check(ans)) {
            cout << "OK" << endl;
        } else {
            cout << "WA\n";
            cout << n << " " << m << "\n";
            cout << ans.size() << " " << res << "\n";
            break;
        }
    }
    exit(0);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    // stress();

    int n, m;
    cin >> n >> m;
    auto ans = solve(n, m);
    cout << ans.size() << "\n";
    for (auto [i, j] : ans) {
        cout << i << " " << j << "\n";
    }
    // assert(check(ans));

#ifdef LOCAL
    cout << "\nTime elapsed: " << double(clock()) / CLOCKS_PER_SEC << " s.\n";
#endif
}

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 13760kb

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

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

input:

100000 100000

output:

199998
1 1
1 2
100000 99999
1 3
100000 99998
1 4
100000 99997
1 5
100000 99996
1 6
100000 99995
1 7
100000 99994
1 8
100000 99993
1 9
100000 99992
1 10
100000 99991
1 11
100000 99990
1 12
100000 99989
1 13
100000 99988
1 14
100000 99987
1 15
100000 99986
1 16
100000 99985
1 17
100000 99984
1 18
1000...

result:

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

Test #4:

score: 0
Accepted
time: 82ms
memory: 24824kb

input:

100000 99999

output:

199998
1 1
1 2
100000 99999
1 3
100000 99998
1 4
100000 99997
1 5
100000 99996
1 6
100000 99995
1 7
100000 99994
1 8
100000 99993
1 9
100000 99992
1 10
100000 99991
1 11
100000 99990
1 12
100000 99989
1 13
100000 99988
1 14
100000 99987
1 15
100000 99986
1 16
100000 99985
1 17
100000 99984
1 18
1000...

result:

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

Test #5:

score: 0
Accepted
time: 46ms
memory: 22464kb

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: 28ms
memory: 19552kb

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: 47ms
memory: 20872kb

input:

34535 99889

output:

134423
34535 99889
34534 99889
34533 99889
34532 99889
34531 99889
34530 99889
34529 99889
34528 99889
34527 99889
34526 99889
34525 99889
34524 99889
34523 99889
34522 99889
34521 99889
34520 99889
34519 99889
34518 99889
34517 99889
34516 99889
34515 99889
34514 99889
34513 99889
34512 99889
34511...

result:

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

Test #8:

score: 0
Accepted
time: 37ms
memory: 20084kb

input:

12231 97889

output:

110119
12231 97889
12230 97889
12229 97889
12228 97889
12227 97889
12226 97889
12225 97889
12224 97889
12223 97889
12222 97889
12221 97889
12220 97889
12219 97889
12218 97889
12217 97889
12216 97889
12215 97889
12214 97889
12213 97889
12212 97889
12211 97889
12210 97889
12209 97889
12208 97889
12207...

result:

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

Test #9:

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

input:

10000 100000

output:

109998
10000 100000
9999 100000
9998 100000
9997 100000
9996 100000
9995 100000
9994 100000
9993 100000
9992 100000
9991 100000
9990 100000
9989 100000
9988 100000
9987 100000
9986 100000
9985 100000
9984 100000
9983 100000
9982 100000
9981 100000
9980 100000
9979 100000
9978 100000
9977 100000
9976...

result:

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

Test #10:

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

input:

13 99999

output:

100011
13 99999
12 99999
11 99999
10 99999
9 99999
8 99999
7 99999
6 99999
5 99999
4 99999
3 99999
2 99999
1 99999
7 99992
7 99991
7 99990
7 99989
7 99988
7 99987
7 99986
7 99985
7 99984
7 99983
7 99982
7 99981
7 99980
7 99979
7 99978
7 99977
7 99976
7 99975
7 99974
7 99973
7 99972
7 99971
7 99970
7...

result:

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

Test #11:

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

input:

21 99999

output:

100019
21 99999
20 99999
19 99999
18 99999
17 99999
16 99999
15 99999
14 99999
13 99999
12 99999
11 99999
10 99999
9 99999
8 99999
7 99999
6 99999
5 99999
4 99999
3 99999
2 99999
1 99999
11 99988
11 99987
11 99986
11 99985
11 99984
11 99983
11 99982
11 99981
11 99980
11 99979
11 99978
11 99977
11 99...

result:

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

Test #12:

score: 0
Accepted
time: 44ms
memory: 21948kb

input:

49999 100000

output:

149998
49999 100000
49998 100000
49997 100000
49996 100000
49995 100000
49994 100000
49993 100000
49992 100000
49991 100000
49990 100000
49989 100000
49988 100000
49987 100000
49986 100000
49985 100000
49984 100000
49983 100000
49982 100000
49981 100000
49980 100000
49979 100000
49978 100000
49977 1...

result:

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

Test #13:

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

input:

33333 99999

output:

133331
33333 99999
33332 99999
33331 99999
33330 99999
33329 99999
33328 99999
33327 99999
33326 99999
33325 99999
33324 99999
33323 99999
33322 99999
33321 99999
33320 99999
33319 99999
33318 99999
33317 99999
33316 99999
33315 99999
33314 99999
33313 99999
33312 99999
33311 99999
33310 99999
33309...

result:

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

Test #14:

score: 0
Accepted
time: 38ms
memory: 20360kb

input:

23342 98876

output:

122216
23342 98876
23341 98876
23340 98876
23339 98876
23338 98876
23337 98876
23336 98876
23335 98876
23334 98876
23333 98876
23332 98876
23331 98876
23330 98876
23329 98876
23328 98876
23327 98876
23326 98876
23325 98876
23324 98876
23323 98876
23322 98876
23321 98876
23320 98876
23319 98876
23318...

result:

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

Test #15:

score: 0
Accepted
time: 57ms
memory: 23032kb

input:

56713 91234

output:

147946
56713 91234
56712 91234
56711 91234
56710 91234
56709 91234
56708 91234
56707 91234
56706 91234
56705 91234
56704 91234
56703 91234
56702 91234
56701 91234
56700 91234
56699 91234
56698 91234
56697 91234
56696 91234
56695 91234
56694 91234
56693 91234
56692 91234
56691 91234
56690 91234
56689...

result:

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

Test #16:

score: 0
Accepted
time: 78ms
memory: 24292kb

input:

99995 99995

output:

199988
1 1
1 2
99995 99994
1 3
99995 99993
1 4
99995 99992
1 5
99995 99991
1 6
99995 99990
1 7
99995 99989
1 8
99995 99988
1 9
99995 99987
1 10
99995 99986
1 11
99995 99985
1 12
99995 99984
1 13
99995 99983
1 14
99995 99982
1 15
99995 99981
1 16
99995 99980
1 17
99995 99979
1 18
99995 99978
1 19
999...

result:

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

Test #17:

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

input:

12345 54321

output:

66665
12345 54321
12344 54321
12343 54321
12342 54321
12341 54321
12340 54321
12339 54321
12338 54321
12337 54321
12336 54321
12335 54321
12334 54321
12333 54321
12332 54321
12331 54321
12330 54321
12329 54321
12328 54321
12327 54321
12326 54321
12325 54321
12324 54321
12323 54321
12322 54321
12321 ...

result:

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

Test #18:

score: 0
Accepted
time: 63ms
memory: 22672kb

input:

90000 92000

output:

181998
90000 92000
89999 92000
89998 92000
89997 92000
89996 92000
89995 92000
89994 92000
89993 92000
89992 92000
89991 92000
89990 92000
89989 92000
89988 92000
89987 92000
89986 92000
89985 92000
89984 92000
89983 92000
89982 92000
89981 92000
89980 92000
89979 92000
89978 92000
89977 92000
89976...

result:

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

Test #19:

score: 0
Accepted
time: 19ms
memory: 18432kb

input:

10000 70000

output:

79998
10000 70000
9999 70000
9998 70000
9997 70000
9996 70000
9995 70000
9994 70000
9993 70000
9992 70000
9991 70000
9990 70000
9989 70000
9988 70000
9987 70000
9986 70000
9985 70000
9984 70000
9983 70000
9982 70000
9981 70000
9980 70000
9979 70000
9978 70000
9977 70000
9976 70000
9975 70000
9974 70...

result:

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

Test #20:

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

input:

10000 70001

output:

80000
10000 70001
9999 70001
9998 70001
9997 70001
9996 70001
9995 70001
9994 70001
9993 70001
9992 70001
9991 70001
9990 70001
9989 70001
9988 70001
9987 70001
9986 70001
9985 70001
9984 70001
9983 70001
9982 70001
9981 70001
9980 70001
9979 70001
9978 70001
9977 70001
9976 70001
9975 70001
9974 70...

result:

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

Test #21:

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

input:

10000 80000

output:

89998
10000 80000
9999 80000
9998 80000
9997 80000
9996 80000
9995 80000
9994 80000
9993 80000
9992 80000
9991 80000
9990 80000
9989 80000
9988 80000
9987 80000
9986 80000
9985 80000
9984 80000
9983 80000
9982 80000
9981 80000
9980 80000
9979 80000
9978 80000
9977 80000
9976 80000
9975 80000
9974 80...

result:

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

Test #22:

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

input:

10000 80001

output:

90000
10000 80001
9999 80001
9998 80001
9997 80001
9996 80001
9995 80001
9994 80001
9993 80001
9992 80001
9991 80001
9990 80001
9989 80001
9988 80001
9987 80001
9986 80001
9985 80001
9984 80001
9983 80001
9982 80001
9981 80001
9980 80001
9979 80001
9978 80001
9977 80001
9976 80001
9975 80001
9974 80...

result:

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

Test #23:

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

input:

10000 80002

output:

90000
10000 80002
9999 80002
9998 80002
9997 80002
9996 80002
9995 80002
9994 80002
9993 80002
9992 80002
9991 80002
9990 80002
9989 80002
9988 80002
9987 80002
9986 80002
9985 80002
9984 80002
9983 80002
9982 80002
9981 80002
9980 80002
9979 80002
9978 80002
9977 80002
9976 80002
9975 80002
9974 80...

result:

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

Test #24:

score: 0
Accepted
time: 17ms
memory: 16936kb

input:

10000 79999

output:

89998
10000 79999
9999 79999
9998 79999
9997 79999
9996 79999
9995 79999
9994 79999
9993 79999
9992 79999
9991 79999
9990 79999
9989 79999
9988 79999
9987 79999
9986 79999
9985 79999
9984 79999
9983 79999
9982 79999
9981 79999
9980 79999
9979 79999
9978 79999
9977 79999
9976 79999
9975 79999
9974 79...

result:

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

Test #25:

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

input:

10000 79998

output:

89996
10000 79998
9999 79998
9998 79998
9997 79998
9996 79998
9995 79998
9994 79998
9993 79998
9992 79998
9991 79998
9990 79998
9989 79998
9988 79998
9987 79998
9986 79998
9985 79998
9984 79998
9983 79998
9982 79998
9981 79998
9980 79998
9979 79998
9978 79998
9977 79998
9976 79998
9975 79998
9974 79...

result:

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

Test #26:

score: 0
Accepted
time: 28ms
memory: 19660kb

input:

11111 100000

output:

111110
11111 100000
11110 100000
11109 100000
11108 100000
11107 100000
11106 100000
11105 100000
11104 100000
11103 100000
11102 100000
11101 100000
11100 100000
11099 100000
11098 100000
11097 100000
11096 100000
11095 100000
11094 100000
11093 100000
11092 100000
11091 100000
11090 100000
11089 1...

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed