QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#176519 | #6324. Expanded Hull | ucup-team1209 | WA | 809ms | 5956kb | C++20 | 2.5kb | 2023-09-11 19:07:56 | 2023-09-11 19:07:56 |
Judging History
answer
#include<bits/stdc++.h>
using std::cin;
using std::cout;
using ll = long long;
using u64 = unsigned long long;
void IOinit() {
std::ios::sync_with_stdio(false), cin.tie(0);
#ifdef zqj
freopen("1.in", "r", stdin);
#endif
}
struct vec3 {
int x, y, z;
bool operator < (const vec3 & rhs) const {
if(x != rhs.x) return x < rhs.x;
if(y != rhs.y) return y < rhs.y;
return z < rhs.z;
}
};
ll K;
struct plane {
vec3 x; int v;
};
vec3 operator - (vec3 x, vec3 y) { return {x.x - y.x, x.y - y.y, x.z - y.z}; }
vec3 operator + (vec3 x, vec3 y) { return {x.x + y.x, x.y + y.y, x.z + y.z}; }
int operator % (vec3 x, vec3 y) { return x.x * y.x + x.y * y.y + x.z * y.z; }
vec3 operator * (vec3 x, vec3 y) {
return {
x.y * y.z - x.z * y.y,
x.z * y.x - x.x * y.z,
x.x * y.y - x.y * y.x
};
}
int n;
ll calc(std::vector<plane> p, int k) {
for(auto & [v, z] : p) {
z *= k;
}
const int V = k * 200;
ll sum = 0;
for(int x = -V;x <= V;++x) {
for(int y = -V;y <= V;++y) {
int minz = -V, maxz = V;
for(auto [v, z] : p) {
z -= v.x * x + v.y * y;
if(v.z == 0) {
if(z < 0) {
minz = 1, maxz = 0;
}
} else if(v.z > 0) { // v.z * Z <= z
for(;minz <= maxz && v.z * maxz > z;) {
-- maxz;
}
} else {
for(;minz <= maxz && v.z * minz > z;) {
++ minz;
}
}
if(minz > maxz) break;
}
sum += maxz - minz + 1;
}
}
return sum;
}
int main() {
IOinit();
cin >> n >> K;
std::vector<vec3> a(n);
std::vector<plane> p;
std::set<vec3> set;
for(auto & [x, y, z] : a) {
cin >> x >> y >> z;
}
for(int i = 0;i < n;++i) {
for(int j = i + 1;j < n;++j) {
for(int k = i + 1;k < n;++k) if(i != j) {
vec3 x = a[j] - a[i];
vec3 y = a[k] - a[i];
vec3 z = x * y;
if(z.x || z.y || z.z) {
int gcd = std::gcd(std::gcd(z.x, z.y), z.z);
z.x /= gcd;
z.y /= gcd;
z.z /= gcd;
if(set.count(z)) {
continue;
}
set.emplace(z);
int v = z % a[i], ok = 1;
for(int l = 0;l < n;++l) {
ok = ok && z % a[l] <= v;
}
if(ok) {
p.push_back({z, v});
}
}
}
}
}
ll v[4] = { 1, calc(p, 1), calc(p, 2), calc(p, 3) };
const int mod = 998244353;
K %= mod;
ll ans = 0;
for(int i = 0;i < 4;++i) {
ll mul = 1;
for(int j = 0;j < 4;++j) if(j != i) {
mul = mul * (K - j) % mod;
for(;mul % (i - j);) mul += mod;
mul /= i - j;
}
ans += mul % mod * v[i];
}
ans %= mod;
ans += mod;
ans %= mod;
cout << ans << '\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 280ms
memory: 3788kb
input:
4 2 0 0 0 1 0 0 0 1 0 0 0 1
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 281ms
memory: 3624kb
input:
4 10000 0 0 0 1 0 0 0 1 0 0 0 1
output:
59878050
result:
ok 1 number(s): "59878050"
Test #3:
score: 0
Accepted
time: 769ms
memory: 3628kb
input:
8 314159265358979 5 -3 -3 -5 -3 -3 0 5 -3 0 0 10 4 2 6 -4 2 6 0 -5 6 0 0 -5
output:
152811018
result:
ok 1 number(s): "152811018"
Test #4:
score: 0
Accepted
time: 329ms
memory: 3872kb
input:
100 1 0 0 77 0 0 -195 0 0 -194 0 0 -112 0 0 -192 0 0 62 0 0 73 0 0 188 0 0 -150 0 0 -26 0 0 -164 0 0 -142 0 0 -90 200 1 0 0 0 50 0 0 111 0 0 -133 0 0 91 0 0 -70 0 0 46 0 0 175 -200 -67 0 0 0 128 0 0 170 0 0 76 0 0 -28 0 0 47 0 0 -196 0 0 45 0 0 -136 0 0 96 0 0 24 0 0 -29 0 0 -141 0 0 -84 0 0 -99 0 0...
output:
882531
result:
ok 1 number(s): "882531"
Test #5:
score: 0
Accepted
time: 781ms
memory: 3576kb
input:
82 333333333 98 99 168 -106 -105 -172 113 114 193 -13 -12 -17 -115 -114 -187 71 72 123 -70 -69 -112 95 96 163 -85 -84 -137 -28 -27 -42 -31 -30 -47 -200 -67 0 -121 -120 -197 -52 -51 -82 -112 -111 -182 110 111 188 44 45 78 86 87 148 104 105 178 -73 -72 -117 47 48 83 62 63 108 -103 -102 -167 56 57 98 1...
output:
767480931
result:
ok 1 number(s): "767480931"
Test #6:
score: 0
Accepted
time: 809ms
memory: 5956kb
input:
100 1 -63 -39 51 -36 -104 70 9 -77 34 115 -153 19 -161 141 10 157 -149 -4 -82 -92 87 14 114 -64 -176 -68 122 -7 -179 93 -182 200 -9 173 97 -135 0 -1 200 -83 -189 136 117 69 -93 -3 -113 58 183 -179 -2 -52 -184 118 -107 89 9 -24 -48 36 -111 87 12 -143 -173 158 -176 -78 127 -96 162 -33 147 -111 -18 -92...
output:
9771107
result:
ok 1 number(s): "9771107"
Test #7:
score: 0
Accepted
time: 371ms
memory: 4172kb
input:
100 1159111449 82 82 90 181 181 -85 70 70 -20 1 1 0 190 190 56 -83 -83 40 -89 -89 39 136 136 146 -195 -195 47 50 50 -99 -101 -101 -161 162 162 146 23 23 152 181 181 -91 -73 -73 -5 -105 -105 6 155 155 -136 152 152 -190 -33 -33 -137 55 55 41 3 3 -199 -168 -168 -177 -111 -111 115 171 171 8 131 131 123 ...
output:
681451260
result:
ok 1 number(s): "681451260"
Test #8:
score: 0
Accepted
time: 9ms
memory: 3512kb
input:
8 1 200 200 200 -200 -200 -200 200 -200 -200 -200 200 200 -200 200 -200 200 200 -200 200 -200 200 -200 -200 200
output:
64481201
result:
ok 1 number(s): "64481201"
Test #9:
score: 0
Accepted
time: 10ms
memory: 3564kb
input:
8 10 200 200 200 -200 200 200 -200 -200 200 200 200 -200 -200 -200 -200 200 -200 -200 -200 200 -200 200 -200 200
output:
160373409
result:
ok 1 number(s): "160373409"
Test #10:
score: 0
Accepted
time: 9ms
memory: 3596kb
input:
8 1234567890123 -200 -200 200 -200 200 200 -200 200 -200 -200 -200 -200 200 -200 200 200 -200 -200 200 200 200 200 200 -200
output:
868669244
result:
ok 1 number(s): "868669244"
Test #11:
score: -100
Wrong Answer
time: 11ms
memory: 3676kb
input:
24 1 200 200 140 200 -140 200 140 200 -200 -140 -200 200 -200 200 140 -200 200 -140 -200 140 200 200 140 -200 200 -140 -200 200 200 -140 -200 -200 140 -200 -140 -200 -200 -200 -140 -200 140 -200 -140 200 200 140 -200 200 200 -200 -140 -200 -140 200 200 140 200 200 -200 140 140 -200 -200 140 200 200 ...
output:
64443381
result:
wrong answer 1st numbers differ - expected: '64178641', found: '64443381'