Karatsuba arrays + debug

#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#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");

typedef unsigned int digit;
const int LIM = 32;

struct poly {
    digit* val;
    int len;

    digit operator[](int pos) {
        if (pos >= len)
            return 0;
        return val[pos];
    }
};

poly sum(poly a, poly b) {
    poly s;
    if (a.len < b.len)
        swap(a, b);

    s.len = a.len;
    s.val = new digit[s.len];

    for (int i = 0; i < a.len; i++)
        s.val[i] = a[i] + b[i];

    return s;
}

poly& sub(poly& a, poly b) {
    for (int i = 0; i < a.len; i++)
        a.val[i] -= b[i];
    return a;
}

void print(poly& a) {
    for (int i = 0; i < a.len; i++)
        cout << a[i] << ' ';
    cout << "  len: " << a.len;
    cout << '\n';
}

bool DEBUG = 0;

poly karatsuba(poly a, poly b) {
    poly res;
    int n = a.len;

    res.len = 2 * n - 1;
    res.val = new digit[res.len];

    if (a.len <= LIM) {
        memset(res.val, 0, sizeof(digit) * res.len);

        if (DEBUG) {
            cout << "Naive multiplication\n";
            cout << "First: ";
            print(a);
            cout << "Second: ";
            print(b);
        }

        for (int i = 0; i < a.len; i++)
            for (int j = 0; j < b.len; j++) {
                res.val[i + j] += a[i] * b[j];
                if (DEBUG) {
                    cout << "res: ";
                    print(res);
                }
            }
        return res;
    }

    poly a_part1;
    a_part1.val = a.val;
    a_part1.len = n / 2;
    if (DEBUG) {
        cout << "a_part1: ";
        print(a_part1);
    }

    poly a_part2;
    a_part2.val = a.val + a_part1.len;
    a_part2.len = n - a_part1.len;
    if (DEBUG) {
        cout << "a_part2: ";
        print(a_part2);
    }

    poly b_part1;
    b_part1.val = b.val;
    b_part1.len = n / 2;
    if (DEBUG) {
        cout << "b_part1: ";
        print(b_part1);
    }

    poly b_part2;
    b_part2.val = b.val + b_part1.len;
    b_part2.len = n - b_part1.len;
    if (DEBUG) {
        cout << "b_part2: ";
        print(b_part2);
    }

    poly sum_of_a_parts = sum(a_part1, a_part2);
    if (DEBUG) {
        cout << "sum_of_a_parts: ";
        print(sum_of_a_parts);
    }
    poly sum_of_b_parts = sum(b_part1, b_part2);
    if (DEBUG) {
        cout << "sum_of_b_parts: ";
        print(sum_of_b_parts);
    }

    poly product_of_sums_of_parts = karatsuba(sum_of_a_parts, sum_of_b_parts);
    if (DEBUG) {
        cout << "product_of_sums_of_parts: ";
        print(product_of_sums_of_parts);
    }

    poly product_of_first_parts = karatsuba(a_part1, b_part1);
    if (DEBUG) {
        cout << "product_of_first_parts: ";
        print(product_of_first_parts);
    }

    poly product_of_second_parts = karatsuba(a_part2, b_part2);
    if (DEBUG) {
        cout << "product_of_second_parts: ";
        print(product_of_second_parts);
    }

    poly sum_of_middle_terms = sub(sub(product_of_sums_of_parts, product_of_first_parts), product_of_second_parts);
    if (DEBUG) {
        cout << "sum_of_middle_terms: ";
        print(sum_of_middle_terms);
    }

    memset(res.val, 0, res.len * sizeof(digit));

    memcpy(res.val, product_of_first_parts.val, product_of_first_parts.len * sizeof(digit));
    if (DEBUG) {
        cout << "res: ";
        print(res);
    }
    memcpy(res.val + 2 * (n/2), product_of_second_parts.val, product_of_second_parts.len * sizeof(digit));
    if (DEBUG) {
        cout << "res: ";
        print(res);
    }

    for (int i = 0; i < sum_of_middle_terms.len; i++)
        res.val[a_part1.len + i] += sum_of_middle_terms[i];

    //
    //зачистка
    //

    delete[] sum_of_a_parts.val;
    delete[] sum_of_b_parts.val;
    delete[] product_of_sums_of_parts.val;
    delete[] product_of_first_parts.val;
    delete[] product_of_second_parts.val;

    return res;
}

poly read_poly(string& s) {
    vector<digit> nums;

    digit num = 0;
    for (char x : s) {
        if (x == ' ') {
            nums.push_back(num);
            num = 0;
        }
        else
            num = num * 10 + x - '0';
    }
    nums.push_back(num);

    poly cur;
    cur.val = new digit[nums.size()];
    cur.len = nums.size();
    for (int i = 0; i < cur.len; i++)
        cur.val[i] = nums[i];

    return cur;
}

void format(poly &a, poly &b) {
    poly s;
    if (a.len < b.len)
        swap(a, b);

    s.val = new digit[a.len];
    s.len = a.len;
    memset(s.val, 0, s.len * sizeof(digit));
    //print(s);
    memcpy(s.val, b.val, b.len * sizeof(digit));
    //print(s);
    b = s;
}

int main()
{
    fast;
    unsigned int start_time = clock();
    string s;
    int fin_n = 0;
    getline(cin, s);
    poly res = read_poly(s);
    fin_n += res.len - 1;

    while (getline(cin, s)) {
        poly b = read_poly(s);
        fin_n += b.len - 1;
        format(res, b);

        //cout << "first: ";
        //print(res);
        //cout << "second: ";
        //print(b);

        res = karatsuba(res, b);
        //cout << "result: ";
        //print(res);
        //cout << '\n';
    }

    //for (int i = 0; i <= fin_n; i++)
        //cout << res[i] << ' ';
    unsigned int end_time = clock();
    cout << (end_time - start_time) / 1000.0;
}