QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232690#7178. BishopsikefumyAC ✓80ms15872kbC++204.3kb2023-10-30 19:43:552023-10-30 19:43:55

Judging History

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

  • [2023-10-30 19:43:55]
  • 评测
  • 测评结果:AC
  • 用时:80ms
  • 内存:15872kb
  • [2023-10-30 19:43:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
    if(x > y) {
        x = y;
        return true;
    } else return false;
}
template<class T> bool chmax(T& x, T y){
    if(x < y) {
        x = y;
        return true;
    } else return false;
}

// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )

#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )

#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)

// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)

// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)

// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)    
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)

// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)

// for_earh
#define fore(e, v) for (auto&& e : v)

// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()

int n, m;
pii upper_right(pii p) {
    auto [x, y] = p;
    int d = min(x, m - 1 - y);
    return {x - d, y + d};
}

pii lower_right(pii p) {
    auto [x, y] = p;
    int d = min(n - 1 - x, m - 1 - y);
    return {x + d, y + d};
}

// 左側からのidx
int get_idx(pii p) {
    auto [x, y] = p;
    if (x == n - 1) return n - 1 + m - 1 - y;
    else return x;
}

pii get_point(int i1, int i2) {
    int x, y;
    if (i1 < n) x = i1, y = 0;
    else x = n - 1, y = i1 - n + 1;

    int mx = get_idx(lower_right({x, y}));
    int d = (mx - i2) / 2;

    return {x - d, y + d};
}
// 番号 区間
vector<pii> get_matching(vector<pair<int, pii>> elem) {
    // 番号 終端
    vector<vector<pii>> query(n + m - 1);
    int parity = 0;
    fore (e, elem) {
        auto [idx, p] = e;
        auto [l, r] = p;
        query[l].push_back({r, idx});
        parity = l % 2;
    }

    vector<pii> ret;
    int nw = parity;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    rep (i, nw, n + m - 1, 2) {
        fore (u, query[i]) pq.push(u);
        while (!pq.empty()) {
            auto [r, idx] = pq.top();
            if (r < i) pq.pop();
            else break;
        }
        
        if (!pq.empty()) {
            ret.push_back({pq.top().second, i});
            pq.pop();
        }
    }

    return ret;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> n >> m;
    int dx = 1, dy = 0, x = 0, y = 0;

    vector<pair<int, pii>> edges[2];
    rep (_, n + m - 1) {
        if (x == n - 1) dx = 0, dy = 1;
        auto [x1, y1] = lower_right(upper_right({x, y}));
        auto [x2, y2] = lower_right({x, y});
        edges[(x + y) % 2].push_back({x + y, {get_idx(lower_right(upper_right({x, y}))), get_idx(lower_right({x, y}))}});
        x += dx, y += dy;
    }

    vector<pii> ans;
    rep (i, 2) {
        auto v = get_matching(edges[i]);
        ans.insert(ans.end(), all(v));
    }

    cout << ans.size() << endl;
    fore (u, ans) {
        auto [x, y] = get_point(u.first, u.second);
        cout << x + 1 << ' ' << y + 1 << endl;
    }
}

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

詳細信息

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

score: 0
Accepted
time: 76ms
memory: 15652kb

input:

100000 100000

output:

199998
1 99999
1 99997
1 99995
1 99993
1 99991
1 99989
1 99987
1 99985
1 99983
1 99981
1 99979
1 99977
1 99975
1 99973
1 99971
1 99969
1 99967
1 99965
1 99963
1 99961
1 99959
1 99957
1 99955
1 99953
1 99951
1 99949
1 99947
1 99945
1 99943
1 99941
1 99939
1 99937
1 99935
1 99933
1 99931
1 99929
1 999...

result:

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

Test #4:

score: 0
Accepted
time: 80ms
memory: 15688kb

input:

100000 99999

output:

