oj.uz

Submission #556449

# Submission time Handle Problem Language Result Execution time Memory
556449 2022-05-03T07:34:04 Z cloudholic 씽크스몰 (kriii3_TT) C++17
30 / 30
 3100 ms 260848 KB 
#include <complex>
#include <vector>
#include <iostream>

using namespace std;
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#define usecppio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x)((x).begin()), ((x).end())

using pii = pair < int, int >;

#define int ll
#define INF 0x7f7f7f7f7f7f7f7f

const bool debug = false;
int N, M;

/* FFT Library : Originally Written by Myungwoo *
 * https://blog.myungwoo.kr/54 *
 * Nonrecursive, Bit-Flipping Trick *
 * Several Modifications */

#define sz(v)((int)(v).size())

typedef complex<double> base;
typedef vector<int> vi;
typedef vector<base> vb;

const double PI = acos(-1);

void fft(vector < base >& a, bool inv = false)
{
    int n = (int)a.size();
    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);
    double ang = 2 * acos(-1) / n * (inv ? -1 : 1);

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

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

    if (inv)
        for (auto& i : a)
            i /= n;
}

const int LARGE = 1e6;

/* FFT polynomial Multiplication with higher precision */
void multiply(const vi& a, const vi& b, vi& res)
{
    vector < base > fa_big, fb_big;
    vector < base > fa_small, fb_small;
    int cut_val = sqrt(LARGE);
    int n = 1;

    while (n < max(sz(a), sz(b)))
        n <<= 1;

    fa_big.resize(n);
    fa_small.resize(n);
    fb_big.resize(n);
    fb_small.resize(n);

    for (int i = 0; i < sz(a); i++)
    {
        fa_big[i] = a[i] / cut_val;
        fa_small[i] = a[i] % cut_val;
    }
    for (int i = 0; i < sz(b); i++)
    {
        fb_big[i] = b[i] / cut_val;
        fb_small[i] = b[i] % cut_val;
    }

    fft(fa_big, 0), fft(fb_big, 0);
    fft(fa_small, 0), fft(fb_small, 0);

    vector<base> fa_big_2(all(fa_big));
    vector<base> fa_small_2(all(fa_small));
    for (int i = 0; i < n; i++) 
    {
        fa_big_2[i] *= fb_big[i];
        fa_big[i] *= fb_small[i];
        fa_small[i] *= fb_small[i];
        fa_small_2[i] *= fb_big[i];
    }

    fft(fa_small, 1);
    fft(fa_small_2, 1);
    fft(fa_big, 1);
    fft(fa_big_2, 1);
    res.resize(n);

    for (int i = 0; i < n; i++)
    {
        int ss = (int64_t)round(fa_small[i].real());
        int sb = (int64_t)round(fa_small_2[i].real());
        int bs = (int64_t)round(fa_big[i].real());
        int bb = (int64_t)round(fa_big_2[i].real());

        res[i] = ss;
        res[i] += (sb + bs) * cut_val;
        res[i] += bb * cut_val * cut_val;
    }
}

vector < int > f, g, res;
int32_t main()
{
    usecppio cin >> N >> M;
    f.resize(2 * (N + 1) + 5);
    g.resize(2 * (M + 1) + 5);

    for (int i = 0; i <= N; i++) 
        cin >> f[i];
    for (int i = 0; i <= M; i++) 
        cin >> g[i];
    multiply(f, g, res);

    int t = 0;
    for (int i = 0; i < res.size(); i++)    
    	t ^= res[i];
    
	cout << t << '\n';
}

Compilation message

tt.cpp: In function 'int32_t main()':
tt.cpp:147:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0; i < res.size(); i++)
      |                     ~~^~~~~~~~~~~~
tt.cpp:147:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  147 |     for (int i = 0; i < res.size(); i++)
      |     ^~~
tt.cpp:150:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  150 |  cout << t << '\n';
      |  ^~~~

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 324 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 4160 KB Output is correct
2 Correct 177 ms 28996 KB Output is correct
3 Correct 189 ms 29260 KB Output is correct
4 Correct 187 ms 30144 KB Output is correct
5 Correct 188 ms 30668 KB Output is correct
6 Correct 220 ms 30308 KB Output is correct
7 Correct 183 ms 30720 KB Output is correct
8 Correct 193 ms 30928 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 60660 KB Output is correct
2 Correct 1244 ms 119648 KB Output is correct
3 Correct 1267 ms 121976 KB Output is correct
4 Correct 2939 ms 251416 KB Output is correct
5 Correct 3100 ms 246920 KB Output is correct
6 Correct 2914 ms 255436 KB Output is correct
7 Correct 2954 ms 260848 KB Output is correct
8 Correct 3014 ms 259224 KB Output is correct