結果

問題 No.206 数の積集合を求めるクエリ
ユーザー Ryuhei MoriRyuhei Mori
提出日時 2017-03-02 10:39:24
言語 C90
(gcc 11.4.0)
結果
AC  
実行時間 30 ms / 7,000 ms
コード長 2,381 bytes
コンパイル時間 582 ms
コンパイル使用メモリ 28,656 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2024-06-26 03:14:43
合計ジャッジ時間 3,124 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 19 ms
8,064 KB
testcase_01 AC 20 ms
7,808 KB
testcase_02 AC 20 ms
7,936 KB
testcase_03 AC 21 ms
7,936 KB
testcase_04 AC 21 ms
7,936 KB
testcase_05 AC 21 ms
8,064 KB
testcase_06 AC 21 ms
7,808 KB
testcase_07 AC 20 ms
7,936 KB
testcase_08 AC 19 ms
7,808 KB
testcase_09 AC 20 ms
7,808 KB
testcase_10 AC 21 ms
7,808 KB
testcase_11 AC 20 ms
7,936 KB
testcase_12 AC 21 ms
7,808 KB
testcase_13 AC 20 ms
7,808 KB
testcase_14 AC 21 ms
7,936 KB
testcase_15 AC 19 ms
7,808 KB
testcase_16 AC 19 ms
7,936 KB
testcase_17 AC 25 ms
7,808 KB
testcase_18 AC 23 ms
7,936 KB
testcase_19 AC 25 ms
7,808 KB
testcase_20 AC 23 ms
7,936 KB
testcase_21 AC 24 ms
7,936 KB
testcase_22 AC 24 ms
7,936 KB
testcase_23 AC 26 ms
7,808 KB
testcase_24 AC 30 ms
7,808 KB
testcase_25 AC 29 ms
7,808 KB
testcase_26 AC 27 ms
7,936 KB
testcase_27 AC 25 ms
7,936 KB
testcase_28 AC 28 ms
7,808 KB
testcase_29 AC 28 ms
7,808 KB
testcase_30 AC 27 ms
7,808 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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];

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

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

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

void write_int(int x){
  int i;
  static char buf[12];
  if(x==0){
    puts("0");
    return;
  }

  for(i=10; x; i--){
    buf[i] = '0' + x % 10;
    x /= 10;
  }
  puts(buf+1+i);
}

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;
  int i, jh, j, je;
  for(i=k;i>0;i--){
    for(jh=0;jh<u;jh++){
      cmplx wj = w[jh];
      for(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;
  int i, jh, j, je;
  for(i=1;i<=k;i++){
    for(jh=0;jh<u;jh++){
      cmplx wj = conj(w[jh]);
      for(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 l, mm, n, q;
  int i, j;
  const double arg = -PI2/m;

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

  read_int(&l);
  read_int(&mm);
  read_int(&n);


  for(i=0;i<l;i++){
    int a;
    read_int(&a);
    C[a] = 1;
  }
  for(i=0;i<mm;i++){
    int a;
    read_int(&a);
    C[(1<<18)-a] += I;
  }
  read_int(&q);

  fft(C, k);

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

  for(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(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);

  write_int(cimag(C[0])/(4*m)+0.5);
  for(i=1;2*i<q;i++){
    write_int(-creal(C[i])/(4*m)+0.5);
    write_int(cimag(C[i])/(4*m)+0.5);
  }
  if(!(q&1)) write_int(-creal(C[q/2])/(4*m)+0.5);

  return 0;
}
0