oj.uz

Submission #15061

# Submission time Handle Problem Language Result Execution time Memory
15061 2015-07-11T08:00:16 Z myungwoo 씽크스몰 (kriii3_TT) C++14
10 / 30
 1150 ms 52740 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
typedef complex<long double> base;
typedef long long lld;

const double PI = atan2(0, -1);

void fft(vector <base> &a, bool invert)
{
	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]);
	}
	for (int len=2;len<=n;len<<=1){
		double ang = 2*PI/len*(invert?-1:1);
		base wlen(cos(ang), sin(ang));
		for (int i=0;i<n;i+=len){
			base w(1);
			for (int j=0;j<len/2;j++){
				base u = a[i+j], v = a[i+j+len/2]*w;
				a[i+j] = u+v;
				a[i+j+len/2] = u-v;
				w *= wlen;
			}
		}
	}
	if (invert){
		for (int i=0;i<n;i++) a[i] /= n;
	}
}

void multiply(const vector<lld> &a, const vector<lld> &b, vector <lld> &res)
{
	vector <base> fa(all(a)), fb(all(b));
	int n = 1;
	while (n < max(sz(a), sz(b))) n <<= 1;
	fa.resize(n); fb.resize(n);
	fft(fa, false); fft(fb, false);
	for (int i=0;i<n;i++) fa[i] *= fb[i];
	fft(fa, true);
	res.resize(n);
	for (int i=0;i<n;i++) res[i] = lld(fa[i].real() + (fa[i].real() > 0 ? 0.5 : -0.5));
}

void my_fft(const vector<lld> &a, const vector<lld> &b, vector <lld> &res)
{
	int n = max(sz(a), sz(b));
	vector <lld> fa, fb;
	for (int i=0;i<n;i++) fa.pb(0), fb.pb(0);
	for (int t: a) fa.pb(t);
	for (int t: b) fb.pb(t);
	for (int i=0;i<n-sz(a);i++) fa.pb(0);
	for (int i=0;i<n-sz(b);i++) fb.pb(0);
	for (int i=0;i<n;i++) fa.pb(0), fb.pb(0);
	vector <lld> tmp;
	multiply(fa, fb, tmp);
	res.clear();
	for (int i=0;i<n+n-1;i++) res.pb(tmp[i+n+n]);
}

int N, M;

int main()
{
	scanf("%d%d", &N, &M);
	vector <lld> a, b;
	for (int i=0;i<=N;i++){
		int x; scanf("%d", &x); a.pb(x);
	}
	for (int i=0;i<=M;i++){
		int x; scanf("%d", &x); b.pb(x);
	}
	vector <lld> val;
	my_fft(a, b, val);
	lld ans = 0;
	for (int i=0;i<=N+M;i++) ans ^= val[i];
	printf("%lld\n", ans);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1824 KB Output is correct
2 Correct 0 ms 1824 KB Output is correct
3 Correct 0 ms 1824 KB Output is correct
4 Correct 3 ms 2204 KB Output is correct
5 Correct 7 ms 2388 KB Output is correct
6 Correct 3 ms 2368 KB Output is correct
7 Correct 6 ms 2400 KB Output is correct
8 Correct 7 ms 2400 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 9036 KB Output is correct
2 Correct 1150 ms 52740 KB Output is correct
3 Incorrect 555 ms 48508 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -