結果

問題 No.2644 Iro Iro-Iro
ユーザー AerenAeren
提出日時 2024-02-19 23:17:01
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 5,811 bytes
コンパイル時間 2,909 ms
コンパイル使用メモリ 265,980 KB
実行使用メモリ 183,524 KB
最終ジャッジ日時 2024-09-29 02:59:00
合計ジャッジ時間 16,177 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 315 ms
183,272 KB
testcase_01 AC 312 ms
183,440 KB
testcase_02 AC 319 ms
183,400 KB
testcase_03 AC 320 ms
183,404 KB
testcase_04 AC 318 ms
183,488 KB
testcase_05 AC 317 ms
183,304 KB
testcase_06 AC 311 ms
183,444 KB
testcase_07 AC 319 ms
183,472 KB
testcase_08 AC 325 ms
183,412 KB
testcase_09 AC 320 ms
183,400 KB
testcase_10 AC 314 ms
183,440 KB
testcase_11 AC 320 ms
183,280 KB
testcase_12 AC 310 ms
183,404 KB
testcase_13 AC 356 ms
183,400 KB
testcase_14 AC 360 ms
183,396 KB
testcase_15 AC 358 ms
183,428 KB
testcase_16 AC 368 ms
183,308 KB
testcase_17 AC 358 ms
183,464 KB
testcase_18 AC 351 ms
183,308 KB
testcase_19 AC 347 ms
183,460 KB
testcase_20 AC 363 ms
183,424 KB
testcase_21 AC 355 ms
183,420 KB
testcase_22 AC 356 ms
183,472 KB
testcase_23 AC 371 ms
183,372 KB
testcase_24 AC 355 ms
183,368 KB
testcase_25 AC 369 ms
183,524 KB
testcase_26 AC 375 ms
183,412 KB
testcase_27 AC 364 ms
183,412 KB
testcase_28 AC 308 ms
183,420 KB
testcase_29 AC 378 ms
183,276 KB
testcase_30 AC 355 ms
183,280 KB
testcase_31 AC 340 ms
183,424 KB
testcase_32 AC 353 ms
183,364 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif

