Submission #2588838


Source Code Expand

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <complex.h>

#define K (8192)
double complex f[K], g[K], h[K];
#undef K

uint32_t bitrev32(uint32_t x)
{
    x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
    x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
    x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
    x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
    return((x >> 16) | (x << 16));
}

uint32_t bitrev(uint32_t x, int msbi) {
    return bitrev32(x) >> (msbi+1);
}

void fft (double complex f[], int K) {
    const int msbi =  __builtin_clz(K);
    for(int i=1; i<K; i<<=1) {
        const double complex w = cexp( -I * 2.0*M_PI / (i<<1) );
        for(int j=0; j<K; j+=i<<1) {
            double complex wn = 1;
            for(int k=0; k<i; k++) {
                const int ai = bitrev(j+k, msbi);
                const int bi = bitrev(i+j+k, msbi);

                const double complex a = f[ai], b = wn*f[bi];
                f[ai] = a + b;
                f[bi] = a - b;
                wn *= w;
            }
        }
    }
    for(int i=0; i<K; i++) {
        const int j = bitrev(i,msbi);
        if(j>=i) continue;
        const double complex t = f[i];
        f[i] = f[j];
        f[j] = t;
    }
    return;
}

void ifft (double complex f[], int K) {
    for(int i=0; i<K; i++)
        f[i] = conj(f[i]);
    fft(f, K);
    for(int i=0; i<K; i++)
        f[i] = conj(f[i]) / K;
}

void naive (double complex f[], int K) {
    double complex F[K];
    for(int i=0; i<K; i++) {
        F[i] = 0;
        for(int j=0; j<K; j++) {
            F[i] += f[j] * cexp( -I * 2.0*M_PI/K * i*j );
        }
    }
    memcpy(f, F, sizeof(F));
}

int main(void) {
    memset(f, 0, sizeof(f));
    memset(g, 0, sizeof(g));
    memset(h, 0, sizeof(h));

    int n;
    scanf("%d",&n);
    for(int i=1; i<=n; i++) {
#define K (8192)
        double a,b;
        scanf("%lf%lf", &a, &b);
        f[i] = a + 0 * I;
        g[i] = b + 0 * I;
    }

    fft(f, K);
    fft(g, K);

    for(int i=0; i<K; i++)
        h[i] = f[i] * g[i];

    ifft(h, K);

    for(int i=1; i<=2*n; i++)
        printf("%d\n", (int)round(creal(h[i])));
#undef K

    return 0;
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User cookies
Language C (GCC 5.4.1)
Score 0
Code Size 2356 Byte
Status RE
Exec Time 101 ms
Memory 640 KB

Compile Error

./Main.c: In function ‘main’:
./Main.c:77:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ^
./Main.c:81:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lf%lf", &a, &b);
         ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 100
Status
AC × 1
AC × 22
WA × 1
RE × 10
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 6 ms 640 KB
01_00_01 AC 4 ms 512 KB
01_01_19 AC 4 ms 512 KB
01_02_31 AC 4 ms 512 KB
01_03_22 AC 4 ms 512 KB
01_04_31 AC 4 ms 512 KB
01_05_40 AC 4 ms 512 KB
01_06_15 AC 4 ms 512 KB
01_07_39 AC 4 ms 512 KB
01_08_28 AC 4 ms 512 KB
01_09_30 AC 4 ms 512 KB
01_10_23 AC 4 ms 512 KB
01_11_33 AC 4 ms 512 KB
01_12_11 AC 4 ms 512 KB
01_13_28 AC 4 ms 512 KB
01_14_41 AC 4 ms 512 KB
01_15_26 AC 4 ms 512 KB
01_16_49 AC 4 ms 512 KB
01_17_34 AC 4 ms 512 KB
01_18_02 AC 4 ms 512 KB
01_19_33 AC 4 ms 512 KB
01_20_29 AC 4 ms 512 KB
02_00_51254 RE 100 ms 512 KB
02_01_82431 RE 99 ms 512 KB
02_02_17056 RE 99 ms 512 KB
02_03_34866 RE 101 ms 512 KB
02_04_6779 WA 7 ms 640 KB
02_05_65534 RE 98 ms 512 KB
02_06_65535 RE 99 ms 512 KB
02_07_65536 RE 99 ms 512 KB
02_08_65537 RE 99 ms 512 KB
02_09_65538 RE 98 ms 512 KB
02_10_100000 RE 98 ms 512 KB