oj.uz

Submission #1086432

# Submission time Handle Problem Language Result Execution time Memory
1086432 2024-09-10T15:34:30 Z shikgom2 씽크스몰 (kriii3_TT) C++17
20 / 30
 74 ms 48076 KB 
#include <bits/stdc++.h>
using namespace std;

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

using complex_t = complex<double>;

void fft(vector<complex_t>& a) {
    int n = sz(a), L = 31 - __builtin_clz(n);
    static vector<complex<long double>> R(2, 1);
    static vector<complex_t> rt(2, 1);  // (^ 10% faster if double)
    for (static int k = 2; k < n; k *= 2) {
        R.resize(n); rt.resize(n);
        auto x = polar(1.0L, acos(-1.0L) / k);
        for (int i = k; i < k + k; i++) 
            rt[i] = R[i] = i & 1 ? R[i / 2] * x : R[i / 2];
    }
    vector<int> rev(n);
    for (int i = 0; i < n; i++) 
        rev[i] = (rev[i / 2] | (i & 1) << L) / 2;
    for (int i = 0; i < n; i++) 
        if (i < rev[i]) swap(a[i], a[rev[i]]);
    for (int k = 1; k < n; k *= 2) {
        for (int i = 0; i < n; i += 2 * k) 
            for (int j = 0; j < k; j++) {
                auto x = (double*)&rt[j + k], y = (double*)&a[i + j + k];           /// exclude-line
                complex_t z(x[0] * y[0] - x[1] * y[1], x[0] * y[1] + x[1] * y[0]);  /// exclude-line
                a[i + j + k] = a[i + j] - z;
                a[i + j] += z;
            }
    }
}

template <typename T>
vector<T> multiply(const vector<T>& a, const vector<T>& b) {
    if (a.empty() || b.empty()) return {};
    vector<T> res(sz(a) + sz(b) - 1);
    int L = 32 - __builtin_clz(sz(res)), n = 1 << L;
    vector<complex_t> in(n), out(n);
    copy(all(a), begin(in));
    for (int i = 0; i < sz(b); i++) 
        in[i].imag(b[i]);
    fft(in);
    for (complex_t& x : in) 
        x *= x;
    for (int i = 0; i < n; i++) 
        out[i] = in[-i & (n - 1)] - conj(in[i]);
    fft(out);
    for (int i = 0; i < sz(res); i++) {
        res[i] = static_cast<T>(imag(out[i]) / (4 * n) + (is_integral_v<T> ? (imag(out[i]) > 0 ? 0.5 : -0.5) : 0));
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1), b(m + 1);
    for (int i = 0; i <= n; i++) cin >> a[i];
    for (int i = 0; i <= m; i++) cin >> b[i];

    auto res = multiply(a, b);
    long long ans = 0;
    for (auto v : res) ans ^= v;
    cout << ans;

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 460 KB Output is correct
6 Correct 1 ms 600 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3420 KB Output is correct
2 Correct 18 ms 12456 KB Output is correct
3 Correct 20 ms 12380 KB Output is correct
4 Correct 35 ms 23640 KB Output is correct
5 Correct 36 ms 23892 KB Output is correct
6 Correct 38 ms 23764 KB Output is correct
7 Correct 37 ms 24132 KB Output is correct
8 Correct 37 ms 24148 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 48076 KB Output isn't correct
2 Halted 0 ms 0 KB -