QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#170244#7178. Bishopsucup-team173#AC ✓125ms23644kbC++142.6kb2023-09-09 14:52:182023-09-09 14:52:20

Judging History

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

  • [2023-09-09 14:52:20]
  • 评测
  • 测评结果:AC
  • 用时:125ms
  • 内存:23644kb
  • [2023-09-09 14:52:18]
  • 提交

answer

#include <bits/stdc++.h>
#define For(x, y, z) for(int x = (y); x <= z; x++)
#define Rep(x, y, z) for(int x = (y); x >= z; x--)
using namespace std;
const int MAXN = 1e5 + 5;
int n, m, flg;
map<int, int> visy, visx;
vector<pair<int, int> > ans; 
inline void SolveEven() {
    for(int x = 2; x <= n + m; x += 2) {
        if(visx[x]) break; 
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(!visy[ly]) {
            visy[ly] = 1, visx[x] = 1;
            ans.emplace_back(x - rj, rj);
        } else break;
    }    
    for(int x = n + m - (n + m & 1); x >= 2; x -= 2) {
        if(visx[x]) break; 
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(!visy[ry]) {
            visy[ry] = 1, visx[x] = 1;
            ans.emplace_back(x - lj, lj);
        } else if(ry != 0) break;
    }
    int pp = 2;
    for(int x = 2; x <= n + m; x += 2) {
        if(visx[x]) continue;
        if(visy[pp]) break;
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(ly <= pp && pp <= ry) {
            visy[pp] = 1, visx[x] = 1;
            ans.emplace_back(x + pp >> 1, x - pp >> 1);
            pp += 2;
        }
    }    
}
inline void SolveOdd() {
    for(int x = 3; x <= n + m; x += 2) {
        if(visx[x]) break; 
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(!visy[ly]) {
            visy[ly] = 1, visx[x] = 1;
            ans.emplace_back(x - rj, rj);
        } else break;
    }    
    for(int x = n + m - 1 + (n + m & 1); x >= 3; x -= 2) {
        if(visx[x]) break; 
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(!visy[ry]) {
            visy[ry] = 1, visx[x] = 1;
            ans.emplace_back(x - lj, lj);
        } else break;
    }
    int pp = 1;
    for(int x = 3; x <= n + m; x += 2) {
        if(visx[x]) continue;
        if(visy[pp]) break;
        int lj = max(x - n, 1), rj = min(x - 1, m);
        int ly = x - 2 * rj, ry = x - 2 * lj;
        if(ly <= pp && pp <= ry) {
            visy[pp] = 1, visx[x] = 1;
            ans.emplace_back(x + pp >> 1, x - pp >> 1);
            pp += 2;
        }
    }    
}
int main() {
    scanf("%d%d", &n, &m);
    if(n < m) swap(n, m), flg = 1;
    SolveEven();
    SolveOdd();
    cout << ans.size() << '\n';
    for(auto [x, y] : ans) {
        if(flg) swap(x, y);
        cout << x << ' ' << y << '\n';
    }
    return 0;
} 

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

score: 0
Accepted
time: 119ms
memory: 23592kb

input:

100000 100000

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: 100000, bishops: 199998

Test #4:

score: 0
Accepted
time: 125ms
memory: 23644kb

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: 80ms
memory: 18348kb

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: 56ms
memory: 13508kb

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: 79ms
memory: 17604kb

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: 68ms
memory: 14396kb

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: 60ms
memory: 14432kb

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: 55ms
memory: 13428kb

input:

13 99999

output:

100011
1 1
3 1
5 1
7 1
9 1
11 1
13 1
13 99999
11 99999
9 99999
7 99999
5 99999
3 99999
1 99999
7 9
7 11
7 13
7 15
7 17
7 19
7 21
7 23
7 25
7 27
7 29
7 31
7 33
7 35
7 37
7 39
7 41
7 43
7 45
7 47
7 49
7 51
7 53
7 55
7 57
7 59
7 61
7 63
7 65
7 67
7 69
7 71
7 73
7 75
7 77
7 79
7 81
7 83
7 85
7 87
7 89
7...

result:

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

Test #11:

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

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
21 99999
19 99999
17 99999
15 99999
13 99999
11 99999
9 99999
7 99999
5 99999
3 99999
1 99999
11 13
11 15
11 17
11 19
11 21
11 23
11 25
11 27
11 29
11 31
11 33
11 35
11 37
11 39
11 41
11 43
11 45
11 47
11 49
11 51
11 53
11 55
11 57
11 59
11 61...

result:

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

Test #12:

score: 0
Accepted
time: 81ms
memory: 18536kb

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: 79ms
memory: 17600kb

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: 59ms
memory: 15536kb

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: 83ms
memory: 18136kb

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: 107ms
memory: 23496kb

input:

99995 99995

output:

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

Test #17:

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

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: 107ms
memory: 21740kb

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: 43ms
memory: 11356kb

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: 45ms
memory: 11188kb

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: 41ms
memory: 12460kb

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: 54ms
memory: 12480kb

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: 54ms
memory: 12276kb

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: 49ms
memory: 12468kb

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: 53ms
memory: 12276kb

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: 52ms
memory: 14620kb

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: 3768kb

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed