AtCoder Typical Contest 001

Submission #1135020

Source codeソースコード

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <vector>

#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define pb push_back
#define all(v) begin(v), end(v)
#define debug(x) //cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
template<class T> using vv=vector<vector< T > >;

#include <complex>
#define EPS 0.5

// cout vector
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size(); s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i]; if (i < len - 1) s << "\t";
  }
  s << "\n"; return s;
}


int power_of_2(int m) {
  int cnt = 0;
  while (m > 0) {
    cnt += 1;
    m >>= 1;
  }
  return 1 << cnt;
}

template<typename T>
void extend_vector(vector<T> *x, int m) {
  int m_ = (int)(*x).size();
  assert (m_ <= m);
  vector<T> tmp = *x;
  (*x).assign(m, T());
  for (int i = 0; i < m_; ++i) {
    (*x)[i] = tmp[i];
  }
}

typedef complex<double> cd;
typedef vector<cd> vcd;

vcd dft(vcd f, int n) {
  if (n == 1) {
    return f;
  }
  vcd f0(n/2), f1(n/2);
  rep (i, n/2) {
    f0[i] = f[2 * i + 0];
    f1[i] = f[2 * i + 1];
  }
  vcd f0_ = dft(f0, n/2);
  vcd f1_ = dft(f1, n/2);
  cd zeta(cos(2 * M_PI / n), sin(2 * M_PI / n));
  cd pow_zeta(1, 0);
  rep (i, n) {
    f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
    pow_zeta *= zeta;
  }
  return f;
}

vcd inverse_dft(vcd f, int n) {
  if (n == 1) {
    return f;
  }
  vcd f0(n/2), f1(n/2);
  rep (i, n/2) {
    f0[i] = f[2 * i + 0];
    f1[i] = f[2 * i + 1];
  }
  vcd f0_ = dft(f0, n/2);
  vcd f1_ = dft(f1, n/2);
  cd zeta(cos(2 * M_PI / n), -sin(2 * M_PI / n));
  cd pow_zeta(1, 0);
  rep (i, n) {
    f[i] = (f0_[i % (n/2)] + pow_zeta * f1_[i % (n/2)]);
    pow_zeta *= zeta;
  }
  return f;
}

vll solve(vll g, vll h) {
  int ng, nh;
  ng = (int)g.size();
  nh = (int)h.size();
  int n = power_of_2(ng + nh + 1);
  extend_vector(&g, n);
  extend_vector(&h, n);
  vcd g_(n), h_(n);
  rep (i, n) {
    g_[i] = cd(g[i], 0);
  }
  rep (i, n) {
    h_[i] = cd(h[i], 0);
  }
  vcd gg = dft(g_, n);
  vcd hh = dft(h_, n);
  debug(gg);
  debug(hh);

  vcd ff(n);
  rep (i, n) {
    ff[i] = gg[i] * hh[i];
  }
  debug(ff);
  // vcd f = inverse_dft(ff, n);
  vcd f = dft(ff, n);
  reverse(all(f));
  rep (i, n) {
    f[i] /= n;
  }
  debug(f);
  vll ret(ng + nh);
  rep (i, ng + nh) {
    ret[i] = EPS + f[i].real();
  }

  return ret;
}

int n;
int n_;
vll a, b;

int main() {
  scanf("%d", &n_);
  n_ += 1;
  a.resize(n_);
  b.resize(n_);
  a[0] = b[0] = 0;
  FOR (i, 1, n_) {
    scanf("%lld %lld", &a[i], &b[i]);
  }

  vll f = solve(a, b);
  n_ -= 1;
  rep (i, 2 * n_) {
    printf("%lld\n", f[i]);
  }

  return 0;
}

Submission

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

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 2 ms 384 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 369 ms 23596 KB
02_01_82431 AC 755 ms 46664 KB
02_02_17056 AC 180 ms 11856 KB
02_03_34866 AC 364 ms 23332 KB
02_04_6779 AC 44 ms 3248 KB
02_05_65534 AC 375 ms 23908 KB
02_06_65535 AC 746 ms 46420 KB
02_07_65536 AC 746 ms 46420 KB
02_08_65537 AC 747 ms 46420 KB
02_09_65538 AC 752 ms 46420 KB
02_10_100000 AC 761 ms 46900 KB