QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#197389#7178. Bishopsmendicillin2#AC ✓47ms10304kbC++173.5kb2023-10-02 15:22:412023-10-02 15:22:42

Judging History

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

  • [2023-10-02 15:22:42]
  • 评测
  • 测评结果:AC
  • 用时:47ms
  • 内存:10304kb
  • [2023-10-02 15:22:41]
  • 提交

answer

#include <bits/stdc++.h>

#define LL long long
#define ull unsigned long long
#define F(i, j, k) for (int i = j; i <= k; ++i)
#define DF(i, j, k) for (int i = j; i >= k; --i)

using namespace std;

template <typename T> inline void read(T &n) {
    T w = 1;
    n = 0;
    char ch = getchar();
    while (!isdigit(ch) && ch != EOF) {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (isdigit(ch) && ch != EOF) {
        n = (n << 3) + (n << 1) + (ch & 15);
        ch = getchar();
    }
    n *= w;
}

template <typename T> inline void write(T x) {
    T l = 0;
    ull y = 0;
    if (!x) { putchar(48); return; }
    if (x < 0) { x = -x; putchar('-'); }
    while (x) { y = y * 10 + x % 10; x /= 10; ++l; }
    while (l) { putchar(y % 10 + 48); y /= 10; --l; }
}

template <typename T> inline void writes(T x) {
    write(x);
    putchar(' ');
}

template <typename T> inline void writeln(T x) {
    write(x);
    puts("");
}

template <typename T> inline void checkmax(T &a, T b) { a = a > b ? a : b; }

template <typename T> inline void checkmin(T &a, T b) { a = a < b ? a : b; }

const int N = 2e5 + 100;

int L[N], R[N];

struct work {
    int l, r, x, y;
} a[N];

inline bool cmp(work x, work y) { return x.l < y.l; }

vector <pair<int, int> > ans;

priority_queue<pair<int, int> > q;

int main() {
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    int n, m;
    read(n); read(m);
    F(i, 1, n + m - 1) {
        int li, ri;
        if (i <= n) li = i; else li = n;
        if (i <= n) ri = 1; else ri = i - n + 1;
        L[i] = ri - li + 100000;
        if (i <= m) li = 1; else li = i - m + 1;
        if (i <= m) ri = i; else ri = m;
        R[i] = ri - li + 100000;
    }
    int cnt = 0, MX = 0;
    for (int i = 1; i <= n + m - 1; i += 2) {
        ++cnt;
        a[cnt].l = L[i] / 2 + 1;
        a[cnt].r = R[i] / 2 + 1;
        int li, ri;
        if (i <= n) li = i; else li = n;
        if (i <= n) ri = 1; else ri = i - n + 1;
        a[cnt].x = li;
        a[cnt].y = ri;
        checkmax(MX, a[i].r);
    }
    sort(a + 1, a + cnt + 1, cmp);
    int pos = a[1].l, now = 0, it = 0;
    while (1) {
        while (a[now + 1].l <= pos && now + 1 <= cnt) { ++now; q.push(make_pair(-a[now].r, now)); }
        while (!q.empty() && -q.top().first < pos) q.pop();
        ++ it;
        if (it > 250000) break;
        if (q.empty()) continue;
        int i = q.top().second; q.pop();
        ans.emplace_back(make_pair(a[i].x - (pos - a[i].l), a[i].y + (pos - a[i].l)));
        ++pos;
    }
    cnt = 0, MX = 0;
    for (int i = 2; i <= n + m - 1; i += 2) {
        ++cnt;
        a[cnt].l = L[i] / 2 + 1;
        a[cnt].r = R[i] / 2 + 1;
        int li, ri;
        if (i <= n) li = i; else li = n;
        if (i <= n) ri = 1; else ri = i - n + 1;
        a[cnt].x = li;
        a[cnt].y = ri;
        checkmax(MX, a[i].r);
    }
    sort(a + 1, a + cnt + 1, cmp);
    pos = a[1].l; now = 0; it = 0;
    while (!q.empty()) q.pop();
    while (1) {
        while (a[now + 1].l <= pos && now + 1 <= cnt) { ++now; q.push(make_pair(-a[now].r, now)); }
        while (!q.empty() && -q.top().first < pos) q.pop();
        ++ it;
        if (it > 250000) break;
        if (q.empty()) continue;
        int i = q.top().second; q.pop();
        ans.emplace_back(make_pair(a[i].x - (pos - a[i].l), a[i].y + (pos - a[i].l)));
        ++pos;
    }
    writeln(ans.size());
    for (auto i : ans) { writes(i.first); writeln(i.second); }
    return 0;
}

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

詳細信息

Test #1:

score: 100
Accepted
time: 2ms
memory: 5616kb

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: 2ms
memory: 5600kb

input:

5 5

output:

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

result:

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

Test #3:

score: 0
Accepted
time: 40ms
memory: 10304kb

input:

100000 100000

output:

199998
100000 2
99997 1
100000 6
99993 1
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
99961 1
99959 1
99957 1
99955 1
99953 1
100000 50
99949 1
99947 1
99945 1
99943 1
99941 1
100000 62
100000 64...

result:

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

Test #4:

score: 0
Accepted
time: 44ms
memory: 10300kb

input:

100000 99999

output:

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

result:

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

Test #5:

score: 0
Accepted
time: 33ms
memory: 9996kb

input:

100000 50000

output:

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

result:

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

Test #6:

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

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: 26ms
memory: 9352kb

input:

34535 99889

output:

134423
34535 1
34533 1
34531 1
34529 1
34527 1
34525 1
34523 1
34521 1
34519 1
34517 1
34515 1
34513 1
34511 1
34509 1
34507 1
34505 1
34503 1
34501 1
34499 1
34497 1
34495 1
34493 1
34491 1
34489 1
34487 1
34485 1
34483 1
34481 1
34479 1
34477 1
34475 1
34473 1
34471 1
34469 1
34467 1
34465 1
34463...

result:

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

Test #8:

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

input:

12231 97889

output:

110119
12231 1
12229 1
12227 1
12225 1
12223 1
12221 1
12219 1
12217 1
12215 1
12213 1
12211 1
12209 1
12207 1
12205 1
12203 1
12201 1
12199 1
12197 1
12195 1
12193 1
12191 1
12189 1
12187 1
12185 1
12183 1
12181 1
12179 1
12177 1
12175 1
12173 1
12171 1
12169 1
12167 1
12165 1
12163 1
12161 1
12159...

result:

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

Test #9:

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

input:

10000 100000

output:

109998
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1...

result:

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

Test #10:

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

input:

13 99999

output:

100011
13 1
11 1
9 1
7 1
5 1
3 1
1 1
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 91
7 93
7 95
7 97
7 99
7 101
7 103
7 105
7 107
7 109
7 11...

result:

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

Test #11:

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

input:

21 99999

output:

100019
21 1
19 1
17 1
15 1
13 1
11 1
9 1
7 1
5 1
3 1
1 1
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
11 63
11 65
11 67
11 69
11 71
11 73
11 75
11 77
11 79
11 81
11 83
11 85
11 87
11 89
11 91
11 ...

result:

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

Test #12:

score: 0
Accepted
time: 23ms
memory: 9764kb

input:

49999 100000

output:

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

result:

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

Test #13:

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

input:

33333 99999

output:

133331
33333 1
33331 1
33329 1
33327 1
33325 1
33323 1
33321 1
33319 1
33317 1
33315 1
33313 1
33311 1
33309 1
33307 1
33305 1
33303 1
33301 1
33299 1
33297 1
33295 1
33293 1
33291 1
33289 1
33287 1
33285 1
33283 1
33281 1
33279 1
33277 1
33275 1
33273 1
33271 1
33269 1
33267 1
33265 1
33263 1
33261...

result:

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

Test #14:

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

input:

23342 98876

output:

122216
23341 1
23339 1
23337 1
23335 1
23333 1
23331 1
23329 1
23327 1
23325 1
23323 1
23321 1
23319 1
23317 1
23315 1
23313 1
23311 1
23309 1
23307 1
23305 1
23303 1
23301 1
23299 1
23297 1
23295 1
23293 1
23291 1
23289 1
23287 1
23285 1
23283 1
23281 1
23279 1
23277 1
23275 1
23273 1
23271 1
23269...

result:

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

Test #15:

score: 0
Accepted
time: 24ms
memory: 9332kb

input:

56713 91234

output:

147946
56713 1
56711 1
56709 1
56707 1
56705 1
56703 1
56701 1
56699 1
56697 1
56695 1
56693 1
56691 1
56689 1
56687 1
56685 1
56683 1
56681 1
56679 1
56677 1
56675 1
56673 1
56671 1
56669 1
56667 1
56665 1
56663 1
56661 1
56659 1
56657 1
56655 1
56653 1
56651 1
56649 1
56647 1
56645 1
56643 1
56641...

result:

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

Test #16:

score: 0
Accepted
time: 47ms
memory: 9760kb

input:

99995 99995

output:

199988
99995 1
99995 3
99995 5
99995 7
99995 9
99995 11
99995 13
99981 1
99979 1
99977 1
99975 1
99973 1
99995 25
99995 27
99995 29
99995 31
99995 33
99961 1
99995 37
99995 39
99955 1
99953 1
99995 45
99995 47
99995 49
99995 51
99995 53
99995 55
99995 57
99937 1
99935 1
99995 63
99931 1
99929 1
9999...

result:

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

Test #17:

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

input:

12345 54321

output:

66665
12345 1
12343 1
12341 1
12339 1
12337 1
12335 1
12333 1
12331 1
12329 1
12327 1
12325 1
12323 1
12321 1
12319 1
12317 1
12315 1
12313 1
12311 1
12309 1
12307 1
12305 1
12303 1
12301 1
12299 1
12297 1
12295 1
12293 1
12291 1
12289 1
12287 1
12285 1
12283 1
12281 1
12279 1
12277 1
12275 1
12273 ...

result:

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

Test #18:

score: 0
Accepted
time: 31ms
memory: 9816kb

input:

90000 92000

output:

181998
89999 1
89997 1
89995 1
89993 1
89991 1
89989 1
89987 1
89985 1
89983 1
89981 1
89979 1
89977 1
89975 1
89973 1
89971 1
89969 1
89967 1
89965 1
89963 1
89961 1
89959 1
89957 1
89955 1
89953 1
89951 1
89949 1
89947 1
89945 1
89943 1
89941 1
89939 1
89937 1
89935 1
89933 1
89931 1
89929 1
89927...

result:

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

Test #19:

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

input:

10000 70000

output:

79998
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #20:

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

input:

10000 70001

output:

80000
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #21:

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

input:

10000 80000

output:

89998
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #22:

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

input:

10000 80001

output:

90000
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #23:

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

input:

10000 80002

output:

90000
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #24:

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

input:

10000 79999

output:

89998
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #25:

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

input:

10000 79998

output:

89996
9999 1
9997 1
9995 1
9993 1
9991 1
9989 1
9987 1
9985 1
9983 1
9981 1
9979 1
9977 1
9975 1
9973 1
9971 1
9969 1
9967 1
9965 1
9963 1
9961 1
9959 1
9957 1
9955 1
9953 1
9951 1
9949 1
9947 1
9945 1
9943 1
9941 1
9939 1
9937 1
9935 1
9933 1
9931 1
9929 1
9927 1
9925 1
9923 1
9921 1
9919 1
9917 1
...

result:

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

Test #26:

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

input:

11111 100000

output:

111110
11111 1
11109 1
11107 1
11105 1
11103 1
11101 1
11099 1
11097 1
11095 1
11093 1
11091 1
11089 1
11087 1
11085 1
11083 1
11081 1
11079 1
11077 1
11075 1
11073 1
11071 1
11069 1
11067 1
11065 1
11063 1
11061 1
11059 1
11057 1
11055 1
11053 1
11051 1
11049 1
11047 1
11045 1
11043 1
11041 1
11039...

result:

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

Test #27:

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

input:

1 1

output:

1
1 1

result:

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

Extra Test:

score: 0
Extra Test Passed