199998
1 99999
1 99997
1 99995
1 99993
1 99991
1 99989
1 99987
1 99985
1 99983
1 99981
1 99979
1 99977
1 99975
1 99973
1 99971
1 99969
1 99967
1 99965
1 99963
1 99961
1 99959
1 99957
1 99955
1 99953
1 99951
1 99949
1 99947
1 99945
1 99943
1 99941
1 99939
1 99937
1 99935
1 99933
1 99931
1 99929
1 999...

result:

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

Test #5:

score: 0
Accepted
time: 48ms
memory: 13264kb

input:

100000 50000

output:

149998
1 49999
1 49997
1 49995
1 49993
1 49991
1 49989
1 49987
1 49985
1 49983
1 49981
1 49979
1 49977
1 49975
1 49973
1 49971
1 49969
1 49967
1 49965
1 49963
1 49961
1 49959
1 49957
1 49955
1 49953
1 49951
1 49949
1 49947
1 49945
1 49943
1 49941
1 49939
1 49937
1 49935
1 49933
1 49931
1 49929
1 499...

result:

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

Test #6:

score: 0
Accepted
time: 36ms
memory: 10264kb

input:

1 100000

output:

100000
1 99999
1 99997
1 99995
1 99993
1 99991
1 99989
1 99987
1 99985
1 99983
1 99981
1 99979
1 99977
1 99975
1 99973
1 99971
1 99969
1 99967
1 99965
1 99963
1 99961
1 99959
1 99957
1 99955
1 99953
1 99951
1 99949
1 99947
1 99945
1 99943
1 99941
1 99939
1 99937
1 99935
1 99933
1 99931
1 99929
1 999...

result:

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

Test #7:

score: 0
Accepted
time: 41ms
memory: 12712kb

input:

34535 99889

output:

134423
1 99889
3 99889
5 99889
7 99889
9 99889
11 99889
13 99889
15 99889
17 99889
19 99889
21 99889
23 99889
25 99889
27 99889
29 99889
31 99889
33 99889
35 99889
37 99889
39 99889
41 99889
43 99889
45 99889
47 99889
49 99889
51 99889
53 99889
55 99889
57 99889
59 99889
61 99889
63 99889
65 99889
6...

result:

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

Test #8:

score: 0
Accepted
time: 48ms
memory: 10612kb

input:

12231 97889

output:

110119
1 97889
3 97889
5 97889
7 97889
9 97889
11 97889
13 97889
15 97889
17 97889
19 97889
21 97889
23 97889
25 97889
27 97889
29 97889
31 97889
33 97889
35 97889
37 97889
39 97889
41 97889
43 97889
45 97889
47 97889
49 97889
51 97889
53 97889
55 97889
57 97889
59 97889
61 97889
63 97889
65 97889
6...

result:

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

Test #9:

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

input:

10000 100000

output:

109998
2 100000
4 100000
6 100000
8 100000
10 100000
12 100000
14 100000
16 100000
18 100000
20 100000
22 100000
24 100000
26 100000
28 100000
30 100000
32 100000
34 100000
36 100000
38 100000
40 100000
42 100000
44 100000
46 100000
48 100000
50 100000
52 100000
54 100000
56 100000
58 100000
60 1000...

result:

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

Test #10:

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

input:

13 99999

output:

100011
1 99999
3 99999
5 99999
7 99999
9 99999
11 99999
13 99999
7 99991
7 99989
7 99987
7 99985
7 99983
7 99981
7 99979
7 99977
7 99975
7 99973
7 99971
7 99969
7 99967
7 99965
7 99963
7 99961
7 99959
7 99957
7 99955
7 99953
7 99951
7 99949
7 99947
7 99945
7 99943
7 99941
7 99939
7 99937
7 99935
7 9...

result:

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

Test #11:

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

input:

21 99999

output:

100019
1 99999
3 99999
5 99999
7 99999
9 99999
11 99999
13 99999
15 99999
17 99999
19 99999
21 99999
11 99987
11 99985
11 99983
11 99981
11 99979
11 99977
11 99975
11 99973
11 99971
11 99969
11 99967
11 99965
11 99963
11 99961
11 99959
11 99957
11 99955
11 99953
11 99951
11 99949
11 99947
11 99945
1...

