AtCoder Typical Contest 001

Submission #7469644

Source codeソースコード

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

Submission

Task問題 C - 高速フーリエ変換
User nameユーザ名 kopricky
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 2675 Byte
File nameファイル名
Exec time実行時間 174 ms
Memory usageメモリ使用量 14080 KB

Compiler messageコンパイルメッセージ

./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]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01
All 100 / 100 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01 AC 5 ms 512 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 164 ms 13824 KB
02_02_17056 AC 38 ms 3584 KB
02_03_34866 AC 80 ms 6912 KB
02_04_6779 AC 10 ms 1152 KB
02_05_65534 AC 90 ms 7424 KB
02_06_65535 AC 90 ms 7424 KB
02_07_65536 AC 161 ms 13568 KB
02_08_65537 AC 163 ms 13568 KB
02_09_65538 AC 162 ms 13568 KB
02_10_100000 AC 174 ms 14080 KB