Submission details
Task:A TIMES B!
Sender:ind1f
Submission time:2025-10-29 17:43:19 +0200
Language:C++ (C++17)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'std::vector<int> multiply(const std::vector<int>&, const std::vector<int>&)':
input/code.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   while (n < a.size() + b.size())
      |          ~~^~~~~~~~~~~~~~~~~~~~~
input/code.cpp: In function 'int main()':
input/code.cpp:64:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |   for (int i = 0; i < s.size(); i++) {
      |                   ~~^~~~~~~~~~
input/code.cpp:67:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   for (int i = 0; i < t.size(); i++) {
      |                   ~~^~~~~~~~~~
input/code.cpp:79:3: error: 'reverse' was not...

Code

#include <iostream>
#include <complex>
#include <vector>

using namespace std;

using cd = complex<double>;
const double PI = acos(-1);

void fft(vector<cd> & a, bool invert) {
  int n = a.size();
  if (n == 1) {
    return;
  }

  vector<cd> a0(n / 2), a1(n / 2);
  for (int i = 0; 2 * i < n; i++) {
    a0[i] = a[2 * i];
    a1[i] = a[2 * i + 1];
  }
  fft(a0, invert);
  fft(a1, invert);

  double ang = 2 * PI / n * (invert ? -1 : 1);
  cd w(1), wn(cos(ang), sin(ang));
  for (int i = 0; 2 * i < n; i++) {
    a[i] = a0[i] + w * a1[i];
    a[i + n/2] = a0[i] - w * a1[i];
    if (invert) {
      a[i] /= 2;
      a[i + n / 2] /= 2;
    }
    w *= wn;
  }
}

vector<int> multiply(vector<int> const& a, vector<int> const& b) {
  vector<cd> fa(a.begin(), a.end()), fb(b.begin(), b.end());
  int n = 1;
  while (n < a.size() + b.size()) 
    n <<= 1;
  fa.resize(n);
  fb.resize(n);

  fft(fa, false);
  fft(fb, false);
  for (int i = 0; i < n; i++)
    fa[i] *= fb[i];
  fft(fa, true);

  vector<int> result(n);
  for (int i = 0; i < n; i++) {
    result[i] = round(fa[i].real());
  }
  return result;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s, t;
  cin >> s >> t;
  vector<int> a(s.size()), b(t.size());
  for (int i = 0; i < s.size(); i++) {
    a[i] = s[i] - '0';
  }
  for (int i = 0; i < t.size(); i++) {
    b[i] = t[i] - '0';
  }
  vector<int> c = multiply(a, b);
  int ca = 0;
  string ans;
  for (int &i : c) {
    i += ca;
    ca = i / 10;
    i %= 10;
    ans += (i + '0');
  }
  reverse(ans.begin(), ans.end());
  cout << ans << '\n';
  return 0;
}