AtCoder Typical Contest 001

Submission #10099546

Source codeソースコード

#include <vector>
#include <cmath>
#include <utility>

namespace fast_fourier_transform {
  using dbl = double;
  constexpr dbl pi = acosl(-1.0L);

  struct complex {
    dbl re, im;
    complex(dbl re_ = 0, dbl im_ = 0): re(re_), im(im_) { }
    inline complex operator + (const complex &rhs) const { 
      return complex(re + rhs.re, im + rhs.im); 
    }
    inline complex operator - (const complex &rhs) const { 
      return complex(re - rhs.re, im - rhs.im); 
    }
    inline complex operator * (const complex &rhs) const { 
      return complex(re * rhs.re - im * rhs.im, re * rhs.im + im * rhs.re); 
    }
  };

  int size;
  std::vector<complex> root;
  void reserve(int size_) {
    size = 1;
    while (size < size_) {
      size <<= 1;
    }
    root.assign(size + 1, complex());
    for (int i = 0; i <= size; ++i) {
      dbl angle = pi * 2.0L / size * i;
      root[i] = complex(cosl(angle), sinl(angle));
    }
  }

  void discrete_fourier_transform(std::vector<complex> &F) {
    for (int i = 0, j = 1; j + 1 < size; ++j) {
      int k = size >> 1;
      while (k > (i ^= k)) {
        k >>= 1;
      }
      if (i < j) {
        std::swap(F[i], F[j]);
      }
    }
    int idx;
    complex first, second;
    for (int len = 1, bit = (size >> 1); len < size; len <<= 1, bit >>= 1) {
      for (int k = 0; k < size; k += (len << 1)) {
        idx = 0;
        for (int i = 0; i < len; ++i) {
          first = F[i + k];
          second = F[(i + k) ^ len];
          F[i + k] = root[0] * first + root[idx] * second;
          F[(i + k) ^ len] = root[0] * first + root[idx + (size >> 1)] * second;
          idx += bit;
        }
      }
    }
  }

  void inverse_discrete_fourier_transform(std::vector<complex> &F) {
    for (int i = 0, j = 1; j + 1 < size; ++j) {
      int k = size >> 1;
      while (k > (i ^= k)) {
        k >>= 1;
      }
      if (i < j) {
        std::swap(F[i], F[j]);
      }
    }
    int idx;
    complex first, second;
    for (int len = 1, bit = (size >> 1); len < size; len <<= 1, bit >>= 1) {
      for (int k = 0; k < size; k += (len << 1)) {
        idx = size;
        for (int i = 0; i < len; ++i) {
          first = F[i + k];
          second = F[(i + k) ^ len];
          F[i + k] = root[size] * first + root[idx] * second;
          F[(i + k) ^ len] = root[size] * first + root[idx - (size >> 1)] * second;
          idx -= bit;
        }
      }
    }
  }

  template <class T>
  std::vector<T> convolve(const std::vector<T> &A, const std::vector<T> &B) {
    int res_size = A.size() + B.size() - 1;
    reserve(res_size);
    std::vector<complex> C(size), D(size);
    for (int i = 0; i < A.size(); ++i) {
      C[i].re = static_cast<dbl>(A[i]);
    }
    for (int i = 0; i < B.size(); ++i) {
      D[i].re = static_cast<dbl>(B[i]);
    }
    discrete_fourier_transform(C);
    discrete_fourier_transform(D);
    for (int i = 0; i < size; ++i) {
      C[i] = C[i] * D[i];
    }
    inverse_discrete_fourier_transform(C);
    std::vector<T> res(res_size);
    for (int i = 0; i < res_size; ++i) {
      res[i] = static_cast<T>(C[i].re / size + 0.5L);
    }
    return res;
    return std::vector<T>();
  }

};

#include <cstdio>
int main() {
  int N;
  scanf("%d", &N);
  std::vector<int> A(N), B(N);
  for (int i = 0; i < N; ++i) {
    scanf("%d %d", &A[i], &B[i]);
  }
  std::vector<int> answer = fast_fourier_transform::convolve(A, B);
  puts("0");
  for (int x: answer) {
    printf("%d\n", x);
  }
  return 0;
}

Submission

Task問題 C - 高速フーリエ変換
User nameユーザ名 Kodaman
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 3607 Byte
File nameファイル名
Exec time実行時間 149 ms
Memory usageメモリ使用量 14080 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main()’:
./Main.cpp:119:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:122:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &A[i], &B[i]);
^

Test case

Set

Set name Score得点 / Max score Cases
Sample - 00_sample_01
All 100 / 100 00_sample_01,01_00_01,01_01_19,01_02_31,01_03_22,01_04_31,01_05_40,01_06_15,01_07_39,01_08_28,01_09_30,01_10_23,01_11_33,01_12_11,01_13_28,01_14_41,01_15_26,01_16_49,01_17_34,01_18_02,01_19_33,01_20_29,02_00_51254,02_01_82431,02_02_17056,02_03_34866,02_04_6779,02_05_65534,02_06_65535,02_07_65536,02_08_65537,02_09_65538,02_10_100000

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
00_sample_01 AC 1 ms 256 KB
01_00_01 AC 1 ms 256 KB
01_01_19 AC 1 ms 256 KB
01_02_31 AC 1 ms 256 KB
01_03_22 AC 1 ms 256 KB
01_04_31 AC 1 ms 256 KB
01_05_40 AC 1 ms 256 KB
01_06_15 AC 1 ms 256 KB
01_07_39 AC 1 ms 256 KB
01_08_28 AC 1 ms 256 KB
01_09_30 AC 1 ms 256 KB
01_10_23 AC 1 ms 256 KB
01_11_33 AC 1 ms 256 KB
01_12_11 AC 1 ms 256 KB
01_13_28 AC 1 ms 256 KB
01_14_41 AC 1 ms 256 KB
01_15_26 AC 1 ms 256 KB
01_16_49 AC 1 ms 256 KB
01_17_34 AC 1 ms 256 KB
01_18_02 AC 1 ms 256 KB
01_19_33 AC 1 ms 256 KB
01_20_29 AC 1 ms 256 KB
02_00_51254 AC 76 ms 7168 KB
02_01_82431 AC 143 ms 13824 KB
02_02_17056 AC 33 ms 3584 KB
02_03_34866 AC 70 ms 6912 KB
02_04_6779 AC 9 ms 1152 KB
02_05_65534 AC 80 ms 7424 KB
02_06_65535 AC 80 ms 7424 KB
02_07_65536 AC 80 ms 7424 KB
02_08_65537 AC 139 ms 13568 KB
02_09_65538 AC 137 ms 13568 KB
02_10_100000 AC 149 ms 14080 KB