結果

問題 No.3041 非対称じゃんけん
ユーザー Aeren
提出日時 2025-02-28 21:45:34
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 5,729 bytes
コンパイル時間 3,840 ms
コンパイル使用メモリ 286,036 KB
実行使用メモリ 8,232 KB
最終ジャッジ日時 2025-02-28 21:46:09
合計ジャッジ時間 21,317 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27 TLE * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #include <bits/allocator.h> // Temp fix for gcc13 global pragma
// #pragma GCC target("avx2,bmi2,popcnt,lzcnt")
// #pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
// #include <x86intrin.h>
using namespace std;
#if __cplusplus >= 202002L
using namespace numbers;
#endif
#ifdef LOCAL
	#include "Debug.h"
#else
	#define debug_endl() 42
	#define debug(...) 42
	#define debug2(...) 42
	#define debugbin(...) 42
#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, acosl(-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(int n, CD *p, bool invert = false){
		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 + 1, p + n);
			auto inv_n = 1.0l / n;
			for(auto i = 0; i < n; ++ i) p[i] *= inv_n;
		}
	}
	// O(n * log(n))
	static void transform(vector<CD> &p, bool invert = false){
		transform((int)p.size(), p.data(), invert);
	}
	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 = 32768;
		buffer1.assign(n, 0);
		for(auto i = 0; i < (int)p.size(); ++ i) buffer1[i] = {(double)((int)p[i] / cut), (double)((int)p[i] % cut)};
		transform(buffer1);
		buffer2.assign(n, 0);
		for(auto i = 0; i < (int)q.size(); ++ i) buffer2[i] = {(double)((int)q[i] / cut), (double)((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{
					(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{
					(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;
	}
};
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, f;
	cin >> n >> f;
	vector<int> a(n), b(n), c(n);
	copy_n(istream_iterator<int>(cin), n, a.begin());
	copy_n(istream_iterator<int>(cin), n, b.begin());
	copy_n(istream_iterator<int>(cin), n, c.begin());
	bitset<900'001> bs;
	bs.set(0);
	for(auto i = 0; i < n; ++ i){
		bs = bs << a[i] | bs << b[i] | bs << c[i];
		cout << bs.count() << "\n";
	}
	return 0;
}

/*

*/
0