result:

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

Test #12:

score: 0
Accepted
time: 56ms
memory: 13572kb

input:

49999 100000

output:

149998
2 100000
4 100000
6 100000
8 100000
10 100000
12 100000
14 100000
16 100000
18 100000
20 100000
22 100000
24 100000
26 100000
28 100000
30 100000
32 100000
34 100000
36 100000
38 100000
40 100000
42 100000
44 100000
46 100000
48 100000
50 100000
52 100000
54 100000
56 100000
58 100000
60 1000...

result:

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

Test #13:

score: 0
Accepted
time: 55ms
memory: 12592kb

input:

33333 99999

output:

133331
1 99999
3 99999
5 99999
7 99999
9 99999
11 99999
13 99999
15 99999
17 99999
19 99999
21 99999
23 99999
25 99999
27 99999
29 99999
31 99999
33 99999
35 99999
37 99999
39 99999
41 99999
43 99999
45 99999
47 99999
49 99999
51 99999
53 99999
55 99999
57 99999
59 99999
61 99999
63 99999
65 99999
6...

result:

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

Test #14:

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

input:

23342 98876

output:

122216
2 98876
4 98876
6 98876
8 98876
10 98876
12 98876
14 98876
16 98876
18 98876
20 98876
22 98876
24 98876
26 98876
28 98876
30 98876
32 98876
34 98876
36 98876
38 98876
40 98876
42 98876
44 98876
46 98876
48 98876
50 98876
52 98876
54 98876
56 98876
58 98876
60 98876
62 98876
64 98876
66 98876
...

result:

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

Test #15:

score: 0
Accepted
time: 51ms
memory: 13228kb

input:

56713 91234

output:

147946
2 91234
4 91234
6 91234
8 91234
10 91234
12 91234
14 91234
16 91234
18 91234
20 91234
22 91234
24 91234
26 91234
28 91234
30 91234
32 91234
34 91234
36 91234
38 91234
40 91234
42 91234
44 91234
46 91234
48 91234
50 91234
52 91234
54 91234
56 91234
58 91234
60 91234
62 91234
64 91234
66 91234
...

result:

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

Test #16:

score: 0
Accepted
time: 64ms
memory: 15872kb

input:

99995 99995

output:

199988
1 99995
1 99993
1 99991
1 99989
1 99987
1 99985
1 99983
1 99981
1 99979
1 99977
1 99975
1 99973
1 99971
1 99969
1 99967
1 99965
1 99963
1 99961
1 99959
1 99957
1 99955
1 99953
1 99951
1 99949
1 99947
1 99945
1 99943
1 99941
1 99939
1 99937
1 99935
1 99933
1 99931
1 99929
1 99927
1 99925
1 999...

result:

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

Test #17:

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

input:

12345 54321

output:

66665
1 54321
3 54321
5 54321
7 54321
9 54321
11 54321
13 54321
15 54321
17 54321
19 54321
21 54321
23 54321
25 54321
27 54321
29 54321
31 54321
33 54321
35 54321
37 54321
39 54321
41 54321
43 54321
45 54321
47 54321
49 54321
51 54321
53 54321
55 54321
57 54321
59 54321
61 54321
63 54321
65 54321
67...

result:

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

Test #18:

score: 0
Accepted
time: 56ms
memory: 14524kb

input:

90000 92000

output:

181998
2 92000
4 92000
6 92000
8 92000
10 92000
12 92000
14 92000
16 92000
18 92000
20 92000
22 92000
24 92000
26 92000
28 92000
30 92000
32 92000
34 92000
36 92000
38 92000
40 92000
42 92000
44 92000
46 92000
48 92000
50 92000
52 92000
54 92000
56 92000
58 92000
60 92000
62 92000
64 92000
66 92000
...

result:

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

Test #19:

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

input:

10000 70000

output:

