Karatsuba non-recursion

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#include <iostream>
#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <set>
#include <map>
#include <math.h>
#include <cmath>
#include <string>
#include <time.h>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <string.h>
#include <complex>
#include <ctime>
using namespace std;

#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
//#define cin in
//#define cout out
#define pii pair<int,int>
//#define ll long long
#define db double
#define ld long double
#define uset unordered_set
#define umap unordered_map
#define vec vector
#define ms multiset
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution

typedef long long ll;
typedef unsigned int uint;

ifstream in("input.txt");
ofstream out("output.txt");

//simple polynomial multiplication O(N^2), given polynoms have to be formatted for Karatsuba algorithm
void simp_mult(vector<uint>& a, vector<uint>& b, vector<uint>& res) {
    int n = a.size();
    vector<uint> ans(2 * n - 1, 0);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            ans[i + j] = ans[i + j] + a[i] * b[j];

    res.resize(2 * n - 1);
    for (int i = 0; i < ans.size(); i++)
        res[i] = ans[i];
}

//simple polynomial addition O(N), given polynoms have to be formatted for Karatsuba algorithm
void simp_add(vector<uint>& a, vector<uint>& b, vector<uint>& res) {
    int n = a.size();
    res.resize(n);

    for (int i = 0; i < n; i++)
        res[i] = a[i] + b[i];
}

//simple polynomial substraction O(N), given polynoms have to be formatted for Karatsuba algorithm
void simp_subs(vector<uint>& a, vector<uint>& b, vector<uint>& res) {
    int n = a.size();
    res.resize(n);

    for (int i = 0; i < n; i++)
        res[i] = a[i] - b[i];
}

//format given polynoms for Karatsuba algorithm
void format(vector<uint>& a, vector<uint>& b) {
    int l = max(a.size(), b.size());
    int n = 1;
    while (n < l)
        n <<= 1;

    a.resize(n);
    b.resize(n);
}

struct unit {
    vector<uint>* a, * b, * res, * t1, * t2, * gamma;
    int sz;
    unit(vector<uint>* a, vector<uint>* b, vector<uint>* res) : a(a), b(b), res(res) {
        t1 = new vector<uint>();
        t2 = new vector<uint>();
        gamma = new vector<uint>();
        sz = a->size();
    }
};

void cnt(vector<uint>& res, vector<uint>& t1, vector<uint>& t2, vector<uint>& t3, int n) {
    int n2 = n / 2;

    res.assign((n << 1) - 1, 0);

    for (int i = 0; i < t1.size(); i++)
        res[i] = t1[i];

    for (int i = 0; i < t3.size(); i++)
        res[i + n2] = res[i + n2] + t3[i];

    for (int i = 0; i < t2.size(); i++)
        res[i + n] = res[i + n] + t2[i];
}

const int LIM = 512;

void karatsuba(vector<uint>& A, vector<uint>& B, vector<uint>& res) {
    deque<unit> units;

    int p = 0;
    units.push_back(unit(&A, &B, &res));

    //идём в одну сторону

    while (p < units.size()) {
        unit cur = units[p++];

        vector<uint>* A, * B, * res, * t1, * t2, * gamma;
        A = cur.a, B = cur.b, res = cur.res, t1 = cur.t1, t2 = cur.t2, gamma = cur.gamma;

        int n = cur.sz;
        if (n <= LIM)
            continue;

        int n2 = (n >> 1);

        vector<uint>* alpha = new vector<uint>(A->begin(), A->begin() + n2);
        vector<uint>* a = new vector<uint>(A->begin() + n2, A->end());
        vector<uint>* beta = new vector<uint>(B->begin(), B->begin() + n2);
        vector<uint>* b = new vector<uint>(B->begin() + n2, B->end());

        units.push_back(unit(alpha, beta, t1));
        units.push_back(unit(a, b, t2));

        vector<uint>* f_sum = new vector<uint>();
        vector<uint>* s_sum = new vector<uint>();
        simp_add(*alpha, *a, *f_sum);
        simp_add(*beta, *b, *s_sum);
        units.push_back(unit(f_sum, s_sum, gamma));

        vector<uint> t3;
        simp_subs(*gamma, *t1, t3);
        simp_subs(t3, *t2, t3);

        res->assign((n << 1) - 1, 0);

    }
    p--;
    //возвращаемся и считаем ответы
    while (p >= 0) {
        unit cur = units[p--];

        int n = cur.sz;
        if (n <= LIM) {
            simp_mult(*cur.a, *cur.b, *cur.res);
            continue;
        }

        vector<uint>* A, * B, * res, * t1, * t2, * gamma;
        A = cur.a, B = cur.b, res = cur.res, t1 = cur.t1, t2 = cur.t2, gamma = cur.gamma;

        vector<uint> t3;
        simp_subs(*gamma, *t1, t3);
        simp_subs(t3, *t2, t3);

        cnt(*res, *t1, *t2, t3, n);

    }
}

void read_vec(vector<uint>& a, string& s) {
    int num = 0;
    for (char x : s) {
        if (x == ' ') {
            a.push_back(num);
            num = 0;
            continue;
        }

        num = num * 10 + x - '0';
    }
    a.push_back(num);
}


int main()
{
    fast;
    string s;
    getline(cin, s);

    int fin_n = 0;

    vector<uint> res;
    read_vec(res, s);
    fin_n += res.size() - 1;

    while (getline(cin, s)) {
        vector<uint> b;
        read_vec(b, s);
        fin_n += b.size() - 1;

        format(res, b);
        karatsuba(res, b, res);
    }

    for (int i = 0; i <= fin_n; i++)
        cout << res[i] << ' ';
}