QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#197389 | #7178. Bishops | mendicillin2# | AC ✓ | 47ms | 10304kb | C++17 | 3.5kb | 2023-10-02 15:22:41 | 2023-10-02 15:22:42 |
Judging History
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