結果

問題 No.206 数の積集合を求めるクエリ
ユーザー 0x19f0x19f
提出日時 2018-06-26 03:36:57
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 2,027 bytes
コンパイル時間 2,136 ms
コンパイル使用メモリ 153,476 KB
実行使用メモリ 51,896 KB
最終ジャッジ日時 2023-09-13 14:05:35
合計ジャッジ時間 10,143 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,380 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 11 ms
5,084 KB
testcase_07 AC 11 ms
4,824 KB
testcase_08 AC 11 ms
4,776 KB
testcase_09 AC 11 ms
4,900 KB
testcase_10 WA -
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 17 ms
4,824 KB
testcase_13 AC 15 ms
4,900 KB
testcase_14 AC 16 ms
4,824 KB
testcase_15 AC 16 ms
4,828 KB
testcase_16 AC 16 ms
4,892 KB
testcase_17 AC 381 ms
51,492 KB
testcase_18 AC 355 ms
51,896 KB
testcase_19 AC 375 ms
51,588 KB
testcase_20 AC 355 ms
51,696 KB
testcase_21 AC 362 ms
51,836 KB
testcase_22 AC 360 ms
51,840 KB
testcase_23 AC 382 ms
51,548 KB
testcase_24 AC 570 ms
51,624 KB
testcase_25 AC 567 ms
51,624 KB
testcase_26 AC 541 ms
51,692 KB
testcase_27 WA -
testcase_28 AC 550 ms
51,696 KB
testcase_29 AC 551 ms
51,628 KB
testcase_30 WA -
権限があれば一括ダウンロードができます

ソースコード

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 << round(ans[N + i]) << endl;
}
0