QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#175373 | #7178. Bishops | zhaohaikun | AC ✓ | 79ms | 20776kb | C++14 | 2.0kb | 2023-09-10 17:42:45 | 2023-09-10 17:42:45 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(x) (int) x.size() - 1
#define all(x) x.begin(), x.end()
#define ms(x, y) memset(x, y, sizeof x)
#define F(i, x, y) for (int i = (x); i <= (y); i++)
#define DF(i, x, y) for (int i = (x); i >= (y); i--)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
template <typename T> inline void chkmax(T& x, T y) { x = max(x, y); }
template <typename T> inline void chkmin(T& x, T y) { x = min(x, y); }
template <typename T> inline void read(T &x) {
x = 0; int f = 1; char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
x *= f;
}
const int N = 2e5 + 20, T = 1e5 + 5;
vector <pair <int, int>> ans;
vector <pair <int, int>> v[N];
int n, m;
signed main() {
cin >> n >> m;
set <int> s;
F(i, 1 - m, n - 1) s.insert(i);//, cout << "~ " << i << endl;
F(i, 2, n + m) {
int l = max(2 - i, i - 2 * m), r = min(i - 2, 2 * n - i);
v[r + T].emplace_back(l, i);
// cout << i << " " << l << " " << r << endl;
// auto it = s.upper_bound(r);
// if (it == s.begin()) continue;
// it--;
// while (it != s.begin() && (*it % 2 + 2) % 2 != i % 2 && *it >= l) it--;
// if (*it >= l && (*it % 2 + 2) % 2 == i % 2) {
// // cout << "# " << *it << endl;
// ans.emplace_back(i, *it);
// s.erase(it);
// }
}
F(ii, 1, 2e5 + 10) {
int i = ii - T;
sort(all(v[ii]));
for (auto [a, b]: v[ii]) {
auto it = s.lower_bound(a);
while (it != s.end() && (*it % 2 + 2) % 2 != b % 2 && *it <= i) it++;
if (*it <= b && (*it % 2 + 2) % 2 == b % 2) {
ans.emplace_back(b, *it);
s.erase(it);
}
}
}
cout << ans.size() << endl;
for (auto [i, j]: ans) cout << (i + j) / 2 << " " << (i - j) / 2 << '\n';
return 0;
// F(i, 1, n)
// F(j, 1, m)
// cout << i + j << " " << i - j << endl;// + n - 1 << endl;// + (2 * n - 1) << endl;
F(i, 2, n + m) {
cout << i << " -> " << max(2 - i, i - 2 * m) << " " << min(i - 2, 2 * n - i) << endl;
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 8300kb
input:
2 5
output:
6 2 5 1 5 2 3 1 3 1 1 2 1
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 4ms
memory: 8332kb
input:
5 5
output:
8 1 1 1 2 5 4 1 3 5 3 1 4 5 2 1 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 70ms
memory: 20680kb
input:
100000 100000
output:
199998 1 1 1 2 100000 99999 1 3 100000 99998 1 4 100000 99997 1 5 100000 99996 1 6 100000 99995 1 7 100000 99994 1 8 100000 99993 1 9 100000 99992 1 10 100000 99991 1 11 100000 99990 1 12 100000 99989 1 13 100000 99988 1 14 100000 99987 1 15 100000 99986 1 16 100000 99985 1 17 100000 99984 1 18 1000...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 76ms
memory: 20772kb
input:
100000 99999
output:
199998 1 1 1 2 100000 99999 1 3 100000 99998 1 4 100000 99997 1 5 100000 99996 1 6 100000 99995 1 7 100000 99994 1 8 100000 99993 1 9 100000 99992 1 10 100000 99991 1 11 100000 99990 1 12 100000 99989 1 13 100000 99988 1 14 100000 99987 1 15 100000 99986 1 16 100000 99985 1 17 100000 99984 1 18 1000...
result:
ok n: 100000, m: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 49ms
memory: 18848kb
input:
100000 50000
output:
149998 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: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 32ms
memory: 16080kb
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: 0
Accepted
time: 38ms
memory: 17656kb
input:
34535 99889
output:
134423 34535 99889 34534 99889 34533 99889 34532 99889 34531 99889 34530 99889 34529 99889 34528 99889 34527 99889 34526 99889 34525 99889 34524 99889 34523 99889 34522 99889 34521 99889 34520 99889 34519 99889 34518 99889 34517 99889 34516 99889 34515 99889 34514 99889 34513 99889 34512 99889 34511...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 33ms
memory: 16512kb
input:
12231 97889
output:
110119 12231 97889 12230 97889 12229 97889 12228 97889 12227 97889 12226 97889 12225 97889 12224 97889 12223 97889 12222 97889 12221 97889 12220 97889 12219 97889 12218 97889 12217 97889 12216 97889 12215 97889 12214 97889 12213 97889 12212 97889 12211 97889 12210 97889 12209 97889 12208 97889 12207...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 25ms
memory: 16464kb
input:
10000 100000
output:
109998 10000 100000 9999 100000 9998 100000 9997 100000 9996 100000 9995 100000 9994 100000 9993 100000 9992 100000 9991 100000 9990 100000 9989 100000 9988 100000 9987 100000 9986 100000 9985 100000 9984 100000 9983 100000 9982 100000 9981 100000 9980 100000 9979 100000 9978 100000 9977 100000 9976...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 29ms
memory: 16080kb
input:
13 99999
output:
100011 13 99999 12 99999 11 99999 10 99999 9 99999 8 99999 7 99999 6 99999 5 99999 4 99999 3 99999 2 99999 1 99999 7 99992 7 99991 7 99990 7 99989 7 99988 7 99987 7 99986 7 99985 7 99984 7 99983 7 99982 7 99981 7 99980 7 99979 7 99978 7 99977 7 99976 7 99975 7 99974 7 99973 7 99972 7 99971 7 99970 7...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 33ms
memory: 16108kb
input:
21 99999
output:
100019 21 99999 20 99999 19 99999 18 99999 17 99999 16 99999 15 99999 14 99999 13 99999 12 99999 11 99999 10 99999 9 99999 8 99999 7 99999 6 99999 5 99999 4 99999 3 99999 2 99999 1 99999 11 99988 11 99987 11 99986 11 99985 11 99984 11 99983 11 99982 11 99981 11 99980 11 99979 11 99978 11 99977 11 99...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 41ms
memory: 19068kb
input:
49999 100000
output:
149998 49999 100000 49998 100000 49997 100000 49996 100000 49995 100000 49994 100000 49993 100000 49992 100000 49991 100000 49990 100000 49989 100000 49988 100000 49987 100000 49986 100000 49985 100000 49984 100000 49983 100000 49982 100000 49981 100000 49980 100000 49979 100000 49978 100000 49977 1...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 53ms
memory: 17676kb
input:
33333 99999
output:
133331 33333 99999 33332 99999 33331 99999 33330 99999 33329 99999 33328 99999 33327 99999 33326 99999 33325 99999 33324 99999 33323 99999 33322 99999 33321 99999 33320 99999 33319 99999 33318 99999 33317 99999 33316 99999 33315 99999 33314 99999 33313 99999 33312 99999 33311 99999 33310 99999 33309...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 34ms
memory: 17164kb
input:
23342 98876
output:
122216 23342 98876 23341 98876 23340 98876 23339 98876 23338 98876 23337 98876 23336 98876 23335 98876 23334 98876 23333 98876 23332 98876 23331 98876 23330 98876 23329 98876 23328 98876 23327 98876 23326 98876 23325 98876 23324 98876 23323 98876 23322 98876 23321 98876 23320 98876 23319 98876 23318...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 30ms
memory: 18636kb
input:
56713 91234
output:
147946 56713 91234 56712 91234 56711 91234 56710 91234 56709 91234 56708 91234 56707 91234 56706 91234 56705 91234 56704 91234 56703 91234 56702 91234 56701 91234 56700 91234 56699 91234 56698 91234 56697 91234 56696 91234 56695 91234 56694 91234 56693 91234 56692 91234 56691 91234 56690 91234 56689...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 79ms
memory: 20776kb
input:
99995 99995
output:
199988 1 1 1 2 99995 99994 1 3 99995 99993 1 4 99995 99992 1 5 99995 99991 1 6 99995 99990 1 7 99995 99989 1 8 99995 99988 1 9 99995 99987 1 10 99995 99986 1 11 99995 99985 1 12 99995 99984 1 13 99995 99983 1 14 99995 99982 1 15 99995 99981 1 16 99995 99980 1 17 99995 99979 1 18 99995 99978 1 19 999...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 20ms
memory: 13280kb
input:
12345 54321
output:
66665 12345 54321 12344 54321 12343 54321 12342 54321 12341 54321 12340 54321 12339 54321 12338 54321 12337 54321 12336 54321 12335 54321 12334 54321 12333 54321 12332 54321 12331 54321 12330 54321 12329 54321 12328 54321 12327 54321 12326 54321 12325 54321 12324 54321 12323 54321 12322 54321 12321 ...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 58ms
memory: 19708kb
input:
90000 92000
output:
181998 90000 92000 89999 92000 89998 92000 89997 92000 89996 92000 89995 92000 89994 92000 89993 92000 89992 92000 89991 92000 89990 92000 89989 92000 89988 92000 89987 92000 89986 92000 89985 92000 89984 92000 89983 92000 89982 92000 89981 92000 89980 92000 89979 92000 89978 92000 89977 92000 89976...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 30ms
memory: 14468kb
input:
10000 70000
output:
79998 10000 70000 9999 70000 9998 70000 9997 70000 9996 70000 9995 70000 9994 70000 9993 70000 9992 70000 9991 70000 9990 70000 9989 70000 9988 70000 9987 70000 9986 70000 9985 70000 9984 70000 9983 70000 9982 70000 9981 70000 9980 70000 9979 70000 9978 70000 9977 70000 9976 70000 9975 70000 9974 70...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 27ms
memory: 14184kb
input:
10000 70001
output:
80000 10000 70001 9999 70001 9998 70001 9997 70001 9996 70001 9995 70001 9994 70001 9993 70001 9992 70001 9991 70001 9990 70001 9989 70001 9988 70001 9987 70001 9986 70001 9985 70001 9984 70001 9983 70001 9982 70001 9981 70001 9980 70001 9979 70001 9978 70001 9977 70001 9976 70001 9975 70001 9974 70...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 25ms
memory: 14952kb
input:
10000 80000
output:
89998 10000 80000 9999 80000 9998 80000 9997 80000 9996 80000 9995 80000 9994 80000 9993 80000 9992 80000 9991 80000 9990 80000 9989 80000 9988 80000 9987 80000 9986 80000 9985 80000 9984 80000 9983 80000 9982 80000 9981 80000 9980 80000 9979 80000 9978 80000 9977 80000 9976 80000 9975 80000 9974 80...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 30ms
memory: 15248kb
input:
10000 80001
output:
90000 10000 80001 9999 80001 9998 80001 9997 80001 9996 80001 9995 80001 9994 80001 9993 80001 9992 80001 9991 80001 9990 80001 9989 80001 9988 80001 9987 80001 9986 80001 9985 80001 9984 80001 9983 80001 9982 80001 9981 80001 9980 80001 9979 80001 9978 80001 9977 80001 9976 80001 9975 80001 9974 80...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 30ms
memory: 15024kb
input:
10000 80002
output:
90000 10000 80002 9999 80002 9998 80002 9997 80002 9996 80002 9995 80002 9994 80002 9993 80002 9992 80002 9991 80002 9990 80002 9989 80002 9988 80002 9987 80002 9986 80002 9985 80002 9984 80002 9983 80002 9982 80002 9981 80002 9980 80002 9979 80002 9978 80002 9977 80002 9976 80002 9975 80002 9974 80...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 21ms
memory: 15180kb
input:
10000 79999
output:
89998 10000 79999 9999 79999 9998 79999 9997 79999 9996 79999 9995 79999 9994 79999 9993 79999 9992 79999 9991 79999 9990 79999 9989 79999 9988 79999 9987 79999 9986 79999 9985 79999 9984 79999 9983 79999 9982 79999 9981 79999 9980 79999 9979 79999 9978 79999 9977 79999 9976 79999 9975 79999 9974 79...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 34ms
memory: 15016kb
input:
10000 79998
output:
89996 10000 79998 9999 79998 9998 79998 9997 79998 9996 79998 9995 79998 9994 79998 9993 79998 9992 79998 9991 79998 9990 79998 9989 79998 9988 79998 9987 79998 9986 79998 9985 79998 9984 79998 9983 79998 9982 79998 9981 79998 9980 79998 9979 79998 9978 79998 9977 79998 9976 79998 9975 79998 9974 79...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 33ms
memory: 16668kb
input:
11111 100000
output:
111110 11111 100000 11110 100000 11109 100000 11108 100000 11107 100000 11106 100000 11105 100000 11104 100000 11103 100000 11102 100000 11101 100000 11100 100000 11099 100000 11098 100000 11097 100000 11096 100000 11095 100000 11094 100000 11093 100000 11092 100000 11091 100000 11090 100000 11089 1...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 3ms
memory: 8236kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed