oj.uz

Submission #556471

# Submission time Handle Problem Language Result Execution time Memory
556471 2022-05-03T08:25:59 Z cloudholic 씽크스몰 (kriii3_TT) C++17
30 / 30
 2569 ms 222412 KB 
#define _USE_MATH_DEFINES

#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <stack>
#include <vector>

using namespace std;

#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define int64 long long

typedef complex<double> base;

void fft(vector <base>& a, const bool invert)
{
    const int n = sz(a);
    for (int i = 1, j = 0; i < n; i++)
    {
        int bit = n >> 1;
        for (; j >= bit; bit >>= 1)
            j -= bit;
        j += bit;

        if (i < j)
            swap(a[i], a[j]);
    }

    vector<base> root(n / 2);
    const double angle = 2 * acos(-1) / n * (invert ? -1 : 1);

    for (int i = 0; i < n / 2; i++)
        root[i] = base(cos(angle * i), sin(angle * i));

    for (int len = 2; len <= n; len <<= 1)
    {
	    const int step = n / len;

        for (int i = 0; i < n; i += len)
        {
            for (int j = 0; j < len / 2; j++)
            {
                base u = a[i + j];
                base v = a[i + j + len / 2] * root[step * j];

                a[i + j] = u + v;
                a[i + j + len / 2] = u - v;
            }
        }
    }

    if (invert)
        for (int i = 0; i < n; i++)
            a[i] /= n;
}

void multiply(const vector<int>& a, const vector<int>& b, vector<int64>& res)
{
    constexpr int cut = 1e3;

    vector<base> lower_a, upper_a;
    vector<base> lower_b, upper_b;

    int n = 1;
    while (n < sz(a) + sz(b) - 1)
        n <<= 1;

    lower_a.resize(n);
    upper_a.resize(n);
    lower_b.resize(n);
    upper_b.resize(n);

    for (int i = 0; i < sz(a); i++)
    {
        lower_a[i] = a[i] % cut;
        upper_a[i] = a[i] / cut;
    }
    for (int i = 0; i < sz(b); i++)
    {
        lower_b[i] = b[i] % cut;
        upper_b[i] = b[i] / cut;
    }

    fft(lower_a, false);
	fft(upper_a, false);
    fft(lower_b, false);
	fft(upper_b, false);

    vector<base> lower_a2(all(lower_a));
    vector<base> upper_a2(all(upper_a));

    for (int i = 0; i < n; i++)
    {
        lower_a[i] *= lower_b[i];
        lower_a2[i] *= upper_b[i];
        upper_a[i] *= lower_b[i];
        upper_a2[i] *= upper_b[i];
    }

    fft(lower_a, true);
    fft(lower_a2, true);
    fft(upper_a, true);
    fft(upper_a2, true);

    res.resize(n);

    for (int i = 0; i < n; i++)
    {
	    const int64 res_ll = static_cast<int64>(lower_a[i].real() + (lower_a[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_lu = static_cast<int64>(lower_a2[i].real() + (lower_a2[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_ul = static_cast<int64>(upper_a[i].real() + (upper_a[i].real() > 0 ? 0.5 : -0.5));
	    const int64 res_uu = static_cast<int64>(upper_a2[i].real() + (upper_a2[i].real() > 0 ? 0.5 : -0.5));

        res[i] = res_uu * cut * cut + (res_lu + res_ul) * cut + res_ll;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> f, g;
	vector<int64> res;

    f.resize(n + 1);
    g.resize(m + 1);

    for (int i = 0; i <= n; i++)
        cin >> f[i];
    for (int i = 0; i <= m; i++)
        cin >> g[i];

    multiply(f, g, res);

    int64 result = 0;
    for (const auto& i : res)
        result ^= i;

    cout << result << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3664 KB Output is correct
2 Correct 89 ms 14188 KB Output is correct
3 Correct 75 ms 14260 KB Output is correct
4 Correct 160 ms 27824 KB Output is correct
5 Correct 129 ms 27992 KB Output is correct
6 Correct 158 ms 27844 KB Output is correct
7 Correct 129 ms 28016 KB Output is correct
8 Correct 135 ms 28000 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 54908 KB Output is correct
2 Correct 1039 ms 110164 KB Output is correct
3 Correct 1044 ms 110416 KB Output is correct
4 Correct 2437 ms 221072 KB Output is correct
5 Correct 2307 ms 220416 KB Output is correct
6 Correct 2569 ms 221800 KB Output is correct
7 Correct 2508 ms 222412 KB Output is correct
8 Correct 2546 ms 222376 KB Output is correct