結果

問題 No.206 数の積集合を求めるクエリ
ユーザー koba-e964koba-e964
提出日時 2015-06-11 15:09:27
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 284 ms / 7,000 ms
コード長 2,687 bytes
コンパイル時間 1,873 ms
コンパイル使用メモリ 100,864 KB
実行使用メモリ 20,020 KB
最終ジャッジ日時 2023-09-20 20:49:17
合計ジャッジ時間 6,070 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 1 ms
4,376 KB
testcase_06 AC 4 ms
4,376 KB
testcase_07 AC 5 ms
4,380 KB
testcase_08 AC 5 ms
4,380 KB
testcase_09 AC 5 ms
4,376 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 9 ms
4,380 KB
testcase_13 AC 8 ms
4,376 KB
testcase_14 AC 8 ms
4,380 KB
testcase_15 AC 8 ms
4,380 KB
testcase_16 AC 8 ms
4,380 KB
testcase_17 AC 160 ms
19,680 KB
testcase_18 AC 137 ms
19,788 KB
testcase_19 AC 149 ms
19,684 KB
testcase_20 AC 130 ms
19,844 KB
testcase_21 AC 140 ms
19,720 KB
testcase_22 AC 136 ms
19,708 KB
testcase_23 AC 147 ms
19,616 KB
testcase_24 AC 284 ms
19,656 KB
testcase_25 AC 284 ms
19,856 KB
testcase_26 AC 253 ms
19,708 KB
testcase_27 AC 222 ms
19,636 KB
testcase_28 AC 263 ms
19,632 KB
testcase_29 AC 267 ms
19,632 KB
testcase_30 AC 264 ms
20,020 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
  }
}
0