Submission #2976696


Source Code Expand

#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;

const int MAX_N = 100005;
const double PI = 4.0*atan(1.0);

inline 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());
}

inline vector<complex<double> > fft(vector<complex<double> > a,bool rev = false)
{
    const double PI = std::acos(-1);
    int n = a.size(),h = 0;
    for(int i = 0; 1 << i < n; i++) h++;
    rep(i,n){
        int j = 0;
        rep(k,h) j |= (i >> k & 1) << (h-1-k);
        if (i < j) swap(a[i], a[j]);
    }
    for(int i = 1; i < n; i *= 2) {
        rep(j,i){
            complex<double> w = polar(1.0,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) rep(i,n) a[i] /= n;
    return a;
}

inline 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);
    rep(i,a.size()) A[i].real(a[i]);
    rep(i,b.size()) B[i].real(b[i]);
    A = fft(A),B = fft(B);
    rep(i,t) A[i] *= B[i];
    A = fft(A, true);
    a.resize(s);
    //整数に直す
    rep(i,s) 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;
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User kopricky
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2440 Byte
Status AC
Exec Time 170 ms
Memory 14080 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:74:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:77: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]);
                                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 100 / 100
Status
AC × 1
AC × 33
Set Name Test Cases
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
Case Name Status Exec Time Memory
00_sample_01 AC 2 ms 256 KB
01_00_01 AC 1 ms 256 KB
01_01_19 AC 1 ms 256 KB
01_02_31 AC 1 ms 256 KB
01_03_22 AC 1 ms 256 KB
01_04_31 AC 1 ms 256 KB
01_05_40 AC 1 ms 256 KB
01_06_15 AC 1 ms 256 KB
01_07_39 AC 1 ms 256 KB
01_08_28 AC 1 ms 256 KB
01_09_30 AC 1 ms 256 KB
01_10_23 AC 1 ms 256 KB
01_11_33 AC 1 ms 256 KB
01_12_11 AC 1 ms 256 KB
01_13_28 AC 1 ms 256 KB
01_14_41 AC 1 ms 256 KB
01_15_26 AC 1 ms 256 KB
01_16_49 AC 1 ms 256 KB
01_17_34 AC 1 ms 256 KB
01_18_02 AC 1 ms 256 KB
01_19_33 AC 1 ms 256 KB
01_20_29 AC 1 ms 256 KB
02_00_51254 AC 84 ms 7168 KB
02_01_82431 AC 165 ms 13824 KB
02_02_17056 AC 37 ms 3584 KB
02_03_34866 AC 78 ms 6912 KB
02_04_6779 AC 10 ms 1152 KB
02_05_65534 AC 88 ms 7424 KB
02_06_65535 AC 89 ms 7424 KB
02_07_65536 AC 159 ms 13568 KB
02_08_65537 AC 159 ms 13568 KB
02_09_65538 AC 158 ms 13568 KB
02_10_100000 AC 170 ms 14080 KB