QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232690 | #7178. Bishops | ikefumy | AC ✓ | 80ms | 15872kb | C++20 | 4.3kb | 2023-10-30 19:43:55 | 2023-10-30 19:43:55 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
if(x > y) {
x = y;
return true;
} else return false;
}
template<class T> bool chmax(T& x, T y){
if(x < y) {
x = y;
return true;
} else return false;
}
// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )
#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )
#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)
// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)
// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)
// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)
// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)
// for_earh
#define fore(e, v) for (auto&& e : v)
// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
int n, m;
pii upper_right(pii p) {
auto [x, y] = p;
int d = min(x, m - 1 - y);
return {x - d, y + d};
}
pii lower_right(pii p) {
auto [x, y] = p;
int d = min(n - 1 - x, m - 1 - y);
return {x + d, y + d};
}
// 左側からのidx
int get_idx(pii p) {
auto [x, y] = p;
if (x == n - 1) return n - 1 + m - 1 - y;
else return x;
}
pii get_point(int i1, int i2) {
int x, y;
if (i1 < n) x = i1, y = 0;
else x = n - 1, y = i1 - n + 1;
int mx = get_idx(lower_right({x, y}));
int d = (mx - i2) / 2;
return {x - d, y + d};
}
// 番号 区間
vector<pii> get_matching(vector<pair<int, pii>> elem) {
// 番号 終端
vector<vector<pii>> query(n + m - 1);
int parity = 0;
fore (e, elem) {
auto [idx, p] = e;
auto [l, r] = p;
query[l].push_back({r, idx});
parity = l % 2;
}
vector<pii> ret;
int nw = parity;
priority_queue<pii, vector<pii>, greater<pii>> pq;
rep (i, nw, n + m - 1, 2) {
fore (u, query[i]) pq.push(u);
while (!pq.empty()) {
auto [r, idx] = pq.top();
if (r < i) pq.pop();
else break;
}
if (!pq.empty()) {
ret.push_back({pq.top().second, i});
pq.pop();
}
}
return ret;
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
cin >> n >> m;
int dx = 1, dy = 0, x = 0, y = 0;
vector<pair<int, pii>> edges[2];
rep (_, n + m - 1) {
if (x == n - 1) dx = 0, dy = 1;
auto [x1, y1] = lower_right(upper_right({x, y}));
auto [x2, y2] = lower_right({x, y});
edges[(x + y) % 2].push_back({x + y, {get_idx(lower_right(upper_right({x, y}))), get_idx(lower_right({x, y}))}});
x += dx, y += dy;
}
vector<pii> ans;
rep (i, 2) {
auto v = get_matching(edges[i]);
ans.insert(ans.end(), all(v));
}
cout << ans.size() << endl;
fore (u, ans) {
auto [x, y] = get_point(u.first, u.second);
cout << x + 1 << ' ' << y + 1 << endl;
}
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3840kb
input:
2 5
output:
6 1 5 1 3 1 1 2 5 2 3 2 1
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
5 5
output:
8 1 5 1 3 1 1 5 3 1 4 1 2 5 4 5 2
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 76ms
memory: 15652kb
input:
100000 100000
output:
199998 1 99999 1 99997 1 99995 1 99993 1 99991 1 99989 1 99987 1 99985 1 99983 1 99981 1 99979 1 99977 1 99975 1 99973 1 99971 1 99969 1 99967 1 99965 1 99963 1 99961 1 99959 1 99957 1 99955 1 99953 1 99951 1 99949 1 99947 1 99945 1 99943 1 99941 1 99939 1 99937 1 99935 1 99933 1 99931 1 99929 1 999...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 80ms
memory: 15688kb
input:
100000 99999
output:
199998 1 99999 1 99997 1 99995 1 99993 1 99991 1 99989 1 99987 1 99985 1 99983 1 99981 1 99979 1 99977 1 99975 1 99973 1 99971 1 99969 1 99967 1 99965 1 99963 1 99961 1 99959 1 99957 1 99955 1 99953 1 99951 1 99949 1 99947 1 99945 1 99943 1 99941 1 99939 1 99937 1 99935 1 99933 1 99931 1 99929 1 999...
result:
ok n: 100000, m: 99999, bishops: 199998
Test #5:
score: 0
Accepted
time: 48ms
memory: 13264kb
input:
100000 50000
output:
149998 1 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 499...
result:
ok n: 100000, m: 50000, bishops: 149998
Test #6:
score: 0
Accepted
time: 36ms
memory: 10264kb
input:
1 100000
output:
100000 1 99999 1 99997 1 99995 1 99993 1 99991 1 99989 1 99987 1 99985 1 99983 1 99981 1 99979 1 99977 1 99975 1 99973 1 99971 1 99969 1 99967 1 99965 1 99963 1 99961 1 99959 1 99957 1 99955 1 99953 1 99951 1 99949 1 99947 1 99945 1 99943 1 99941 1 99939 1 99937 1 99935 1 99933 1 99931 1 99929 1 999...
result:
ok n: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 41ms
memory: 12712kb
input:
34535 99889
output:
134423 1 99889 3 99889 5 99889 7 99889 9 99889 11 99889 13 99889 15 99889 17 99889 19 99889 21 99889 23 99889 25 99889 27 99889 29 99889 31 99889 33 99889 35 99889 37 99889 39 99889 41 99889 43 99889 45 99889 47 99889 49 99889 51 99889 53 99889 55 99889 57 99889 59 99889 61 99889 63 99889 65 99889 6...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 48ms
memory: 10612kb
input:
12231 97889
output:
110119 1 97889 3 97889 5 97889 7 97889 9 97889 11 97889 13 97889 15 97889 17 97889 19 97889 21 97889 23 97889 25 97889 27 97889 29 97889 31 97889 33 97889 35 97889 37 97889 39 97889 41 97889 43 97889 45 97889 47 97889 49 97889 51 97889 53 97889 55 97889 57 97889 59 97889 61 97889 63 97889 65 97889 6...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 28ms
memory: 10620kb
input:
10000 100000
output:
109998 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 60 1000...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 19ms
memory: 10152kb
input:
13 99999
output:
100011 1 99999 3 99999 5 99999 7 99999 9 99999 11 99999 13 99999 7 99991 7 99989 7 99987 7 99985 7 99983 7 99981 7 99979 7 99977 7 99975 7 99973 7 99971 7 99969 7 99967 7 99965 7 99963 7 99961 7 99959 7 99957 7 99955 7 99953 7 99951 7 99949 7 99947 7 99945 7 99943 7 99941 7 99939 7 99937 7 99935 7 9...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 46ms
memory: 10184kb
input:
21 99999
output:
100019 1 99999 3 99999 5 99999 7 99999 9 99999 11 99999 13 99999 15 99999 17 99999 19 99999 21 99999 11 99987 11 99985 11 99983 11 99981 11 99979 11 99977 11 99975 11 99973 11 99971 11 99969 11 99967 11 99965 11 99963 11 99961 11 99959 11 99957 11 99955 11 99953 11 99951 11 99949 11 99947 11 99945 1...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 56ms
memory: 13572kb
input:
49999 100000
output:
149998 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 60 1000...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 55ms
memory: 12592kb
input:
33333 99999
output:
133331 1 99999 3 99999 5 99999 7 99999 9 99999 11 99999 13 99999 15 99999 17 99999 19 99999 21 99999 23 99999 25 99999 27 99999 29 99999 31 99999 33 99999 35 99999 37 99999 39 99999 41 99999 43 99999 45 99999 47 99999 49 99999 51 99999 53 99999 55 99999 57 99999 59 99999 61 99999 63 99999 65 99999 6...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 28ms
memory: 11248kb
input:
23342 98876
output:
122216 2 98876 4 98876 6 98876 8 98876 10 98876 12 98876 14 98876 16 98876 18 98876 20 98876 22 98876 24 98876 26 98876 28 98876 30 98876 32 98876 34 98876 36 98876 38 98876 40 98876 42 98876 44 98876 46 98876 48 98876 50 98876 52 98876 54 98876 56 98876 58 98876 60 98876 62 98876 64 98876 66 98876 ...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 51ms
memory: 13228kb
input:
56713 91234
output:
147946 2 91234 4 91234 6 91234 8 91234 10 91234 12 91234 14 91234 16 91234 18 91234 20 91234 22 91234 24 91234 26 91234 28 91234 30 91234 32 91234 34 91234 36 91234 38 91234 40 91234 42 91234 44 91234 46 91234 48 91234 50 91234 52 91234 54 91234 56 91234 58 91234 60 91234 62 91234 64 91234 66 91234 ...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 64ms
memory: 15872kb
input:
99995 99995
output:
199988 1 99995 1 99993 1 99991 1 99989 1 99987 1 99985 1 99983 1 99981 1 99979 1 99977 1 99975 1 99973 1 99971 1 99969 1 99967 1 99965 1 99963 1 99961 1 99959 1 99957 1 99955 1 99953 1 99951 1 99949 1 99947 1 99945 1 99943 1 99941 1 99939 1 99937 1 99935 1 99933 1 99931 1 99929 1 99927 1 99925 1 999...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 19ms
memory: 7836kb
input:
12345 54321
output:
66665 1 54321 3 54321 5 54321 7 54321 9 54321 11 54321 13 54321 15 54321 17 54321 19 54321 21 54321 23 54321 25 54321 27 54321 29 54321 31 54321 33 54321 35 54321 37 54321 39 54321 41 54321 43 54321 45 54321 47 54321 49 54321 51 54321 53 54321 55 54321 57 54321 59 54321 61 54321 63 54321 65 54321 67...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 56ms
memory: 14524kb
input:
90000 92000
output:
181998 2 92000 4 92000 6 92000 8 92000 10 92000 12 92000 14 92000 16 92000 18 92000 20 92000 22 92000 24 92000 26 92000 28 92000 30 92000 32 92000 34 92000 36 92000 38 92000 40 92000 42 92000 44 92000 46 92000 48 92000 50 92000 52 92000 54 92000 56 92000 58 92000 60 92000 62 92000 64 92000 66 92000 ...
result:
ok n: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 28ms
memory: 8680kb
input:
10000 70000
output:
79998 2 70000 4 70000 6 70000 8 70000 10 70000 12 70000 14 70000 16 70000 18 70000 20 70000 22 70000 24 70000 26 70000 28 70000 30 70000 32 70000 34 70000 36 70000 38 70000 40 70000 42 70000 44 70000 46 70000 48 70000 50 70000 52 70000 54 70000 56 70000 58 70000 60 70000 62 70000 64 70000 66 70000 6...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 19ms
memory: 8744kb
input:
10000 70001
output:
80000 1 70001 3 70001 5 70001 7 70001 9 70001 11 70001 13 70001 15 70001 17 70001 19 70001 21 70001 23 70001 25 70001 27 70001 29 70001 31 70001 33 70001 35 70001 37 70001 39 70001 41 70001 43 70001 45 70001 47 70001 49 70001 51 70001 53 70001 55 70001 57 70001 59 70001 61 70001 63 70001 65 70001 67...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 27ms
memory: 9308kb
input:
10000 80000
output:
89998 2 80000 4 80000 6 80000 8 80000 10 80000 12 80000 14 80000 16 80000 18 80000 20 80000 22 80000 24 80000 26 80000 28 80000 30 80000 32 80000 34 80000 36 80000 38 80000 40 80000 42 80000 44 80000 46 80000 48 80000 50 80000 52 80000 54 80000 56 80000 58 80000 60 80000 62 80000 64 80000 66 80000 6...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 35ms
memory: 9308kb
input:
10000 80001
output:
90000 1 80001 3 80001 5 80001 7 80001 9 80001 11 80001 13 80001 15 80001 17 80001 19 80001 21 80001 23 80001 25 80001 27 80001 29 80001 31 80001 33 80001 35 80001 37 80001 39 80001 41 80001 43 80001 45 80001 47 80001 49 80001 51 80001 53 80001 55 80001 57 80001 59 80001 61 80001 63 80001 65 80001 67...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 27ms
memory: 9440kb
input:
10000 80002
output:
90000 2 80002 4 80002 6 80002 8 80002 10 80002 12 80002 14 80002 16 80002 18 80002 20 80002 22 80002 24 80002 26 80002 28 80002 30 80002 32 80002 34 80002 36 80002 38 80002 40 80002 42 80002 44 80002 46 80002 48 80002 50 80002 52 80002 54 80002 56 80002 58 80002 60 80002 62 80002 64 80002 66 80002 6...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 52ms
memory: 9308kb
input:
10000 79999
output:
89998 1 79999 3 79999 5 79999 7 79999 9 79999 11 79999 13 79999 15 79999 17 79999 19 79999 21 79999 23 79999 25 79999 27 79999 29 79999 31 79999 33 79999 35 79999 37 79999 39 79999 41 79999 43 79999 45 79999 47 79999 49 79999 51 79999 53 79999 55 79999 57 79999 59 79999 61 79999 63 79999 65 79999 67...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 28ms
memory: 9444kb
input:
10000 79998
output:
89996 2 79998 4 79998 6 79998 8 79998 10 79998 12 79998 14 79998 16 79998 18 79998 20 79998 22 79998 24 79998 26 79998 28 79998 30 79998 32 79998 34 79998 36 79998 38 79998 40 79998 42 79998 44 79998 46 79998 48 79998 50 79998 52 79998 54 79998 56 79998 58 79998 60 79998 62 79998 64 79998 66 79998 6...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 55ms
memory: 10640kb
input:
11111 100000
output:
111110 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 60 1000...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed