結果

問題 No.206 数の積集合を求めるクエリ
ユーザー rogi52rogi52
提出日時 2021-08-14 22:04:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 929 ms / 7,000 ms
コード長 1,983 bytes
コンパイル時間 2,026 ms
コンパイル使用メモリ 175,040 KB
実行使用メモリ 43,612 KB
最終ジャッジ日時 2024-04-15 19:35:37
合計ジャッジ時間 16,632 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 3 ms
5,376 KB
testcase_06 AC 25 ms
5,376 KB
testcase_07 AC 24 ms
5,376 KB
testcase_08 AC 24 ms
5,376 KB
testcase_09 AC 24 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 25 ms
5,376 KB
testcase_13 AC 25 ms
5,376 KB
testcase_14 AC 24 ms
5,376 KB
testcase_15 AC 24 ms
5,376 KB
testcase_16 AC 24 ms
5,376 KB
testcase_17 AC 929 ms
43,604 KB
testcase_18 AC 909 ms
43,480 KB
testcase_19 AC 908 ms
43,488 KB
testcase_20 AC 879 ms
43,484 KB
testcase_21 AC 899 ms
43,612 KB
testcase_22 AC 899 ms
43,480 KB
testcase_23 AC 914 ms
43,612 KB
testcase_24 AC 906 ms
43,480 KB
testcase_25 AC 905 ms
43,484 KB
testcase_26 AC 900 ms
43,608 KB
testcase_27 AC 898 ms
43,604 KB
testcase_28 AC 903 ms
43,612 KB
testcase_29 AC 892 ms
43,608 KB
testcase_30 AC 907 ms
43,612 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

vector<complex<double>> fft(vector<complex<double>> f, int inv = 0){
    int n = f.size();
    if(n == 1) return f;
    vector<complex<double>> f_e, f_o;
    for(int i = 0; i < n; i++){
        if(i % 2 == 0) f_e.push_back(f[i]); else f_o.push_back(f[i]);
    }
    vector<complex<double>> F_e = fft(f_e, inv), F_o = fft(f_o, inv);
    vector<complex<double>> ret;
    for(int i = 0; i < n; i++){
        complex<double> zeta = exp(i * 2 * M_PI / (double)n * complex<double>{0, 1.0} * (double)(inv ? -1 : +1));
        int j = i % (n / 2);
        ret.push_back(F_e[j] + zeta * F_o[j]);
    }
    return ret;
}

vector<complex<double>> change(vector<complex<double>> f){
    int n = 1;
    while(n < f.size()) n <<= 1;
    while(f.size() < n) f.push_back(complex<double>{0, 0});
    return f;
}

template<class T>
vector<T> convolution(vector<T> a, vector<T> b){
    int N = a.size();
    vector<complex<double>> A, B;
    for(int i = 0; i < N; i++){
        A.push_back(complex<double>{(double)a[i], 0});
        B.push_back(complex<double>{(double)b[i], 0});
    }
    for(int i = 0; i < N; i++){
        A.push_back(complex<double>{0, 0});
        B.push_back(complex<double>{0, 0});
    }

    A = change(A);
    B = change(B);
    A = fft(A);
    B = fft(B);
    vector<complex<double>> C;
    for(int i = 0; i < A.size(); i++) C.push_back(A[i] * B[i]);
    C = fft(C, 1);
    vector<T> c;
    c.push_back(0);
    for(int i = 0; i < 2 * N - 1; i++){
        c.push_back((T)(C[i].real() / (double)C.size() + 0.5));
    }
    return c;
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);

    int L,M,N; cin >> L >> M >> N;
    vector<int> A(N),B(N);
    rep(i,L){ int a; cin >> a; A[a - 1] = 1; }
    rep(i,M){ int b; cin >> b; B[N - 1 - (b - 1)] = 1; }

    vector<int> C = convolution(A, B);
    int Q; cin >> Q;
    rep(i,Q) printf("%d\n", C[N + i]);
}
0