QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#42323 | #168. Cube Dividing | afhi | ML | 44ms | 40580kb | C++ | 2.4kb | 2022-08-01 22:16:26 | 2022-08-01 22:16:29 |
Judging History
answer
#include <bits/stdc++.h>
#define SZ(x) (int) x.size()
#define rep(i,a,b) for (int i = a;i < b;i++)
using ll = long long;
template<typename T> using V = std::vector<T>;
using std::cin;
using std::cout;
using std::cerr;
using vb = V<bool>;
using vvb = V<vb>;
using vvvb = V<vvb>;
void solve() {
ll a,b,c,n;
cin>>a>>b>>c>>n;
V<int> xs{0,int(a) - 1},ys{0,int(b) - 1},zs{0,int(c) - 1};
V<int> xx,yy,zz;
for (int i = 0;i < n;i++) {
int x,y,z;
cin>>x>>y>>z;
xx.push_back(x);
yy.push_back(y);
zz.push_back(z);
xs.push_back(x);
xs.push_back(std::max(x - 1,0));
xs.push_back(std::min(x + 1,(int)a - 1));
ys.push_back(y);
ys.push_back(std::max(y - 1,0));
ys.push_back(std::min(y + 1,(int)b - 1));
zs.push_back(z);
zs.push_back(std::max(z - 1,0));
zs.push_back(std::min(z + 1,(int)c - 1));
}
std::sort(xs.begin(),xs.end());
xs.erase(std::unique(xs.begin(),xs.end()),xs.end());
std::sort(ys.begin(),ys.end());
ys.erase(std::unique(ys.begin(),ys.end()),ys.end());
std::sort(zs.begin(),zs.end());
zs.erase(std::unique(zs.begin(),zs.end()),zs.end());
auto index = [] (const V<int>& ids,int v) {
return (int) (std::lower_bound(ids.begin(),ids.end(),v) - ids.begin());
};
vvvb g(SZ(xs),vvb(SZ(ys),vb(SZ(zs))));
for (int i = 0;i < n;i++) {
g[index(xs,xx[i])][index(ys,yy[i])][index(zs,zz[i])] = true;
}
std::function<void(int,int,int)> dfs = [&] (int x,int y,int z) {
if (x < 0 || y < 0 || z < 0 || x >= SZ(xs) || y >= SZ(ys) || z >= SZ(zs)) return;
if (g[x][y][z]) return;
g[x][y][z] = 1;
dfs(x - 1,y,z);
dfs(x + 1,y,z);
dfs(x,y - 1,z);
dfs(x,y + 1,z);
dfs(x,y,z - 1);
dfs(x,y,z + 1);
};
int cnt = 0;
for (int x = 0;x < SZ(xs);x++) {
for (int y = 0;y < SZ(ys);y++) {
for (int z = 0;z < SZ(zs);z++) {
if (!g[x][y][z]) {
dfs(x,y,z);
cnt++;
}
}
}
}
cout<<cnt<<'\n';
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(0);
cin.exceptions(cin.failbit);
#ifdef DEBUG
freopen("input.txt","r",stdin);
#endif
solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3520kb
input:
2 2 2 4 0 0 0 1 1 0 1 0 1 0 1 1
output:
4
result:
ok single line: '4'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
3 3 3 1 1 1 1
output:
1
result:
ok single line: '1'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3740kb
input:
1 1 3 2 0 0 0 0 0 2
output:
1
result:
ok single line: '1'
Test #4:
score: 0
Accepted
time: 3ms
memory: 5888kb
input:
8 60 66 8004 4 49 31 0 38 42 0 45 22 1 19 23 1 36 47 6 9 15 7 55 18 4 24 51 4 34 31 0 31 64 5 24 23 0 48 34 6 30 12 6 41 22 3 6 51 3 43 34 4 49 39 5 31 5 3 36 63 5 37 21 4 11 55 6 53 41 6 51 56 6 42 9 4 59 55 3 30 49 5 15 32 3 59 64 5 7 32 2 42 60 3 0 27 7 5 41 3 34 45 5 39 57 3 24 36 0 16 13 1 55 3...
output:
15
result:
ok single line: '15'
Test #5:
score: 0
Accepted
time: 44ms
memory: 24820kb
input:
97 26 86 6966 67 4 0 63 2 45 30 1 66 37 12 70 54 10 50 61 13 14 82 10 29 76 20 42 66 14 45 8 19 65 2 0 63 42 19 24 11 21 23 65 2 56 65 24 61 33 15 17 51 0 26 2 19 51 7 21 38 53 15 57 73 13 42 38 13 10 78 22 52 83 15 14 68 13 55 50 5 62 70 0 17 56 2 84 93 13 29 44 6 40 58 13 1 15 17 66 38 21 59 2 16 ...
output:
1
result:
ok single line: '1'
Test #6:
score: 0
Accepted
time: 18ms
memory: 4444kb
input:
80 33 9 14465 35 15 4 24 9 4 59 30 8 18 15 6 64 2 4 54 5 6 49 29 1 38 12 8 1 5 4 29 23 0 70 25 5 26 15 2 11 18 7 47 30 5 37 30 3 54 29 1 73 23 5 22 31 8 31 28 7 4 11 2 65 10 8 64 15 1 25 31 7 58 2 5 72 2 2 49 15 3 50 18 5 36 22 1 19 21 7 29 31 6 31 25 0 54 30 3 15 24 1 7 18 7 38 6 7 57 20 8 32 16 0 ...
output:
857
result:
ok single line: '857'
Test #7:
score: 0
Accepted
time: 24ms
memory: 17948kb
input:
52 78 36 9942 35 64 32 40 33 27 9 69 5 24 3 19 46 30 5 40 11 5 47 28 13 15 56 30 1 1 2 43 24 35 48 31 33 49 13 31 35 36 2 25 45 0 14 67 26 30 52 23 1 45 13 3 47 0 7 40 28 21 0 4 19 64 8 32 26 17 19 29 12 7 8 24 42 3 15 21 39 11 35 41 13 47 28 22 18 5 18 40 67 23 36 75 12 35 21 10 16 59 0 25 13 10 51...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 28ms
memory: 40580kb
input:
51 84 87 15969 40 48 55 26 8 25 36 80 48 40 13 16 32 68 60 19 2 45 16 38 38 49 22 70 36 66 76 21 51 86 24 9 80 50 78 36 9 78 50 9 35 2 49 63 83 16 52 0 50 58 76 47 43 66 37 3 71 14 70 86 49 48 66 39 74 80 34 16 24 9 34 54 49 65 54 16 77 17 18 73 84 35 61 45 39 16 38 21 2 46 48 5 7 22 17 64 14 35 38 ...
output:
1
result:
ok single line: '1'
Test #9:
score: 0
Accepted
time: 27ms
memory: 24156kb
input:
58 55 66 17448 53 12 4 23 49 53 53 8 55 57 12 42 51 47 34 20 45 24 48 37 2 0 24 28 33 4 38 1 26 56 57 17 31 6 14 31 36 36 26 33 0 40 24 1 50 37 0 45 15 32 59 40 19 31 32 54 50 29 9 38 32 42 40 21 47 21 46 48 65 21 13 46 50 17 37 5 47 19 56 44 41 15 20 44 10 43 2 37 2 7 39 11 7 34 10 55 8 46 24 18 41...
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 9ms
memory: 5468kb
input:
31 49 22 14484 7 46 11 10 29 1 15 0 8 11 10 3 14 9 5 22 3 4 9 27 18 13 40 13 28 20 7 4 28 12 4 44 21 15 10 17 4 8 12 17 25 15 30 11 0 24 8 6 24 37 2 1 4 6 8 47 16 26 33 14 3 26 14 11 24 13 19 41 15 13 10 19 24 38 12 30 28 13 12 0 9 5 4 6 18 16 20 13 20 13 29 8 21 27 2 18 19 2 19 23 41 7 25 32 2 25 1...
output:
205
result:
ok single line: '205'
Test #11:
score: 0
Accepted
time: 11ms
memory: 13280kb
input:
65 36 42 8374 5 21 22 44 30 18 50 1 35 16 34 37 54 30 4 28 33 8 12 31 24 32 28 15 45 11 27 12 34 15 36 10 6 52 34 7 37 25 32 6 5 3 53 17 32 17 25 6 45 34 13 5 13 41 56 24 27 45 11 9 15 28 0 42 4 14 50 30 40 61 0 26 51 4 31 59 13 1 39 5 12 11 28 9 55 19 25 12 18 14 58 35 4 14 3 41 59 5 34 24 22 22 30...
output:
1
result:
ok single line: '1'
Test #12:
score: 0
Accepted
time: 13ms
memory: 16108kb
input:
24 49 106 3104 7 32 74 19 29 65 8 31 71 10 7 74 0 21 49 16 6 100 11 5 97 6 5 43 21 9 88 6 11 22 16 38 40 4 30 14 2 27 101 17 8 84 12 44 56 6 21 4 19 42 0 10 29 71 1 17 92 16 15 76 0 43 43 23 47 99 14 27 64 17 47 19 0 8 35 19 26 39 23 30 74 13 30 35 19 37 49 4 1 87 12 17 50 22 30 2 14 3 38 23 10 105 ...
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 10ms
memory: 10572kb
input:
14 92 57 6904 10 47 23 12 77 13 12 34 39 4 79 23 3 60 39 2 42 20 2 25 3 2 33 52 6 32 3 2 72 13 2 88 29 6 29 35 13 27 49 1 44 15 0 56 36 4 18 10 2 35 22 5 11 33 6 4 29 8 8 43 7 73 28 2 9 45 6 27 43 0 71 29 9 22 46 8 1 23 3 64 12 12 89 1 11 41 56 12 25 51 13 21 52 10 85 41 6 70 44 3 14 1 8 2 26 9 35 4...
output:
2
result:
ok single line: '2'
Test #14:
score: -100
Memory Limit Exceeded
input:
883659 73120 315984 13620 356561 25749 95618 703272 39911 262803 491727 19022 72760 70333 17287 153234 97287 33099 183707 824073 26403 296847 810501 53197 224664 751333 40590 147652 477481 66750 310506 311528 62992 8676 89763 58901 253720 698886 31886 41966 514225 56832 252776 792753 51105 160521 14...