結果

問題 No.206 数の積集合を求めるクエリ
ユーザー Ryuhei MoriRyuhei Mori
提出日時 2018-07-22 00:42:18
言語 C
(gcc 12.3.0)
結果
AC  
実行時間 14 ms / 7,000 ms
コード長 4,291 bytes
コンパイル時間 878 ms
コンパイル使用メモリ 37,244 KB
実行使用メモリ 6,528 KB
最終ジャッジ日時 2024-06-07 20:08:39
合計ジャッジ時間 2,214 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 8 ms
5,248 KB
testcase_01 AC 8 ms
5,376 KB
testcase_02 AC 8 ms
5,376 KB
testcase_03 AC 8 ms
5,376 KB
testcase_04 AC 8 ms
5,376 KB
testcase_05 AC 8 ms
5,376 KB
testcase_06 AC 8 ms
5,376 KB
testcase_07 AC 9 ms
5,376 KB
testcase_08 AC 9 ms
5,376 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 9 ms
5,376 KB
testcase_11 AC 8 ms
5,376 KB
testcase_12 AC 8 ms
5,376 KB
testcase_13 AC 8 ms
5,376 KB
testcase_14 AC 9 ms
5,376 KB
testcase_15 AC 9 ms
5,376 KB
testcase_16 AC 9 ms
5,376 KB
testcase_17 AC 12 ms
5,888 KB
testcase_18 AC 9 ms
5,376 KB
testcase_19 AC 12 ms
5,888 KB
testcase_20 AC 11 ms
5,504 KB
testcase_21 AC 11 ms
5,504 KB
testcase_22 AC 11 ms
5,504 KB
testcase_23 AC 12 ms
5,888 KB
testcase_24 AC 14 ms
6,528 KB
testcase_25 AC 14 ms
6,400 KB
testcase_26 AC 13 ms
5,888 KB
testcase_27 AC 11 ms
5,632 KB
testcase_28 AC 14 ms
6,016 KB
testcase_29 AC 13 ms
6,144 KB
testcase_30 AC 13 ms
5,888 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <unistd.h>
#include <complex.h>

#define PI2 6.28318530717958647692

char ibuf[1200100];
char *ibufe = ibuf-1;

void readall(){
  int k, t = 0;
  while((k=read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t))>0) t += k;
}

int read_uint(){
  int x=0;
  while(*(++ibufe) <'0');
  do {
    x *= 10;
    x += *ibufe-'0';
  } while(*(++ibufe) >='0');

  return x;
}

char buf[700000];
char *bufe = buf;

void write_uintln(int x){
  int i;
  static char tmp[13];
  if(x==0){
    *bufe++ = '0';
    *bufe++ = '\n';
    return;
  }

  for(i=0; x; i++){
    tmp[i] = '0' + x % 10;
    x /= 10;
  }
  for(i--; i >= 0; i--){
    *bufe++ = tmp[i];
  }
  *bufe++ = '\n';
}

void writeall(){
  int k, t = 0;
  while((k=write(STDOUT_FILENO, buf+t, bufe-buf-t))>0) t += k;
}


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

typedef double complex cmplx;

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


void fft(int k, cmplx *A, const cmplx *w){
  const int m = 1 << k;
  int u = 1;
  int v = m/4;
  int i, j;
  if(k&1){
    for(j=0; j<m/2; j++){
      cmplx Ajv = A[j|(m/2)];
      A[j|(m/2)] = A[j] - Ajv;
      A[j] += Ajv;
    }
    u <<= 1;
    v >>= 1;
  }
  for(i=k&~1;i>0;i-=2){
    int jh;
    for(jh=0;jh<u;jh++){
      cmplx wj = w[jh<<1];
      cmplx wj2 = w[jh];
      cmplx wj3 = wj2 * wj;
      int je;
      for(j = jh << i, je = j+v;j<je; j++){
        cmplx tmp0 = A[j];
        cmplx tmp1 = wj * A[j+v];
        cmplx tmp2 = wj2 * A[j+2*v];
        cmplx tmp3 = wj3 * A[j+3*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+2*v] = ttmp2 + ttmp3;
        A[j+3*v] = ttmp2 - ttmp3;
      }
    }
    u <<= 2;
    v >>= 2;
  }
}


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

void convolver(int k, cmplx *A, const cmplx *w){
  int i;
  const int m = 1 << k;

  fft(k, A, w);
  A[0] = 4 * creal(A[0]) * cimag(A[0]) * I;
  A[1] = 4 * creal(A[1]) * cimag(A[1]) * I;
  for(i = 2; i < m; i+=2){
    int y = 1 << (31-__builtin_clz(i));
    int j = i^(y-1);
    A[i] = (A[i] + conj(A[j]))*(A[i] - conj(A[j]));
    A[j] = -conj(A[i]);
  }

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

  ifft(k-1, A, w);
}


int main(){
  int l, mm, q;
  int i, j;
  const double arg = -PI2/m;
  const int B = 100009;

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

  readall();
  l = read_uint();
  mm = read_uint();
  read_uint();


  for(i=0;i<l;i++){
    int a;
    a = read_uint();
    if(a&1) C[a/2] += B;
    else    C[a/2] += 1;
  }
  for(i=0;i<mm;i++){
    int a;
    a = read_uint();
    if(a&1) C[((1<<18)-a)/2] += B*I;
    else    C[((1<<18)-a)/2] += I;
  }

  q = read_uint();

  convolver(k, C, w);

  int carry=0;
  for(i=0, j=0;4*i<q+2;i++){
    unsigned long long int tmp = creal(C[i])+carry+0.480;
    if(i&&j<q){
      write_uintln(tmp % B);
      j++;
    }
    tmp /= B;
    if(i&&j<q){ write_uintln(tmp%B);
      j++;
    }
    carry = tmp/B;
    tmp = cimag(C[i])+carry+0.480;
    if(j<q) write_uintln(tmp%B);
    j++;
    tmp /= B;
    if(j<q) write_uintln(tmp%B);
    j++;
    carry = tmp/B;
  }
  writeall();

  return 0;
}
0