結果
問題 | No.206 数の積集合を求めるクエリ |
ユーザー | EmKjp |
提出日時 | 2015-05-08 22:57:30 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 171 ms / 7,000 ms |
コード長 | 2,254 bytes |
コンパイル時間 | 787 ms |
コンパイル使用メモリ | 92,596 KB |
実行使用メモリ | 17,528 KB |
最終ジャッジ日時 | 2023-09-19 07:10:36 |
合計ジャッジ時間 | 5,309 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 4 ms
4,376 KB |
testcase_07 | AC | 4 ms
4,376 KB |
testcase_08 | AC | 5 ms
4,376 KB |
testcase_09 | AC | 5 ms
4,380 KB |
testcase_10 | AC | 2 ms
4,380 KB |
testcase_11 | AC | 1 ms
4,376 KB |
testcase_12 | AC | 5 ms
4,380 KB |
testcase_13 | AC | 5 ms
4,380 KB |
testcase_14 | AC | 5 ms
4,380 KB |
testcase_15 | AC | 5 ms
4,376 KB |
testcase_16 | AC | 5 ms
4,380 KB |
testcase_17 | AC | 161 ms
17,420 KB |
testcase_18 | AC | 151 ms
16,880 KB |
testcase_19 | AC | 162 ms
17,184 KB |
testcase_20 | AC | 152 ms
17,024 KB |
testcase_21 | AC | 157 ms
17,056 KB |
testcase_22 | AC | 152 ms
17,044 KB |
testcase_23 | AC | 165 ms
17,276 KB |
testcase_24 | AC | 171 ms
17,416 KB |
testcase_25 | AC | 170 ms
17,528 KB |
testcase_26 | AC | 160 ms
16,872 KB |
testcase_27 | AC | 154 ms
16,804 KB |
testcase_28 | AC | 166 ms
17,060 KB |
testcase_29 | AC | 163 ms
17,100 KB |
testcase_30 | AC | 158 ms
16,972 KB |
ソースコード
#include<iostream> #include<sstream> #include<cstdio> #include<cstring> #include<algorithm> #include<string> #include<vector> #include<cmath> #include<set> #include<map> #include<stack> #include<queue> #include<numeric> #include<functional> #include<complex> using namespace std; #define BET(a,b,c) ((a)<=(b)&&(b)<(c)) #define FOR(i,n) for(int i=0,i##_end=(int(n));i<i##_end;i++) #define SZ(x) (int)(x.size()) #define ALL(x) (x).begin(),(x).end() #define MP make_pair #define FOR_EACH(it,v) for(__typeof(v.begin()) it=v.begin(),it_end=v.end() ; it != it_end ; it++) typedef vector<int> VI; typedef vector<VI> VVI; const long double PI = 4.0*atan(1.0); typedef complex<double> Complex; const Complex I(0, 1); template<typename T> void fft(int n, double theta, vector<T>& a) { for (int m = n; m >= 2; m >>= 1) { int mh = m >> 1; for (int i = 0; i < mh; i++) { Complex w = exp(i*theta*I); for (int j = i; j < n; j += m) { int k = j + mh; Complex x = a[j] - a[k]; a[j] += a[k]; a[k] = w * x; } } theta *= 2; } int i = 0; for (int j = 1; j < n - 1; j++) { for (int k = n >> 1; k > (i ^= k); k >>= 1); if (j < i) swap(a[i], a[j]); } } // result[i] = sum a[x] * b[y] where x + y == i template<typename T> vector<long long> comvolution(const vector<T> &a, const vector<T> &b){ vector<long long> result; vector<Complex> fa(a.begin(), a.end()); vector<Complex> fb(b.begin(), b.end()); //while(SZ(fa) && fa.back().real() == 0.0) fa.pop_back(); //while(SZ(fb) && fb.back().real() == 0.0) fb.pop_back(); int n = 1; while(n < SZ(fa) + SZ(fb)) n <<= 1; fa.resize(n); fb.resize(n); fft(n, 2 * PI / n, fa); fft(n, 2 * PI / n, fb); FOR(i,n) fa[i] *= fb[i]; fft(n, -2 * PI / n, fa); FOR(i,n) result.push_back(round(fa[i].real()/n)); return result; } int main() { int L,M,N; cin>>L>>M>>N; VI A(L); VI B(M); FOR(i,L) scanf("%d",&A[i]); FOR(i,M) scanf("%d",&B[i]); int Q; cin>>Q; VI AH(N + 1); VI BH(N + 1); FOR(i,L) AH[A[i]]++; FOR(i,M) BH[B[i]]++; reverse(ALL(BH)); auto r = comvolution(AH, BH); FOR(i,Q){ printf("%lld\n", r[i+N]); } return 0; }