This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <stdio.h>
#include <vector>
#include <iostream>
int n, m, l;
int i, j;
unsigned int A[1000000], B[1000000];
std::vector<unsigned int> solve(int al, int ar, int bl, int br)
{
int n = ar-al, m = br-bl;
int l = n + m + 1;
std::vector<unsigned int> ret(l);
for (i = 0; i <= l; ++i)
ret[i] = 0;
if (n == 0 || m == 0) {
for (i = 0; i <= l; ++i) {
for (j = 0; j <= i; ++j) {
ret[i] += A[al+j] * B[bl+i-j];
}
}
return ret;
}
std::vector<unsigned int> a, b, c, d;
int amid = (al + ar) / 2;
int bmid = (bl + br) / 2;
a = solve(al, amid, bl, bmid);
b = solve(al, amid, bmid+1, br);
c = solve(amid+1, ar, bl, bmid);
d = solve(amid+1, ar, bmid+1, br);
for (i = 0; i < a.size(); ++i)
ret[i] += a[i];
for (i = 0; i < b.size(); ++i)
ret[amid+1+i] += b[i];
for (i = 0; i < c.size(); ++i)
ret[bmid+1+i] += c[i];
for (i = 0; i < d.size(); ++i)
ret[amid+bmid+2+i] += d[i];
return ret;
}
int main(int argc, char *argv[])
{
scanf("%d", &n);
scanf("%d", &m);
l = n + m + 1;
for (i = 0; i <= n; ++i)
scanf("%u", A+i);
for (i = 0; i <= m; ++i)
scanf("%u", B+i);
std::vector<unsigned int> C = solve(0, n, 0, m);
unsigned int ret = C[0];
for (i = 1; i < l; ++i) {
ret ^= C[i];
}
printf("%u\n", ret);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |