Submission #1139153

---

Source Code Expand

#include <stdio.h>
#include <complex.h>

#define PI2 6.28318530717958647692

const int k = 18;
const int m = (1 << 18);

typedef double complex cmplx;

cmplx C[1<<18];
cmplx w[1<<17];


const char mod5[500] = {
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,
0,1,2,3,4,0,1,2,3,4,0,1,2,3,4,0,1,2,3,4
};

const char div5[500] = {
0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6,7,7,7,7,7,8,8,8,8,8,9,9,9,9,9,10,10,10,10,10,
11,11,11,11,11,12,12,12,12,12,13,13,13,13,13,14,14,14,14,14,15,15,15,15,15,16,16,16,16,16,17,17,17,17,17,18,18,18,18,18,
19,19,19,19,19,20,20,20,20,20,21,21,21,21,21,22,22,22,22,22,23,23,23,23,23,24,24,24,24,24,25,25,25,25,25,26,26,26,26,26,
27,27,27,27,27,28,28,28,28,28,29,29,29,29,29,30,30,30,30,30,31,31,31,31,31,32,32,32,32,32,33,33,33,33,33,34,34,34,34,34,
35,35,35,35,35,36,36,36,36,36,37,37,37,37,37,38,38,38,38,38,39,39,39,39,39,40,40,40,40,40,41,41,41,41,41,42,42,42,42,42,
43,43,43,43,43,44,44,44,44,44,45,45,45,45,45,46,46,46,46,46,47,47,47,47,47,48,48,48,48,48,49,49,49,49,49,50,50,50,50,50,
51,51,51,51,51,52,52,52,52,52,53,53,53,53,53,54,54,54,54,54,55,55,55,55,55,56,56,56,56,56,57,57,57,57,57,58,58,58,58,58,
59,59,59,59,59,60,60,60,60,60,61,61,61,61,61,62,62,62,62,62,63,63,63,63,63,64,64,64,64,64,65,65,65,65,65,66,66,66,66,66,
67,67,67,67,67,68,68,68,68,68,69,69,69,69,69,70,70,70,70,70,71,71,71,71,71,72,72,72,72,72,73,73,73,73,73,74,74,74,74,74,
75,75,75,75,75,76,76,76,76,76,77,77,77,77,77,78,78,78,78,78,79,79,79,79,79,80,80,80,80,80,81,81,81,81,81,82,82,82,82,82,
83,83,83,83,83,84,84,84,84,84,85,85,85,85,85,86,86,86,86,86,87,87,87,87,87,88,88,88,88,88,89,89,89,89,89,90,90,90,90,90,
91,91,91,91,91,92,92,92,92,92,93,93,93,93,93,94,94,94,94,94,95,95,95,95,95,96,96,96,96,96,97,97,97,97,97,98,98,98,98,98,99,99,99,99,99,
};


void read_int(int *x){
  char c=0;
  while(c<'0'||c>'9') c = getchar_unlocked();

  *x = c-'0';
  c = getchar_unlocked();

  while(c>='0'&&c<='9') {
    *x *= 10;
    *x += c-'0';
    c = getchar_unlocked();
  }
}

void write_int(int x){
  int i;
  static char buf[13]="           \n";
  if(x==0){
    fputs_unlocked("0\n", stdout);
    return;
  }

  for(i=10; x; i--){
    if(x >= 1000){
      buf[i] = '0' + x % 10;
      x /= 10;
    }
    else {
      buf[i] = '0' + (mod5[x>>1]<<1) + (x&1);
      x = div5[x>>1];
    }
  }
  fputs_unlocked(buf+1+i, stdout);
}

unsigned minus(unsigned x) {
  int y = 1 << (31-__builtin_clz(x));
  return (~x&(y-1))^y;
}


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

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

void genw(int i, int b, cmplx z){
  if(b == 0){
    w[i] = z;
  }
  else {
    genw(i, b>>1, z);
    genw(i|b, b>>1, z*w[b]);
  }
}

int main(){
  int n;
  const double arg = -PI2/m;

  for(int i=1, j=m/4; j; i<<=1, j>>=1){
    w[i] = cexp(I * (arg * j));
  }
  genw(0, m/4, 1);

  read_int(&n);
  for(int i=1;i<=n;i++){
    int a, b;
    read_int(&a);
    read_int(&b);
    C[i] = a + b*I;
  }
//  k = 33 - __builtin_clz(n);
//  m = 1 << k;

  fft(C, k);

  C[0] = 4 * creal(C[0]) * cimag(C[0]) * I;
  C[1] = 4 * creal(C[1]) * cimag(C[1]) * I;

  for(int i = 2; i < m; i+=2){
    int j = minus(i);
    C[i] = (C[i] + conj(C[j]))*(C[i] - conj(C[j]));
    C[j] = -conj(C[i]);
  }

  for(int i = 0; i < m; i+=2){
    C[i/2] = C[i]+C[i^1] + (C[i]-C[i^1])*w[i/2]*I;
  }

  ifft(C, k-1);

  for(int i=1;i<=n;i++){
    write_int(-creal(C[i])/(4*m)+0.5);
    write_int(cimag(C[i])/(4*m)+0.5);
  }
}

Submission Info

Compile Error

./Main.c:65:5: warning: implicit declaration of function 'fputs_unlocked' is invalid in C99 [-Wimplicit-function-declaration]
    fputs_unlocked("0\n", stdout);
    ^
1 warning generated.

Judge Result