QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165423#7178. Bishopsucup-team1600#AC ✓22ms5336kbC++235.0kb2023-09-05 18:00:022023-09-05 18:00:03

Judging History

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

  • [2023-09-05 18:00:03]
  • 评测
  • 测评结果:AC
  • 用时:22ms
  • 内存:5336kb
  • [2023-09-05 18:00:02]
  • 提交

answer

//#pragma GCC optimize("Ofast", "unroll-loops")
//#pragma GCC target("sse", "sse2", "sse3", "ssse3", "sse4")
#ifdef LOCAL
#include <iostream>
#include <cmath>
#include <algorithm>
#include <stdio.h>
#include <cstdint>
#include <cstring>
#include <string>
#include <cstdlib>
#include <vector>
#include <bitset>
#include <map>
#include <queue>
#include <ctime>
#include <stack>
#include <set>
#include <list>
#include <random>
#include <deque>
#include <functional>
#include <iomanip>
#include <sstream>
#include <fstream>
#include <complex>
#include <numeric>
#include <cassert>
#include <array>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <thread>
#else
#include <bits/stdc++.h>
#endif

#define all(a) a.begin(),a.end()
#define len(a) (int)(a.size())
#define mp make_pair
#define pb push_back
#define fir first
#define sec second
#define fi first
#define se second

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef long double ld;

