QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#173730#7178. Bishopsucup-team197#WA 18ms5264kbC++202.0kb2023-09-10 01:30:162023-09-10 01:30:17

Judging History

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

  • [2023-09-10 01:30:17]
  • 评测
  • 测评结果:WA
  • 用时:18ms
  • 内存:5264kb
  • [2023-09-10 01:30:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

vector<pair<int, int>> solve(int n, int m){
    vector<pair<int, int>> v;
    while(m >= 2 * n){
        for(int i = 1; i <= n; ++i){
            v.push_back({i, m});
        }
        m -= n;
    }

    if(m == n){
        for(int i = 1; i <= n; ++i)
            v.push_back({i, 1});
        for(int i = 2; i <= n - 1; ++i)
            v.push_back({i, n});
    }
    else{
        for(int i = 1; i <= n; ++i)
            v.push_back({i, 1});
        for(int i = 1; i <= n; ++i)
            v.push_back({i, m});

        int mid = (1 + m) / 2;
        for(int i = 1; i <= n; ++i){
            int diff = m - mid;
            int diff2 = mid - 1;
            diff = min(diff, diff2);
            // cout << diff << " diff " << n - diff << " " << i <<  " " << 1 + diff << endl;
            if(i > n - diff && i < 1 + diff){
                v.push_back({i, mid});
            }
        }
    }
    return v;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<pair<int, int>> v;
    if(n < m){
        v = solve(n, m);
    }
    else{
        v = solve(m, n);
        for(auto &[x, y]: v)
            swap(x, y);
    }

    /*for(auto [x, y]: v){
        assert(1 <= x && x <= n);
        assert(1 <= y && y <= m);
    }

    for(int i = 0; i < v.size(); ++i){
        auto [x, y] = v[i];
        for(int j = i + 1; j < v.size(); ++j){
            auto [x2, y2] = v[j];

            int sum_1 = x + y;
            int sum_2 = x2 + y2;
            assert(sum_1 != sum_2);
            int diff_1 = x - y;
            int diff_2 = x2 - y2;
            assert(diff_1 != diff_2);
        }
    }*/

    cout << v.size() << "\n";
    for(auto [x, y]: v)
        cout << x << " " << y << "\n";
}

详细

Test #1:

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

input:

2 5

output:

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

result:

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

Test #2:

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

input:

5 5

output:

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

result:

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

Test #3:

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

input:

100000 100000

output:

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

Test #4:

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

input:

100000 99999

output:

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

Test #5:

score: 0
Accepted
time: 8ms
memory: 5128kb

input:

100000 50000

output:

149998
100000 1
100000 2
100000 3
100000 4
100000 5
100000 6
100000 7
100000 8
100000 9
100000 10
100000 11
100000 12
100000 13
100000 14
100000 15
100000 16
100000 17
100000 18
100000 19
100000 20
100000 21
100000 22
100000 23
100000 24
100000 25
100000 26
100000 27
100000 28
100000 29
100000 30
10...

result:

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

Test #6:

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

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: -100
Wrong Answer
time: 10ms
memory: 5168kb

input:

34535 99889

output:

134422
1 99889
2 99889
3 99889
4 99889
5 99889
6 99889
7 99889
8 99889
9 99889
10 99889
11 99889
12 99889
13 99889
14 99889
15 99889
16 99889
17 99889
18 99889
19 99889
20 99889
21 99889
22 99889
23 99889
24 99889
25 99889
26 99889
27 99889
28 99889
29 99889
30 99889
31 99889
32 99889
33 99889
34 99...

result:

wrong answer Participant's answer is not optimal (134422 < 134423)