提出 #7469644


ソースコード 拡げる

Copy
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define each(a,b) for(auto (a): (b))
#define all(v) (v).begin(),(v).end()
#define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end())
#define fi first
#define se second
#define pb push_back
#define show(x) cout<<#x<<" = "<<(x)<<endl
#define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl
#define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl
#define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl
#define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl

using namespace std;

typedef pair<int,int>P;

complex<double> operator* (const complex<double> a, const complex<double> b){
    return complex<double>(a.real()*b.real()-a.imag()*b.imag(),a.real()*b.imag()+a.imag()*b.real());
}

vector<complex<double> > fft(vector<complex<double> > a,bool rev = false)
{
    constexpr double PI = std::acos(-1);
    int n = a.size(),h = 0;
    for(int i = 0; 1 << i < n; i++) h++;
    for(int i = 0; i < n; i++){
        int j = 0;
        for(int k = 0; k < h; k++){
            j |= (i >> k & 1) << (h-1-k);
        }
        if (i < j) swap(a[i], a[j]);
    }
    for(int i = 1; i < n; i *= 2) {
        for(int j = 0; j < i; j++){
            complex<double> w = {cos(2*PI/(i*2)*(rev?-1:1)*j), sin(2*PI/(i*2)*(rev?-1:1)*j)};
            for(int k = 0; k < n; k += i * 2) {
                complex<double> s = a[j+k];
                complex<double> t = a[j+k+i]*w;
                a[j+k+0] = s+t;
                a[j+k+i] = s-t;
            }
        }
    }
    if(rev){
        for(int i = 0; i < n; i++){
            a[i] /= n;
        }
    }
    return a;
}

vector<int> mul(vector<int> a, vector<int> b)
{
    int s = (int)a.size() + (int)b.size() - 1,t = 1;
    while (t < s) t *= 2;
    vector<complex<double> > A(t), B(t);
    for(int i = 0; i < (int)a.size(); i++){
        A[i].real(a[i]);
    }
    for(int i = 0; i < (int)b.size(); i++){
        B[i].real(b[i]);
    }
    A = fft(A), B = fft(B);
    for(int i = 0; i < t; i++){
        A[i] *= B[i];
    }
    A = fft(A, true);
    a.resize(s);
    //整数に直す
    for(int i = 0; i < s; i++){
        a[i] = round(A[i].real());
    }
    return a;
}

int main()
{
    int n;
    scanf("%d",&n);
    vector<int> a(n+1,0),b(n+1,0);
    rep(i,n){
        scanf("%d%d",&a[i+1],&b[i+1]);
    }
    a = mul(a,b);
    rep(i,2*n){
        cout << a[i+1] << "\n";
    }
    return 0;
}

提出情報

提出日時
問題 C - 高速フーリエ変換
ユーザ kopricky
言語 C++14 (GCC 5.4.1)
得点 100
コード長 2675 Byte
結果
実行時間 174 ms
メモリ 14080 KB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:85:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:88:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i+1],&b[i+1]);
                                      ^

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 100 / 100
結果
× 1
× 33
セット名 テストケース
Sample 00_sample_01
All 00_sample_01, 01_00_01, 01_01_19, 01_02_31, 01_03_22, 01_04_31, 01_05_40, 01_06_15, 01_07_39, 01_08_28, 01_09_30, 01_10_23, 01_11_33, 01_12_11, 01_13_28, 01_14_41, 01_15_26, 01_16_49, 01_17_34, 01_18_02, 01_19_33, 01_20_29, 02_00_51254, 02_01_82431, 02_02_17056, 02_03_34866, 02_04_6779, 02_05_65534, 02_06_65535, 02_07_65536, 02_08_65537, 02_09_65538, 02_10_100000
ケース名 結果 実行時間 メモリ
00_sample_01 5 ms 512 KB
01_00_01 1 ms 256 KB
01_01_19 1 ms 256 KB
01_02_31 1 ms 256 KB
01_03_22 1 ms 256 KB
01_04_31 1 ms 256 KB
01_05_40 1 ms 256 KB
01_06_15 1 ms 256 KB
01_07_39 1 ms 256 KB
01_08_28 1 ms 256 KB
01_09_30 1 ms 256 KB
01_10_23 1 ms 256 KB
01_11_33 1 ms 256 KB
01_12_11 1 ms 256 KB
01_13_28 1 ms 256 KB
01_14_41 1 ms 256 KB
01_15_26 1 ms 256 KB
01_16_49 1 ms 256 KB
01_17_34 1 ms 256 KB
01_18_02 1 ms 256 KB
01_19_33 1 ms 256 KB
01_20_29 1 ms 256 KB
02_00_51254 84 ms 7168 KB
02_01_82431 164 ms 13824 KB
02_02_17056 38 ms 3584 KB
02_03_34866 80 ms 6912 KB
02_04_6779 10 ms 1152 KB
02_05_65534 90 ms 7424 KB
02_06_65535 90 ms 7424 KB
02_07_65536 161 ms 13568 KB
02_08_65537 163 ms 13568 KB
02_09_65538 162 ms 13568 KB
02_10_100000 174 ms 14080 KB