QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#176519#6324. Expanded Hullucup-team1209WA 809ms5956kbC++202.5kb2023-09-11 19:07:562023-09-11 19:07:56

Judging History

你现在查看的是最新测评结果

  • [2023-09-11 19:07:56]
  • 评测
  • 测评结果:WA
  • 用时:809ms
  • 内存:5956kb
  • [2023-09-11 19:07:56]
  • 提交

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'