Submission #977595


Source Code Expand

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

int m;
int k;

typedef std::complex<double> complex;

complex A[1<<18];
complex B[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;
   x = x ^ mm;
   if ((int)x >= 0) {
      do {
         mm = mm >> 1;
         x = x ^ mm;
      } while (x < mm);
   }
   return x;
}
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 jl=0;jl<v;jl++){
        int j = (jh << i) | jl;
        complex Aj  = A[j];
        complex Ajv = wj * A[j|v];
        A[j]   = Aj + Ajv;
        A[j|v] = Aj - 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 jl=0;jl<v;jl++){
        int j = (jh << i) | jl;
        complex Aj  = A[j] + A[j|v];
        complex Ajv = A[j] - A[j|v];
        A[j]   = Aj;
        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);
    A[i] = a;
    B[i] = 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(A);
  fft(B);
  for(int i=0;i<m;i++){
    A[i] *= B[i];
  }
  ifft(A);
  for(int i=1;i<=2*n;i++){
    std::printf("%d\n", (int) ((A[i].real()+0.5)/m));
  }
}


Submission Info

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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:76:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d", &n);
                       ^
./Main.cpp:79: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 31 ms 13084 KB
01_00_01 AC 32 ms 13084 KB
01_01_19 AC 33 ms 13088 KB
01_02_31 AC 32 ms 13080 KB
01_03_22 AC 32 ms 13044 KB
01_04_31 AC 34 ms 13084 KB
01_05_40 AC 33 ms 13088 KB
01_06_15 AC 35 ms 13088 KB
01_07_39 AC 33 ms 13080 KB
01_08_28 AC 34 ms 12964 KB
01_09_30 AC 34 ms 12964 KB
01_10_23 AC 33 ms 13088 KB
01_11_33 AC 33 ms 12956 KB
01_12_11 AC 33 ms 13216 KB
01_13_28 AC 33 ms 13088 KB
01_14_41 AC 34 ms 12968 KB
01_15_26 AC 32 ms 13204 KB
01_16_49 AC 33 ms 13092 KB
01_17_34 AC 33 ms 13088 KB
01_18_02 AC 34 ms 13088 KB
01_19_33 AC 33 ms 13084 KB
01_20_29 AC 34 ms 12960 KB
02_00_51254 AC 111 ms 13096 KB
02_01_82431 AC 171 ms 13044 KB
02_02_17056 AC 62 ms 13088 KB
02_03_34866 AC 92 ms 12960 KB
02_04_6779 AC 41 ms 13212 KB
02_05_65534 AC 128 ms 12960 KB
02_06_65535 AC 126 ms 13044 KB
02_07_65536 AC 155 ms 13080 KB
02_08_65537 AC 154 ms 13084 KB
02_09_65538 AC 156 ms 13092 KB
02_10_100000 AC 191 ms 13092 KB