QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#167698 | #7178. Bishops | ucup-team045# | AC ✓ | 136ms | 51728kb | C++20 | 3.3kb | 2023-09-07 16:40:26 | 2023-09-07 16:40:27 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<set>
#include<limits>
using namespace std;
using LL = long long;
const int maxn = 1e6 + 5, maxm = 2e6 + 5;
template<typename flow_t>
struct MaxFlow{
const flow_t INF = numeric_limits<flow_t>::max() / 2;
int h[maxn], e[maxm], ne[maxm], idx;
flow_t f[maxm];
int cur[maxn], q[maxn], d[maxn];
int V, S, T;
void init(int v, int s, int t){
for(int i = 0; i <= v; i++) h[i] = -1;
idx = 0;
V = v, S = s, T = t;
}
void add(int a, int b, flow_t c, flow_t d = 0){
e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
e[idx] = a, f[idx] = d, ne[idx] = h[b], h[b] = idx++;
}
bool bfs(){
for(int i = 0; i <= V; i++) d[i] = -1;
int hh = 0, tt = -1;
q[++tt] = S, d[S] = 0, cur[S] = h[S];
while(hh <= tt){
int t = q[hh++];
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if (d[j] == -1 && f[i]){
d[j] = d[t] + 1;
cur[j] = h[j];
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
flow_t find(int u, flow_t limit){
if (u == T) return limit;
flow_t flow = 0;
// start from cur[u] instead of h[u] <- important
for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]){
flow_t t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
else f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
flow_t dinic(){
flow_t res = 0, flow;
while(bfs()) while(flow = find(S, INF)) res += flow;
return res;
}
};
MaxFlow<int> flow;
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
const int cnt = n + m - 1;
int s = 0, t = 2 * cnt + 1;
flow.init(2 * cnt + 1, s, t);
for(int i = 1; i <= cnt; i++){
flow.add(s, i, 1);
flow.add(i + cnt, t, 1);
}
auto add = [&](int x, int y){
int l = x + y - 1;
int r = m - y + 1 + x - 1;
flow.add(l, r + cnt, 1);
};
for(int i = 1; i <= m; i++){
add(1, i);
add(n, i);
}
for(int i = 2; i <= n - 1; i++){
add(i, 1);
add(i, m);
}
flow.dinic();
auto get = [&](int x, int y){
int s1 = x + 1;
int s2 = y - m;
x = (s1 + s2) / 2;
y = s1 - x;
return make_pair(x, y);
};
vector<pair<int, int> > ans;
for(int x = 1; x <= cnt; x++){
for(int i = flow.h[x]; ~i; i = flow.ne[i]){
int j = flow.e[i];
if (j > cnt && j <= 2 * cnt && !flow.f[i]){
ans.push_back(get(x, j - cnt));
}
}
}
cout << ans.size() << '\n';
for(auto [x, y] : ans)
cout << x << ' ' << y << '\n';
}
这程序好像有点Bug,我给组数据试试?
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 15868kb
input:
2 5
output:
6 1 1 2 1 1 3 2 3 1 5 2 5
result:
ok n: 2, m: 5, bishops: 6
Test #2:
score: 0
Accepted
time: 1ms
memory: 15744kb
input:
5 5
output:
8 2 1 3 1 4 1 1 5 2 5 3 5 4 5 5 5
result:
ok n: 5, m: 5, bishops: 8
Test #3:
score: 0
Accepted
time: 32ms
memory: 41544kb
input:
100000 100000
output:
199998 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 61 1 6...
result:
ok n: 100000, m: 100000, bishops: 199998
Test #4:
score: 0
Accepted
time: 39ms
memory: 51728kb
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: 19ms
memory: 39008kb
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: 19ms
memory: 28948kb
input:
1 100000
output:
100000 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: 1, m: 100000, bishops: 100000
Test #7:
score: 0
Accepted
time: 136ms
memory: 41728kb
input:
34535 99889
output:
134423 1 1 1 2 1 3 4 1 5 1 1 6 1 7 8 1 9 1 1 10 11 1 12 1 1 13 1 14 15 1 16 1 1 17 1 18 1 19 20 1 21 1 1 22 1 23 24 1 25 1 1 26 1 27 28 1 1 29 1 30 31 1 32 1 1 33 1 34 35 1 36 1 37 1 1 38 1 39 40 1 41 1 1 42 1 43 44 1 45 1 1 46 47 1 48 1 1 49 1 50 51 1 52 1 1 53 1 54 1 55 56 1 57 1 1 58 1 59 60 1 61...
result:
ok n: 34535, m: 99889, bishops: 134423
Test #8:
score: 0
Accepted
time: 97ms
memory: 31820kb
input:
12231 97889
output:
110119 1 1 1 2 1 3 4 1 5 1 1 6 1 7 8 1 9 1 1 10 11 1 12 1 1 13 1 14 15 1 16 1 1 17 1 18 19 1 20 1 21 1 1 22 1 23 24 1 25 1 1 26 1 27 28 1 29 1 1 30 31 1 32 1 1 33 1 34 35 1 36 1 1 37 1 38 39 1 40 1 41 1 1 42 1 43 44 1 45 1 1 46 1 47 48 1 1 49 1 50 51 1 52 1 1 53 1 54 55 1 56 1 1 57 1 58 1 59 60 1 61...
result:
ok n: 12231, m: 97889, bishops: 110119
Test #9:
score: 0
Accepted
time: 29ms
memory: 30144kb
input:
10000 100000
output:
109998 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 56 1 57 1 58 1 59 1 60 1 61 1 6...
result:
ok n: 10000, m: 100000, bishops: 109998
Test #10:
score: 0
Accepted
time: 11ms
memory: 33332kb
input:
13 99999
output:
100011 1 1 2 1 3 1 1 4 5 1 6 1 7 1 1 8 9 1 10 1 11 1 1 12 13 1 13 2 1 15 1 16 1 17 13 6 1 19 1 20 1 21 13 10 1 23 1 24 1 25 13 14 13 15 1 28 13 17 13 18 13 19 1 32 13 21 13 22 13 23 1 36 13 25 13 26 1 39 1 40 1 41 13 30 1 43 1 44 1 45 13 34 1 47 1 48 1 49 13 38 13 39 1 52 13 41 13 42 13 43 1 56 13 4...
result:
ok n: 13, m: 99999, bishops: 100011
Test #11:
score: 0
Accepted
time: 39ms
memory: 31684kb
input:
21 99999
output:
100019 1 1 2 1 3 1 1 4 1 5 6 1 7 1 1 8 1 9 10 1 11 1 1 12 1 13 14 1 15 1 1 16 1 17 18 1 19 1 1 20 21 1 21 2 1 23 1 24 21 5 21 6 1 27 1 28 21 9 21 10 1 31 1 32 21 13 21 14 1 35 1 36 21 17 21 18 1 39 1 40 1 41 21 22 21 23 1 44 1 45 21 26 21 27 1 48 1 49 21 30 21 31 1 52 1 53 21 34 21 35 1 56 1 57 21 3...
result:
ok n: 21, m: 99999, bishops: 100019
Test #12:
score: 0
Accepted
time: 30ms
memory: 36544kb
input:
49999 100000
output:
149998 1 1 1 2 1 3 1 4 5 1 6 1 7 1 1 8 1 9 1 10 11 1 12 1 13 1 1 14 1 15 1 16 17 1 18 1 19 1 1 20 1 21 1 22 23 1 24 1 25 1 1 26 1 27 1 28 29 1 30 1 31 1 1 32 1 33 1 34 35 1 36 1 37 1 1 38 1 39 1 40 41 1 42 1 43 1 1 44 1 45 1 46 47 1 48 1 49 1 1 50 1 51 1 52 53 1 54 1 55 1 1 56 1 57 1 58 59 1 60 1 61...
result:
ok n: 49999, m: 100000, bishops: 149998
Test #13:
score: 0
Accepted
time: 25ms
memory: 35812kb
input:
33333 99999
output:
133331 1 1 2 1 3 1 1 4 5 1 6 1 7 1 1 8 9 1 10 1 11 1 1 12 13 1 14 1 15 1 1 16 17 1 18 1 19 1 1 20 21 1 22 1 23 1 1 24 25 1 26 1 27 1 1 28 29 1 30 1 31 1 1 32 33 1 34 1 35 1 1 36 37 1 38 1 39 1 1 40 41 1 42 1 43 1 1 44 45 1 46 1 47 1 1 48 49 1 50 1 51 1 1 52 53 1 54 1 55 1 1 56 57 1 58 1 59 1 1 60 61...
result:
ok n: 33333, m: 99999, bishops: 133331
Test #14:
score: 0
Accepted
time: 77ms
memory: 34948kb
input:
23342 98876
output:
122216 1 1 1 2 1 3 4 1 5 1 6 1 1 7 1 8 9 1 10 1 11 1 1 12 1 13 14 1 15 1 16 1 1 17 1 18 19 1 20 1 21 1 1 22 1 23 24 1 25 1 26 1 1 27 1 28 29 1 30 1 31 1 1 32 1 33 34 1 35 1 36 1 1 37 1 38 39 1 40 1 41 1 1 42 1 43 44 1 45 1 46 1 1 47 1 48 49 1 50 1 51 1 1 52 1 53 54 1 55 1 56 1 1 57 1 58 59 1 60 1 61...
result:
ok n: 23342, m: 98876, bishops: 122216
Test #15:
score: 0
Accepted
time: 106ms
memory: 34252kb
input:
56713 91234
output:
147946 1 1 2 1 3 1 1 4 1 5 1 6 1 7 8 1 9 1 10 1 1 11 1 12 13 1 14 1 15 1 16 1 1 17 1 18 1 19 20 1 21 1 1 22 1 23 1 24 25 1 26 1 27 1 28 1 1 29 1 30 31 1 32 1 33 1 1 34 1 35 1 36 1 37 38 1 39 1 40 1 1 41 1 42 43 1 44 1 45 1 46 1 1 47 1 48 1 49 50 1 51 1 1 52 1 53 1 54 55 1 56 1 57 1 58 1 1 59 1 60 61...
result:
ok n: 56713, m: 91234, bishops: 147946
Test #16:
score: 0
Accepted
time: 31ms
memory: 41596kb
input:
99995 99995
output:
199988 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 61 1 6...
result:
ok n: 99995, m: 99995, bishops: 199988
Test #17:
score: 0
Accepted
time: 29ms
memory: 25168kb
input:
12345 54321
output:
66665 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 1 18 1 19 1 20 1 21 1 22 1 23 1 24 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 42 1 43 1 44 1 45 1 46 1 47 1 48 1 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 58 1 59 1 60 1 61 ...
result:
ok n: 12345, m: 54321, bishops: 66665
Test #18:
score: 0
Accepted
time: 35ms
memory: 43368kb
input:
90000 92000
output:
181998 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: 90000, m: 92000, bishops: 181998
Test #19:
score: 0
Accepted
time: 33ms
memory: 27980kb
input:
10000 70000
output:
79998 1 1 2 1 3 1 4 1 1 5 1 6 7 1 8 1 9 1 10 1 1 11 1 12 13 1 14 1 15 1 16 1 1 17 1 18 19 1 20 1 21 1 22 1 1 23 1 24 25 1 26 1 27 1 28 1 1 29 1 30 31 1 32 1 33 1 34 1 1 35 1 36 37 1 38 1 39 1 40 1 1 41 1 42 43 1 44 1 45 1 46 1 1 47 1 48 49 1 50 1 51 1 52 1 1 53 1 54 55 1 56 1 57 1 58 1 1 59 1 60 61 ...
result:
ok n: 10000, m: 70000, bishops: 79998
Test #20:
score: 0
Accepted
time: 23ms
memory: 27772kb
input:
10000 70001
output:
80000 1 1 2 1 3 1 4 1 1 5 1 6 1 7 8 1 9 1 10 1 11 1 1 12 1 13 1 14 15 1 16 1 17 1 18 1 1 19 1 20 1 21 22 1 23 1 24 1 25 1 1 26 1 27 1 28 29 1 30 1 31 1 32 1 1 33 1 34 1 35 36 1 37 1 38 1 39 1 1 40 1 41 1 42 43 1 44 1 45 1 46 1 1 47 1 48 1 49 50 1 51 1 52 1 53 1 1 54 1 55 1 56 57 1 58 1 59 1 60 1 1 6...
result:
ok n: 10000, m: 70001, bishops: 80000
Test #21:
score: 0
Accepted
time: 39ms
memory: 30772kb
input:
10000 80000
output:
89998 1 1 1 2 3 1 1 4 6 1 1 7 1 8 9 1 1 10 1 11 12 1 1 13 14 1 15 1 1 16 17 1 1 18 1 19 20 1 1 21 1 22 23 1 1 24 1 25 26 1 1 27 28 1 29 1 1 30 31 1 1 32 1 33 34 1 1 35 1 36 37 1 1 38 1 39 40 1 1 41 42 1 43 1 1 44 45 1 1 46 1 47 48 1 1 49 1 50 51 1 1 52 1 53 54 1 1 55 56 1 57 1 1 58 59 1 1 60 1 61 62...
result:
ok n: 10000, m: 80000, bishops: 89998
Test #22:
score: 0
Accepted
time: 43ms
memory: 30736kb
input:
10000 80001
output:
90000 1 1 1 2 3 1 1 4 5 1 1 6 7 1 1 8 1 9 10 1 1 11 12 1 1 13 14 1 1 15 16 1 17 1 1 18 19 1 1 20 21 1 1 22 23 1 1 24 1 25 26 1 1 27 28 1 1 29 30 1 1 31 32 1 33 1 1 34 35 1 1 36 37 1 1 38 39 1 1 40 1 41 42 1 1 43 44 1 1 45 46 1 1 47 48 1 49 1 1 50 51 1 1 52 53 1 1 54 55 1 1 56 1 57 58 1 1 59 60 1 1 6...
result:
ok n: 10000, m: 80001, bishops: 90000
Test #23:
score: 0
Accepted
time: 14ms
memory: 29872kb
input:
10000 80002
output:
90000 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 56 1 57 1 58 1 59 1 60 1 61 1 62...
result:
ok n: 10000, m: 80002, bishops: 90000
Test #24:
score: 0
Accepted
time: 33ms
memory: 27960kb
input:
10000 79999
output:
89998 1 1 2 1 3 1 4 1 1 5 1 6 1 7 8 1 9 1 1 10 1 11 1 12 13 1 14 1 15 1 16 1 1 17 1 18 1 19 20 1 21 1 1 22 1 23 1 24 25 1 26 1 27 1 28 1 1 29 1 30 1 31 32 1 33 1 1 34 1 35 1 36 37 1 38 1 39 1 40 1 1 41 1 42 1 43 44 1 45 1 1 46 1 47 1 48 49 1 50 1 51 1 52 1 1 53 1 54 1 55 56 1 57 1 1 58 1 59 1 60 61 ...
result:
ok n: 10000, m: 79999, bishops: 89998
Test #25:
score: 0
Accepted
time: 27ms
memory: 28180kb
input:
10000 79998
output:
89996 1 2 1 3 1 4 1 5 1 6 7 1 8 1 9 1 10 1 1 11 1 12 1 13 1 14 1 15 1 16 17 1 18 1 19 1 20 1 1 21 1 22 1 23 1 24 1 25 1 26 27 1 28 1 29 1 30 1 1 31 1 32 1 33 1 34 1 35 1 36 37 1 38 1 39 1 40 1 1 41 1 42 1 43 1 44 1 45 1 46 47 1 48 1 49 1 50 1 1 51 1 52 1 53 1 54 1 55 1 56 57 1 58 1 59 1 60 1 1 61 1 ...
result:
ok n: 10000, m: 79998, bishops: 89996
Test #26:
score: 0
Accepted
time: 35ms
memory: 34148kb
input:
11111 100000
output:
111110 1 1 2 1 3 1 4 1 5 1 1 6 1 7 1 8 1 9 10 1 11 1 12 1 13 1 14 1 1 15 1 16 1 17 1 18 19 1 20 1 21 1 22 1 23 1 1 24 1 25 1 26 1 27 28 1 29 1 30 1 31 1 32 1 1 33 1 34 1 35 1 36 37 1 38 1 39 1 40 1 41 1 1 42 1 43 1 44 1 45 46 1 47 1 48 1 49 1 50 1 1 51 1 52 1 53 1 54 55 1 56 1 57 1 58 1 59 1 1 60 1 ...
result:
ok n: 11111, m: 100000, bishops: 111110
Test #27:
score: 0
Accepted
time: 0ms
memory: 16100kb
input:
1 1
output:
1 1 1
result:
ok n: 1, m: 1, bishops: 1
Extra Test:
score: 0
Extra Test Passed