Submission #977849


Source Code Expand

#include <iostream>
#include <cstdio>
#include <complex>
#include <cmath>

int m;
int k;

typedef std::complex<double> complex;

complex C[1<<18];
complex w[1<<18];

unsigned clp2(unsigned x) {
   x = x - 1;
   x = x | (x >> 1);
   x = x | (x >> 2);
   x = x | (x >> 4);
   x = x | (x >> 8);
   x = x | (x >>16);
   return x + 1;
}

unsigned increv(unsigned x) {
   unsigned mm=m/2;
   x = x ^ mm;
   if (x < mm) {
      do {
         mm >>= 1;
         x = x ^ mm;
      } while (x < mm);
   }
   return x;
}

unsigned rev(unsigned x) {
   x = (x & 0x55555555) <<  1 | (x >>  1) & 0x55555555;
   x = (x & 0x33333333) <<  2 | (x >>  2) & 0x33333333;
   x = (x & 0x0F0F0F0F) <<  4 | (x >>  4) & 0x0F0F0F0F;
   x = (x << 24) | ((x & 0xFF00) << 8) |
       ((x >> 8) & 0xFF00) | (x >> 24);
   return x >> (32-k);
}

void fft(complex *A){
  int u = 2;
  int v = m/2;
  for(int i=k-1;i>=0;i--){
    for(int jh=0;jh<u;jh+=2){
      complex wj = w[jh];
      for(int j = jh << i, je = (jh+1) << i;j<je; j++){
        complex Ajv = wj * A[j|v];
        A[j|v]  = A[j] - Ajv;
        A[j]   += Ajv;
      }
    }
    u <<= 1;
    v >>= 1;
  }
}

void ifft(complex *A){
  int u = m;
  int v = 1;
  for(int i=0;i<k;i++){
    for(int jh=0;jh<u;jh+=2){
      complex wj = std::conj(w[jh]);
      for(int j = jh << i, je = (jh+1) << i;j<je; j++){
        complex Ajv = A[j] - A[j|v];
        A[j] += A[j|v];
        A[j|v] = wj * Ajv;
      }
    }
    u >>= 1;
    v <<= 1;
  }
}

int main(){
  int n;
  std::scanf("%d", &n);
  for(int i=1;i<=n;i++){
    int a, b;
    std::scanf(" %d %d", &a, &b);
    C[i] = complex(a, b);
  }
  m = clp2(n+1) << 1;
  k = __builtin_ctz(m);
  double arg = -2*M_PI/m;
  for(int i=0, j=0;i<m;i++){
    w[i] = std::polar(1.0, arg * j);
    j = increv(j);
  }
  fft(C);
  C[0] = C[0].real() * C[0].imag();
  for(int i=m/2, j=m-1;i!=(m/2|1);j=(~i&(m-1)),i=increv(i)){
    C[i] = (C[i] + std::conj(C[j]))*(C[i] - std::conj(C[j]));
    C[j].real(C[i].imag()/4.0);
    C[j].imag(C[i].real()/4.0);
    C[i] = std::conj(C[j]);
  }
  ifft(C);
  for(int i=1;i<=2*n;i++){
    std::printf("%d\n", (int) ((C[i].real()+0.5)/m));
  }
}

Submission Info

Submission Time
Task C - 高速フーリエ変換
User ryuhei
Language C++ (GCC 4.9.2)
Score 100
Code Size 2246 Byte
Status AC
Exec Time 172 ms
Memory 9116 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:81:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d", &n);
                       ^
./Main.cpp:84:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     std::scanf(" %d %d", &a, &b);
                                 ^

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 26 ms 8988 KB
01_00_01 AC 29 ms 8948 KB
01_01_19 AC 27 ms 8948 KB
01_02_31 AC 27 ms 8944 KB
01_03_22 AC 28 ms 8984 KB
01_04_31 AC 27 ms 8992 KB
01_05_40 AC 28 ms 9116 KB
01_06_15 AC 27 ms 8988 KB
01_07_39 AC 29 ms 8984 KB
01_08_28 AC 29 ms 8868 KB
01_09_30 AC 27 ms 8948 KB
01_10_23 AC 28 ms 8868 KB
01_11_33 AC 27 ms 8992 KB
01_12_11 AC 29 ms 8988 KB
01_13_28 AC 28 ms 8992 KB
01_14_41 AC 28 ms 8864 KB
01_15_26 AC 28 ms 8864 KB
01_16_49 AC 27 ms 8984 KB
01_17_34 AC 27 ms 8988 KB
01_18_02 AC 29 ms 8948 KB
01_19_33 AC 28 ms 9116 KB
01_20_29 AC 26 ms 8992 KB
02_00_51254 AC 101 ms 8864 KB
02_01_82431 AC 154 ms 8992 KB
02_02_17056 AC 54 ms 8988 KB
02_03_34866 AC 82 ms 8996 KB
02_04_6779 AC 37 ms 8996 KB
02_05_65534 AC 113 ms 8924 KB
02_06_65535 AC 111 ms 8992 KB
02_07_65536 AC 136 ms 8992 KB
02_08_65537 AC 133 ms 8988 KB
02_09_65538 AC 131 ms 8992 KB
02_10_100000 AC 172 ms 8864 KB