79998
2 70000
4 70000
6 70000
8 70000
10 70000
12 70000
14 70000
16 70000
18 70000
20 70000
22 70000
24 70000
26 70000
28 70000
30 70000
32 70000
34 70000
36 70000
38 70000
40 70000
42 70000
44 70000
46 70000
48 70000
50 70000
52 70000
54 70000
56 70000
58 70000
60 70000
62 70000
64 70000
66 70000
6...

result:

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

Test #20:

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

input:

10000 70001

output:

80000
1 70001
3 70001
5 70001
7 70001
9 70001
11 70001
13 70001
15 70001
17 70001
19 70001
21 70001
23 70001
25 70001
27 70001
29 70001
31 70001
33 70001
35 70001
37 70001
39 70001
41 70001
43 70001
45 70001
47 70001
49 70001
51 70001
53 70001
55 70001
57 70001
59 70001
61 70001
63 70001
65 70001
67...

result:

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

Test #21:

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

input:

10000 80000

output:

89998
2 80000
4 80000
6 80000
8 80000
10 80000
12 80000
14 80000
16 80000
18 80000
20 80000
22 80000
24 80000
26 80000
28 80000
30 80000
32 80000
34 80000
36 80000
38 80000
40 80000
42 80000
44 80000
46 80000
48 80000
50 80000
52 80000
54 80000
56 80000
58 80000
60 80000
62 80000
64 80000
66 80000
6...

result:

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

Test #22:

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

input:

10000 80001

output:

90000
1 80001
3 80001
5 80001
7 80001
9 80001
11 80001
13 80001
15 80001
17 80001
19 80001
21 80001
23 80001
25 80001
27 80001
29 80001
31 80001
33 80001
35 80001
37 80001
39 80001
41 80001
43 80001
45 80001
47 80001
49 80001
51 80001
53 80001
55 80001
57 80001
59 80001
61 80001
63 80001
65 80001
67...

result:

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

Test #23:

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

input:

10000 80002

output:

90000
2 80002
4 80002
6 80002
8 80002
10 80002
12 80002
14 80002
16 80002
18 80002
20 80002
22 80002
24 80002
26 80002
28 80002
30 80002
32 80002
34 80002
36 80002
38 80002
40 80002
42 80002
44 80002
46 80002
48 80002
50 80002
52 80002
54 80002
56 80002
58 80002
60 80002
62 80002
64 80002
66 80002
6...

result:

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

Test #24:

score: 0
Accepted
time: 52ms
memory: 9308kb

input:

10000 79999

output:

89998
1 79999
3 79999
5 79999
7 79999
9 79999
11 79999
13 79999
15 79999
17 79999
19 79999
21 79999
23 79999
25 79999
27 79999
29 79999
31 79999
33 79999
35 79999
37 79999
39 79999
41 79999
43 79999
45 79999
47 79999
49 79999
51 79999
53 79999
55 79999
57 79999
59 79999
61 79999
63 79999
65 79999
67...

result:

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

Test #25:

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

input:

10000 79998

output:

89996
2 79998
4 79998
6 79998
8 79998
10 79998
12 79998
14 79998
16 79998
18 79998
20 79998
22 79998
24 79998
26 79998
28 79998
30 79998
32 79998
34 79998
36 79998
38 79998
40 79998
42 79998
44 79998
46 79998
48 79998
50 79998
52 79998
54 79998
56 79998
58 79998
60 79998
62 79998
64 79998
66 79998
6...

result:

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

Test #26:

score: 0
Accepted
time: 55ms
memory: 10640kb

input:

11111 100000

output:

111110
2 100000
4 100000
6 100000
8 100000
10 100000
12 100000
14 100000
16 100000
18 100000
20 100000
22 100000
24 100000
26 100000
28 100000
30 100000
32 100000
34 100000
36 100000
38 100000
40 100000
42 100000
44 100000
46 100000
48 100000
50 100000
52 100000
54 100000
56 100000
58 100000
60 1000...

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed