Submission #977573

---

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 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 v = m/2;
  for(int i=k-1;i>=0;i--){
    int j = m;
    while(j){
      j = (j-1)&~v;
      complex Aj  = A[j];
      complex Ajv = A[j|v];
      A[j]   = Aj + w[j>>i]*Ajv;
      A[j|v] = Aj - w[j>>i]*Ajv;
    }
    v >>= 1;
  }
}

void ifft(complex *A){
  int v = 1;
  for(int i=0;i<k;i++){
    int j = m;
    while(j){
      j = (j-1)&~v;
      complex Aj  = A[j];
      complex Ajv = A[j|v];
      A[j]   = Aj + Ajv;
      A[j|v] = (Aj - Ajv)*std::conj(w[j>>i]);
    }
    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;i<m;i++){
    w[i] = std::polar(1.0, arg * rev(i));
  }
  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

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:66:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   std::scanf("%d", &n);
                       ^
./Main.cpp:69: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