struct fast_fourier_transform_wrapper{
	using CD = complex<double>;
	using CLD = complex<long double>;
	// i \in [2^k, 2^{k+1}) holds w_{2^k+1}^{i-2^k}
	static vector<CD> root;
	static vector<CLD> root_ld;
	static void adjust_root(int n){
		if(root.empty()) root = {1, 1}, root_ld = {1, 1};
		for(auto k = (int)root.size(); k < n; k <<= 1){
			root.resize(n), root_ld.resize(n);
			auto theta = polar(1.0L, acos(-1.0L) / k);
			for(auto i = k; i < k << 1; ++ i) root[i] = root_ld[i] = i & 1 ? root_ld[i >> 1] * theta : root_ld[i >> 1];
		}
	}
	// O(n * log(n))
	static void transform(vector<CD> &p, bool invert = false){
		int n = (int)p.size();
		assert(n && __builtin_popcount(n) == 1);
		for(auto i = 1, j = 0; i < n; ++ i){
			int bit = n >> 1;
			for(; j & bit; bit >>= 1) j ^= bit;
			j ^= bit;
			if(i < j) swap(p[i], p[j]);
		}
		adjust_root(n);
		for(auto len = 1; len < n; len <<= 1) for(auto i = 0; i < n; i += len << 1) for(auto j = 0; j < len; ++ j){
			auto x = (double *)&root[j + len], y = (double *)&p[i + j + len];
			CD z(x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]);
			p[len + i + j] = p[i + j] - z, p[i + j] += z;
		}
		if(invert){
			reverse(p.begin() + 1, p.end());
			auto inv_n = 1.0l / n;
			for(auto &x: p) x *= inv_n;
		}
	}
	static vector<CD> buffer1, buffer2;
	// O(n * m)
	template<class T>
	static vector<T> convolute_naive(const vector<T> &p, const vector<T> &q){
		vector<T> res(max((int)p.size() + (int)q.size() - 1, 0));
		for(auto i = 0; i < (int)p.size(); ++ i) for(auto j = 0; j < (int)q.size(); ++ j) res[i + j] += p[i] * q[j];
		return res;
	}
	// Safe for sum(p[i]^2 + q[i]^2) lg2(n) < 9e14
	// O(n * log(n))
	template<class T>
	static vector<T> convolute(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 60) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		buffer1.assign(n, 0);
		for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i].real(p[i]);
		for(auto i = 0; i < (int)q.size(); ++ i) buffer1[i].imag(q[i]);
		transform(buffer1);
		for(auto &x: buffer1) x *= x;
		buffer2.assign(n, 0);
		for(auto i = 0; i < n; ++ i) buffer2[i] = buffer1[i] - conj(buffer1[-i & n - 1]);
		transform(buffer2, true);
		vector<T> res((int)p.size() + (int)q.size() - 1);
		for(auto i = 0; i < (int)res.size(); ++ i) res[i] = is_integral_v<T> ? llround(buffer2[i].imag() / 4) : buffer2[i].imag() / 4;
		return res;
	}
	// O(n * log(n))
	static vector<CD> convolute_complex(const vector<CD> &p, const vector<CD> &q){
		if(min(p.size(), q.size()) < 60) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		buffer1 = p, buffer2 = q;
		buffer1.resize(n), buffer2.resize(n);
		transform(buffer1), transform(buffer2);
		for(auto i = 0; i < n; ++ i) buffer1[i] *= buffer2[i];
		transform(buffer1, true);
		return {buffer1.begin(), buffer1.begin() + ((int)p.size() + (int)q.size() - 1)};
	}
	// Safe for 64-bit integer range
	// O(n * log(n))
	template<class T>
	static vector<T> convolute_splitting(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 80) return convolute_naive(p, q);
		int n = 1 << __lg((int)p.size() + (int)q.size() - 1) + 1;
		const int cut = 32000;
		buffer1.assign(n, 0);
		for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i] = {(int)p[i] / cut, (int)p[i] % cut};
		transform(buffer1);
		buffer2.assign(n, 0);
		for(auto i = 0; i < (int)q.size(); ++ i) buffer2[i] = {(int)q[i] / cut, (int)q[i] % cut};
		transform(buffer2);
		for(auto i = 0; i <= n >> 1; ++ i){
			int j = -i & n - 1;
			if(i == j){
				tie(buffer1[i], buffer2[i]) = pair<CD, CD>{
					(buffer1[i] + conj(buffer1[i])) * buffer2[i] / 2.0,
					(buffer1[i] - conj(buffer1[i])) * buffer2[i] / 2i
				};
			}
			else{
				tie(buffer1[i], buffer2[i], buffer1[j], buffer2[j]) = tuple<CD, CD, CD, CD>{
					(buffer1[i] + conj(buffer1[j])) * buffer2[i] / 2.0,
					(buffer1[i] - conj(buffer1[j])) * buffer2[i] / 2i,
					(buffer1[j] + conj(buffer1[i])) * buffer2[j] / 2.0,
					(buffer1[j] - conj(buffer1[i])) * buffer2[j] / 2i
				};
			}
		}
		transform(buffer1, true);
		transform(buffer2, true);
		vector<T> res((int)p.size() + (int)q.size() - 1);
		for(auto i = 0; i < (int)res.size(); ++ i) res[i] = ((T)llround(buffer1[i].real()) * cut + (T)(llround(buffer1[i].imag()) + llround(buffer2[i].real()))) * cut + (T)llround(buffer2[i].imag());
		return res;
	}
	// Safe for 64-bit integer range
	// O(n * log(n))
	template<class T>
	static vector<T> convolute_splitting_mod(const vector<T> &p, const vector<T> &q){
		if(min(p.size(), q.size()) < 80) return convolute_naive(p, q);
		vector<int> p2(p.begin(), p.end()), q2(q.begin(), q.end());
		p2 = convolute_splitting(p2, q2);
		return {p2.begin(), p2.end()};
	}
};
vector<complex<double>> fast_fourier_transform_wrapper::root;
vector<complex<long double>> fast_fourier_transform_wrapper::root_ld;
vector<complex<double>> fast_fourier_transform_wrapper::buffer1;
vector<complex<double>> fast_fourier_transform_wrapper::buffer2;
 
using fft = fast_fourier_transform_wrapper;

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::badbit | ios::failbit);
	int n, qn;
	cin >> n >> qn;
	const int base = 101;
	vector<int> a(base * base * base);
	for(auto i = 0; i < n; ++ i){
		int x, y, z;
		cin >> x >> y >> z;
		a[base * base * x + base * y + z] = 1;
	}
	auto b = a;
	ranges::reverse(b);
	auto ab = fft::convolute(a, b);
	int res = 0;
	for(auto qi = 0; qi < qn; ++ qi){
		int x, y, z;
		cin >> x >> y >> z;
		res = max(res, 2 * n - ab[base * base * base - 1 + base * base * x + base * y + z]);
	}
	cout << res << "\n";
	return 0;
}

/*

*/
0