結果

問題 No.206 数の積集合を求めるクエリ
ユーザー 0x19f0x19f
提出日時 2018-06-26 03:40:43
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 465 ms / 7,000 ms
コード長 2,033 bytes
コンパイル時間 1,408 ms
コンパイル使用メモリ 168,712 KB
実行使用メモリ 51,732 KB
最終ジャッジ日時 2024-06-30 22:51:42
合計ジャッジ時間 8,029 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 10 ms
6,944 KB
testcase_07 AC 9 ms
6,940 KB
testcase_08 AC 10 ms
6,940 KB
testcase_09 AC 10 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 15 ms
6,940 KB
testcase_13 AC 13 ms
6,944 KB
testcase_14 AC 13 ms
6,940 KB
testcase_15 AC 13 ms
6,944 KB
testcase_16 AC 13 ms
6,940 KB
testcase_17 AC 339 ms
51,616 KB
testcase_18 AC 310 ms
51,664 KB
testcase_19 AC 332 ms
51,692 KB
testcase_20 AC 310 ms
51,676 KB
testcase_21 AC 320 ms
51,688 KB
testcase_22 AC 316 ms
51,700 KB
testcase_23 AC 331 ms
51,652 KB
testcase_24 AC 465 ms
51,652 KB
testcase_25 AC 461 ms
51,704 KB
testcase_26 AC 436 ms
51,648 KB
testcase_27 AC 397 ms
51,732 KB
testcase_28 AC 444 ms
51,648 KB
testcase_29 AC 447 ms
51,728 KB
testcase_30 AC 435 ms
51,684 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

const double pi = acos(-1);

vector<complex<double>> fft(vector<complex<double>> f, int n, int sign) {
  if(n == 1) return f;

  vector<complex<double>> f0(n / 2), f1(n / 2);
  for(int i = 0; i < n / 2; i++) {
    f0[i] = f[i * 2];
    f1[i] = f[i * 2 + 1];
  }

  vector<complex<double>> ft0 = fft(f0, n / 2, sign);
  vector<complex<double>> ft1 = fft(f1, n / 2, sign);

  vector<complex<double>> ft(n);
  complex<double> zeta(cos(2 * pi / n), sign * sin(2 * pi / n));
  complex<double> x = 1;
  for(int i = 0; i < n / 2; i++) {
    ft[i] = ft0[i] + x * ft1[i];
    x *= zeta;
  }
  for(int i = 0; i < n / 2; i++) {
    ft[n / 2 + i] = ft0[i] + x * ft1[i];
    x *= zeta;
  }

  return ft;
}

vector<complex<double>> dft(vector<complex<double>> f) {
  int n = f.size();
  vector<complex<double>> ft = fft(f, n, 1);
  return ft;
}

vector<complex<double>> idft(vector<complex<double>> ft) {
  int n = ft.size();
  vector<complex<double>> f = fft(ft, n, -1);
  for(int i = 0; i < n; i++) f[i] /= n;
  return f;
}

vector<double> convolution(vector<double> a, vector<double> b) {
  ll p = a.size(), q = b.size();
  ll n = 1;
  while(n < p + q + 1) n *= 2;

  vector<complex<double>> g(n), h(n);
  for(int i = 0; i < p; i++) g[i] = a[i];
  for(int i = 0; i < q; i++) h[i] = b[i];

  vector<complex<double>> gt = dft(g);
  vector<complex<double>> ht = dft(h);

  vector<complex<double>> ft(n);
  for(int i = 0; i < n; i++) ft[i] = gt[i] * ht[i];

  vector<complex<double>> f = idft(ft);

  vector<double> c(n);
  for(int i = 0; i < n; i++) c[i] = f[i].real();
  return c;
}

int main(void) {
  ll L, M, N;
  cin >> L >> M >> N;
  vector<double> A(N + 1), B(N + 1);
  REP(i, 0, L) {
    ll a;
    cin >> a;
    A[a] = 1;
  }
  REP(i, 0, M) {
    ll b;
    cin >> b;
    B[N - b] = 1;
  }
  ll Q;
  cin >> Q;

  vector<double> ans = convolution(A, B);
  REP(i, 0, Q) cout << (ll) (ans[N + i] + 0.5) << endl;
}
0