Submission #1143636

---

Source Code Expand

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

#define PI2 6.28318530717958647692

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

typedef double complex cmplx;

cmplx C[1<<k];
cmplx w[1<<(k-1)];


const int mod10[200] = {
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,
0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9,0,1,2,3,4,5,6,7,8,9
};

const int div10[200] = {
0,0,0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,
10,10,10,10,10,10,10,10,10,10,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,
14,14,14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,17,17,17,17,17,17,17,17,17,17,
18,18,18,18,18,18,18,18,18,18,19,19,19,19,19,19,19,19,19,19
};



void read_uint(int *x){
  char c=0;
  while(c<'0') c = getchar_unlocked();

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

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

void write_uint(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 >= 200){
      buf[i] = '0' + x % 10;
      x /= 10;
    }
    else {
      buf[i] = '0' + mod10[x];
      x = div10[x];
    }
  }
  fputs_unlocked(buf+1+i, stdout);
}

void fft4(cmplx *A, int k){
  const int m = 1 << k;
  int u = 1;
  int v = m/4;
  for(int i=k;i>0;i-=2){
    for(int jh=0;jh<u;jh++){
      cmplx wj = w[jh<<1];
      cmplx wj2 = w[jh];
      cmplx wj3 = wj2 * wj;
      for(int j = jh << i, je = j+v;j<je; j++){
        cmplx tmp0 = A[j];
        cmplx tmp1 = wj * A[j|v];
        cmplx tmp2 = wj2 * A[j|(v<<1)];
        cmplx tmp3 = wj3 * A[j|(v<<1)|v];

        cmplx ttmp0 = tmp0 + tmp2;
        cmplx ttmp2 = tmp0 - tmp2;
        cmplx ttmp1 = tmp1 + tmp3;
        cmplx ttmp3 = -I * (tmp1 - tmp3);

        A[j] = ttmp0 + ttmp1;
        A[j|v] = ttmp0 - ttmp1;
        A[j|(v<<1)] = ttmp2 + ttmp3;
        A[j|(v<<1)|v] = ttmp2 - ttmp3;
      }
    }
    u <<= 2;
    v >>= 2;
  }
}

void ifft4(cmplx *A, int k){
  const int m = 1 << k;
  int u = m/4;
  int v = 1;
  for(int i=2;i<=k;i+=2){
    for(int jh=0;jh<u;jh++){
      cmplx wj = conj(w[jh<<1]);
      cmplx wj2 = conj(w[jh]);
      cmplx wj3 = wj2 * wj;
      for(int j = jh << i, je = j+v;j<je; j++){
        cmplx tmp0 = A[j];
        cmplx tmp1 = A[j|v];
        cmplx tmp2 = A[j|(v<<1)];
        cmplx tmp3 = A[j|(v<<1)|v];

        cmplx ttmp0 = tmp0 + tmp1;
        cmplx ttmp1 = tmp0 - tmp1;
        cmplx ttmp2 = tmp2 + tmp3;
        cmplx ttmp3 = I * (tmp2 - tmp3);

        A[j] = ttmp0 + ttmp2;
        A[j|v] = wj * (ttmp1 + ttmp3);
        A[j|(v<<1)] = wj2 * (ttmp0 - ttmp2);
        A[j|(v<<1)|v] = wj3 * (ttmp1 - ttmp3);
      }
    }
    u >>= 2;
    v <<= 2;
  }
  if(k&1){
    for(int j = 0;j<m/2; j++){
      cmplx Ajv = A[j|(m/2)];
      A[j|(m/2)] = A[j] - Ajv;
      A[j] += Ajv;
    }
  }
}

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_uint(&n);
  for(int i=1;i<=n;i++){
    int a, b;
    read_uint(&a);
    read_uint(&b);
    C[i] = a + b*I;
  }
//  k = 33 - __builtin_clz(n);
//  m = 1 << k;

  fft4(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 y = 1 << (31-__builtin_clz(i));
    int j = i^(y-1);
    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;
  }

  ifft4(C, k-1);

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

Submission Info

Compile Error

./Main.c:50: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