QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#175523#7178. BishopsSorahISAAC ✓19ms9380kbC++202.9kb2023-09-10 19:06:442023-09-10 19:06:45

Judging History

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

  • [2023-09-10 19:06:45]
  • 评测
  • 测评结果:AC
  • 用时:19ms
  • 内存:9380kb
  • [2023-09-10 19:06:44]
  • 提交

answer

#ifndef Yamada
#define Yamada
#include Yamada __FILE__ Yamada

void solve() {
    int N, M; cin >> N >> M;
    
    if (N == 1 and M == 1) {
        cout << 1 << "\n";
        cout << 1 << " " << 1 << "\n";
        return;
    }
    
    bool flag_swap = false;
    if (N == M) --N;
    if (N > M) swap(N, M), flag_swap = true;
    
    vector<pii> bishops;
    for (int c1 = 1, c2 = M; c1 + N <= c2; c1 += N, c2 -= N) {
        for (int r = 1; r <= N; ++r) bishops.eb(r, c1), bishops.eb(r, c2);
        if (c1 + 3*N > c2) {
            if (c1 + 2*N <= c2) {
                c1 += N;
                for (int r = 1; r <= N; ++r) bishops.eb(r, c1);
            }
            if (N % 2 == 1) {
                for (int r = (N+1)/2, c = c1+N/2+1; c <= c2-N/2-1; ++c) bishops.eb(r, c);
            }
            else {
                int c = (c1 + c2) / 2, k = N - (c - c1);
                for (int r = k+1; r <= N-k; ++r) bishops.eb(r, c);
                if (N - 2*k == 1 and c - c1 != c2 - c) bishops.eb(k+1, c+1);
            }
        }
    }
    
    cout << SZ(bishops) << "\n";
    for (auto [r, c] : bishops) {
        if (flag_swap) cout << c << " " << r << "\n";
        else           cout << r << " " << c << "\n";
    }
    
    // vector<string> board(N, string(M, '.'));
    // for (auto [r, c] : bishops) board[r-1][c-1] = 'x';
    // for (string &str : board) debug(str);
}

int32_t main() {
    fastIO();
    
    int t = 1; // cin >> t;
    for (int _ = 1; _ <= t; ++_) {
        solve();
    }
    
    return 0;
}

#else

#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
// #define double __float80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())

#ifdef local
#define fastIO() void()
#define debug(...) \
    fprintf(stderr, "%sAt [%s], line %d: (%s) = ", "\u001b[33m", __FILE__, __LINE__, #__VA_ARGS__), \
    _do(__VA_ARGS__), fprintf(stderr, "%s", "\u001b[0m")
template <typename T> void _do(T &&_t) {cerr << _t << "\n";}
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) {cerr << _t << ", ", _do(_u...);}
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template <typename T, typename U> bool chmin(T &lhs, U rhs) {return lhs > rhs ? lhs = rhs, 1 : 0;}
template <typename T, typename U> bool chmax(T &lhs, U rhs) {return lhs < rhs ? lhs = rhs, 1 : 0;}

#endif

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

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

input:

100000 100000

output:

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

result:

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

Test #4:

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

input:

100000 99999

output:

199998
1 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...

result:

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

Test #5:

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

input:

100000 50000

output:

149998
1 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...

result:

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

Test #6:

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

input:

1 100000

output:

100000
1 1
1 100000
1 2
1 99999
1 3
1 99998
1 4
1 99997
1 5
1 99996
1 6
1 99995
1 7
1 99994
1 8
1 99993
1 9
1 99992
1 10
1 99991
1 11
1 99990
1 12
1 99989
1 13
1 99988
1 14
1 99987
1 15
1 99986
1 16
1 99985
1 17
1 99984
1 18
1 99983
1 19
1 99982
1 20
1 99981
1 21
1 99980
1 22
1 99979
1 23
1 99978
1 ...

result:

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

Test #7:

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

input:

34535 99889

output:

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

result:

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

Test #8:

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

input:

12231 97889

output:

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

result:

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

Test #9:

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

input:

10000 100000

output:

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

result:

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

Test #10:

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

input:

13 99999

output:

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

result:

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

Test #11:

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

input:

21 99999

output:

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

result:

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

Test #12:

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

input:

49999 100000

output:

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

result:

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

Test #13:

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

input:

33333 99999

output:

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

result:

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

Test #14:

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

input:

23342 98876

output:

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

result:

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

Test #15:

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

input:

56713 91234

output:

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

result:

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

Test #16:

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

input:

99995 99995

output:

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

result:

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

Test #17:

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

input:

12345 54321

output:

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

result:

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

Test #18:

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

input:

90000 92000

output:

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

result:

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

Test #19:

score: 0
Accepted
time: 5ms
memory: 5256kb

input:

10000 70000

output:

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

result:

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

Test #20:

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

input:

10000 70001

output:

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

result:

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

Test #21:

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

input:

10000 80000

output:

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

result:

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

Test #22:

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

input:

10000 80001

output:

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

result:

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

Test #23:

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

input:

10000 80002

output:

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

result:

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

Test #24:

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

input:

10000 79999

output:

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

result:

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

Test #25:

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

input:

10000 79998

output:

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

result:

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

Test #26:

score: 0
Accepted
time: 2ms
memory: 5320kb

input:

11111 100000

output:

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

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed