結果

問題 No.206 数の積集合を求めるクエリ
ユーザー kazumakazuma
提出日時 2018-03-25 10:03:38
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 192 ms / 7,000 ms
コード長 2,065 bytes
コンパイル時間 2,264 ms
コンパイル使用メモリ 206,776 KB
実行使用メモリ 13,632 KB
最終ジャッジ日時 2023-09-07 11:18:34
合計ジャッジ時間 6,980 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,376 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 1 ms
4,380 KB
testcase_06 AC 3 ms
4,380 KB
testcase_07 AC 4 ms
4,376 KB
testcase_08 AC 3 ms
4,376 KB
testcase_09 AC 3 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 7 ms
4,380 KB
testcase_13 AC 6 ms
4,380 KB
testcase_14 AC 7 ms
4,376 KB
testcase_15 AC 7 ms
4,380 KB
testcase_16 AC 6 ms
4,380 KB
testcase_17 AC 66 ms
13,400 KB
testcase_18 AC 59 ms
13,476 KB
testcase_19 AC 65 ms
13,100 KB
testcase_20 AC 58 ms
13,440 KB
testcase_21 AC 60 ms
13,480 KB
testcase_22 AC 60 ms
13,632 KB
testcase_23 AC 65 ms
13,104 KB
testcase_24 AC 192 ms
13,588 KB
testcase_25 AC 190 ms
13,484 KB
testcase_26 AC 179 ms
13,400 KB
testcase_27 AC 146 ms
13,444 KB
testcase_28 AC 185 ms
13,408 KB
testcase_29 AC 185 ms
13,468 KB
testcase_30 AC 182 ms
13,480 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

const double pi = acos(-1);

typedef complex<double> Comp;

int size(int n) {
	int res = 1;
	while (res < n) res <<= 1;
	return res;
}

void fft(vector<Comp>& v) {
	int n = size(v.size());
	if (n >(int)v.size()) v.resize(n);
	for (int j = 1, i = 0; j < n - 1; j++) {
		for (int k = n >> 1; k >(i ^= k); k >>= 1);
		if (j < i) swap(v[i], v[j]);
	}
	for (int m = 2; m <= n; m <<= 1) {
		double deg = (-1) * 2 * pi / m;
		Comp r(cos(deg), sin(deg));
		for (int i = 0; i < n; i += m) {
			Comp w(1, 0);
			for (int j = i, k = i + m / 2; k < i + m; j++, k++) {
				Comp t1 = v[j], t2 = w * v[k];
				v[j] = t1 + t2, v[k] = t1 - t2;
				w *= r;
			}
		}
	}
}

void ifft(vector<Comp>& v) {
	int n = size(v.size());
	if (n > (int)v.size()) v.resize(n);
	for (int j = 1, i = 0; j < n - 1; j++) {
		for (int k = n >> 1; k >(i ^= k); k >>= 1);
		if (j < i) swap(v[i], v[j]);
	}
	for (int m = 2; m <= n; m <<= 1) {
		double deg = 2 * pi / m;
		Comp r(cos(deg), sin(deg));
		for (int i = 0; i < n; i += m) {
			Comp w(1, 0);
			for (int j = i, k = i + m / 2; k < i + m; j++, k++) {
				Comp t1 = v[j], t2 = w * v[k];
				v[j] = t1 + t2, v[k] = t1 - t2;
				w *= r;
			}
		}
	}
	for (int i = 0; i < n; ++i) v[i] *= 1.0 / n;
}

vector<int> convolution(const vector<int>& p, const vector<int>& q) {
	int n = size(p.size() + q.size());
	vector<Comp> P(n), Q(n);
	for (int i = 0; i < (int)p.size(); i++) P[i] = p[i];
	for (int i = 0; i < (int)q.size(); i++) Q[i] = q[i];
	fft(P); fft(Q);
	for (int i = 0; i < n; i++) P[i] *= Q[i];
	ifft(P);
	vector<int> res(n);
	for (int i = 0; i < n; i++) {
		res[i] = round(P[i].real());
	}
	return res;
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int L, M, N, Q;
	cin >> L >> M >> N;
	vector<int> cnt1(N + 1), cnt2(N + 1);
	for (int i = 0; i < L; i++) {
		int A;
		cin >> A;
		cnt1[A]++;
	}
	for (int i = 0; i < M; i++) {
		int B;
		cin >> B;
		cnt2[N - B]++;
	}
	auto v = convolution(cnt1, cnt2);
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cout << v[N + i] << endl;
	}
	return 0;
}
0