template<typename T>
inline bool umin(T &a, T b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<typename T>
inline bool umax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

#ifdef LOCAL
#define D for (bool _FLAG = true; _FLAG; _FLAG = false)
#define LOG(...) print(#__VA_ARGS__" ::", __VA_ARGS__) << endl
template <class ...Ts> auto &print(Ts ...ts) { return ((cerr << ts << " "), ...); }
#else
#define D while (false)
#define LOG(...)
#endif // LOCAL

const int max_n = -1, inf = 1000111222;


vector <pii> ans;

inline int f (int n, int m) {
    int ans = (n + m + (n & 1) + (m & 1) - 1) / 2;
    if (n == m && n % 2) {
        --ans;
    }
    return max(1, ans);
}
inline void solve1 (int n, int m, int x, int y, int sgnx, int sgny);

inline void solve2 (int n, int m, int x, int y, int sgnx, int sgny) {
    LOG(2, n, m);
    if (n % 2 == 0) {
        solve1(n, m, x + (n + 1) * sgnx, y, -sgnx, sgny);
        return;
    }
    else if (m % 2 == 0) {
        solve1(n, m, x, y + (m + 1) * sgny, sgnx, -sgny);
        return;
    }

    if (n == 1) {
        for (int i = 2; i <= m; i += 2) {
            ans.pb({x + 1 * sgnx, y + i * sgny});
        }
        return;
    }
    if (m == 1) {
        for (int i = 2; i <= n; i += 2) {
            ans.pb({x + i * sgnx, y + 1 * sgny});
        }
        return;
    }
//    if (n == m) {
//        if (n >= 2) {
//            for (int i = 1; i <= n; i += 2) {
//                ans.pb({x + sgnx * 2, y + i * sgny});
//            }
//            for (int i = 4; i <= n - 3; i += 2) {
//                ans.pb({x + sgnx * n, y + i * sgny});
//            }
//        }
//        return;
//    }
    if (n < m) {
        for (int i = 2; i <= n; i += 2) {
            ans.pb({x + i * sgnx, y + 1 * sgny});
        }
        solve2(n, m - n + 1, x, y + (n - 1) * sgny, sgnx, sgny);
        return;
    }
    for (int i = 2; i <= m; i += 2) {
        ans.pb({x + 1 * sgnx, y + i * sgny});
    }
    solve2(n - m + 1, m, x + (m - 1) * sgnx, y, sgnx, sgny);
}

inline void solve1 (int n, int m, int x, int y, int sgnx, int sgny) {
    LOG(1, n, m);
    if (n == m) {
        if (n & 1) {
            for (int i = 1; i <= n; i += 2) {
                ans.pb({x + i * sgnx, y + sgny});
            }
            for (int i = 3; i < n; i += 2) {
                ans.pb({x + i *sgnx, y + n * sgny});
            }
        }
        else {
            for (int i = 1; i <= n; i += 2) {
                ans.pb({x + i * sgnx, y + sgny});
            }
            for (int i = 2; i < n; i += 2) {
                ans.pb({x + i * sgnx, y + n * sgny});
            }
        }
        return;
    }
    if (n < m) {
        for (int i = 1; i <= n; i += 2) {
            ans.pb({x + i * sgnx, y + sgny});
        }
        if (n & 1) {
            solve2(n, m - n, x, y + n * sgny, sgnx, sgny);
        }
        else {
            solve1(n, m - n, x, y + n * sgny, sgnx, sgny);
        }
        return;
    }
    for (int i = 1; i <= m; i += 2) {
        ans.pb({x + sgnx, y + i * sgny});
    }
    if (m & 1) {
        solve2(n - m, m, x + m * sgnx, y, sgnx, sgny);
    }
    else {
        solve1(n - m, m, x + m * sgnx, y, sgnx, sgny);
    }
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

//    int n;
//    cin >> n;
//    for (int i = 1; i < n; i++) {
//        for (int j = i + 1; j < n; j++) {
//            int res = f(i, j);
//            int go = (i + 1) / 2 + f(i, j - i);
//            if (res != go) {
//                LOG(i, j, res, go);
//            }
//        }
//    }
    int n, m;
    cin >> n >> m;
    solve1(n, m, 0, 0, 1, 1);
    solve2(n, m, 0, 0, 1, 1);
    cout << len(ans) << '\n';
    for (auto &i : ans) {
        cout << i.first << ' ' << i.second << '\n';
    }
}

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

詳細信息

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

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

input:

100000 100000

output:

199998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #4:

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

input:

100000 99999

output:

199998
1 1
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109
1 111
1 113
1 115
...

result:

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

Test #5:

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

input:

100000 50000

output:

149998
1 1
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109
1 111
1 113
1 115
...

result:

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

Test #6:

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

input:

1 100000

output:

100000
1 1
1 3
1 5
1 7
1 9
1 11
1 13
1 15
1 17
1 19
1 21
1 23
1 25
1 27
1 29
1 31
1 33
1 35
1 37
1 39
1 41
1 43
1 45
1 47
1 49
1 51
1 53
1 55
1 57
1 59
1 61
1 63
1 65
1 67
1 69
1 71
1 73
1 75
1 77
1 79
1 81
1 83
1 85
1 87
1 89
1 91
1 93
1 95
1 97
1 99
1 101
1 103
1 105
1 107
1 109
1 111
1 113
1 115
...

result:

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

Test #7:

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

input:

34535 99889

output:

134423
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #8:

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

input:

12231 97889

output:

110119
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #9:

score: 0
Accepted
time: 13ms
memory: 4248kb

input:

10000 100000

output:

109998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #10:

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

input:

13 99999

output:

100011
1 1
3 1
5 1
7 1
9 1
11 1
13 1
1 99999
3 99999
5 99999
7 99999
9 99999
11 99999
13 99999
2 99986
4 99986
6 99986
8 99986
10 99986
12 99986
2 99974
4 99974
6 99974
8 99974
10 99974
12 99974
2 99962
4 99962
6 99962
8 99962
10 99962
12 99962
2 99950
4 99950
6 99950
8 99950
10 99950
12 99950
2 999...

result:

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

Test #11:

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

input:

21 99999

output:

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

result:

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

Test #12:

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

input:

49999 100000

output:

149998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #13:

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

input:

33333 99999

output:

133331
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #14:

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

input:

23342 98876

output:

122216
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #15:

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

input:

56713 91234

output:

147946
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #16:

score: 0
Accepted
time: 22ms
memory: 5220kb

input:

99995 99995

output:

199988
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #17:

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

input:

12345 54321

output:

66665
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #18:

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

input:

90000 92000

output:

181998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #19:

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

input:

10000 70000

output:

79998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #20:

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

input:

10000 70001

output:

80000
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #21:

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

input:

10000 80000

output:

89998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #22:

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

input:

10000 80001

output:

90000
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #23:

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

input:

10000 80002

output:

90000
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #24:

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

input:

10000 79999

output:

89998
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #25:

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

input:

10000 79998

output:

89996
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
1...

result:

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

Test #26:

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

input:

11111 100000

output:

111110
1 1
3 1
5 1
7 1
9 1
11 1
13 1
15 1
17 1
19 1
21 1
23 1
25 1
27 1
29 1
31 1
33 1
35 1
37 1
39 1
41 1
43 1
45 1
47 1
49 1
51 1
53 1
55 1
57 1
59 1
61 1
63 1
65 1
67 1
69 1
71 1
73 1
75 1
77 1
79 1
81 1
83 1
85 1
87 1
89 1
91 1
93 1
95 1
97 1
99 1
101 1
103 1
105 1
107 1
109 1
111 1
113 1
115 1
...

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed