結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー |
|
提出日時 | 2015-06-11 15:09:27 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 217 ms / 7,000 ms |
コード長 | 2,687 bytes |
コンパイル時間 | 1,032 ms |
コンパイル使用メモリ | 82,004 KB |
実行使用メモリ | 19,796 KB |
最終ジャッジ日時 | 2024-07-06 15:37:13 |
合計ジャッジ時間 | 4,101 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 1 ms
5,376 KB |
testcase_03 | AC | 1 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 1 ms
5,376 KB |
testcase_06 | AC | 3 ms
5,376 KB |
testcase_07 | AC | 3 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 1 ms
5,376 KB |
testcase_11 | AC | 1 ms
5,376 KB |
testcase_12 | AC | 7 ms
5,376 KB |
testcase_13 | AC | 7 ms
5,376 KB |
testcase_14 | AC | 7 ms
5,376 KB |
testcase_15 | AC | 6 ms
5,376 KB |
testcase_16 | AC | 6 ms
5,376 KB |
testcase_17 | AC | 108 ms
19,772 KB |
testcase_18 | AC | 79 ms
19,776 KB |
testcase_19 | AC | 98 ms
19,792 KB |
testcase_20 | AC | 79 ms
19,792 KB |
testcase_21 | AC | 86 ms
19,796 KB |
testcase_22 | AC | 84 ms
19,684 KB |
testcase_23 | AC | 101 ms
19,664 KB |
testcase_24 | AC | 217 ms
19,760 KB |
testcase_25 | AC | 210 ms
19,756 KB |
testcase_26 | AC | 194 ms
19,760 KB |
testcase_27 | AC | 154 ms
19,752 KB |
testcase_28 | AC | 198 ms
19,784 KB |
testcase_29 | AC | 197 ms
19,792 KB |
testcase_30 | AC | 188 ms
19,792 KB |
ソースコード
#include <iostream> #include <vector> #include <complex> /* * Fast fourier transformation. n must be a power of 2. * header requirement: vector, complex */ class FFT { private: typedef std::complex<double> comp; static void inplace_internal_fft( comp const *f, comp *output, comp const *ztbl, int x, int fstart, int fstep, int n, int ostart) { if (n == 1) { output[ostart] = f[fstart]; return; } inplace_internal_fft(f, output, ztbl, x + 1, fstart, 2 * fstep, n / 2, ostart); inplace_internal_fft(f, output, ztbl, x + 1, fstart + fstep, 2 * fstep, n / 2, ostart + n / 2); comp zeta = ztbl[x]; comp pzeta = 1; for (int i = 0; i < n / 2; ++i) { comp f0 = output[ostart + i]; comp f1 = output[ostart + i + n / 2]; output[ostart + i] = f0 + pzeta * f1; output[ostart + i + n / 2] = f0 - pzeta * f1; pzeta *= zeta; } return; } public: static int ceil_pow2(int n) { while (n & (n -1)) { n += n & (-n); } return n; } static std::vector<comp> transform(std::vector<comp> f, int n) { const double pi = 3.141592653589793238463; int p = __builtin_popcount(n - 1); // n = 2^p std::vector<comp> ztbl(p); for (int i = 0; i < p; ++i) { int d = n >> i; comp zeta = comp(cos(2 * pi / d), sin(2 * pi / d)); ztbl[i] = zeta; } std::vector<comp> output(n); inplace_internal_fft(&f[0], &output[0], &ztbl[0], 0, 0, 1, n, 0); return output; } static std::vector<comp> inverse_transform(std::vector<comp> f, int n) { const double pi = 3.141592653589793238463; int p = __builtin_popcount(n - 1); // n = 2^p std::vector<comp> ztbl(p); for (int i = 0; i < p; ++i) { int d = n >> i; comp zeta = comp(cos(2 * pi / d), - sin(2 * pi / d)); ztbl[i] = zeta; } std::vector<comp> output(n); inplace_internal_fft(&f[0], &output[0], &ztbl[0], 0, 0, 1, n, 0); for (int i = 0; i < n; i++) { output[i] /= n; } return output; } }; #define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++) using namespace std; typedef complex<double> comp; int main(void) { int l, m, n; cin >> l >> m >> n; n = FFT::ceil_pow2(n) * 2; vector<comp> a(n), b(n); REP(i, 0, l) { int t; cin >> t; a[t - 1] = 1; } REP(i, 0, m) { int t; cin >> t; b[n / 2 - t] = 1; } a = FFT::transform(a, n); b = FFT::transform(b, n); REP(i, 0, n) { a[i] *= b[i]; } a = FFT::inverse_transform(a, n); int q; cin >> q; REP(i, 0, q) { cout << (int)(a[n / 2 - 1 + i].real() + 0.5) << endl; } }