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
2018-05-31 19:20:37+0900
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
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