Submission #757482

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
757482	2023-06-13T08:52:14 Z	lsj_haru	씽크스몰 (kriii3_TT)	C++17	20 / 30	281 ms	48320 KB

tt

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cpx;
#define pi acos(-1)

int N, M;
vector<cpx> cc;
vector<cpx> aa, bb;
long long ans;

void FFT(vector<cpx> &f, cpx w)
{
    int n = f.size(); if (n==1) return;
    vector<cpx> fe(n/2), fo(n/2);
    for (int i = 0; i < n; i++) {
        if (i&1) fo[i/2] = f[i]; else fe[i/2] = f[i];
    }
    FFT(fe, w*w); FFT(fo, w*w);
    cpx now(1, 0);
    for (int i = 0; i < n/2; i++) {
        f[i] = fe[i] + now * fo[i];
        f[i+n/2] = fe[i] - now * fo[i];
        now *= w;
    }
    return;
}

vector<cpx> mul(vector<cpx> a, vector<cpx> b)
{
    int n = 1; while (n < a.size()+1 || n < b.size()+1) n *= 2; n *= 2;
    a.resize(n); b.resize(n);
    vector<cpx> c(n);
    cpx w(cos(pi*2/n), sin(pi*2/n));
    FFT(a, w);
    FFT(b, w);
    for (int i = 0; i < n; i++) c[i] = a[i]*b[i];
    FFT(c, cpx(1, 0)/w);
    for (int i = 0; i < n; i++) {
        c[i] /= cpx(n, 0);
        c[i] = cpx(round(c[i].real()), round(c[i].imag()));
    }
    return c;
}

int main()
{
    int k;
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= N+1; i++) {
        scanf("%d", &k);
        aa.push_back({k, 0});
    }
    for (int i = 1; i <= M+1; i++) {
        scanf("%d", &k);
        bb.push_back({k, 0});
    }
    cc = mul(aa, bb);
    ans = (long long)cc[0].real();
    for (int i = 1; i <= N + M; i++) {
        ans = ans ^ (long long)cc[i].real();
    }
    printf("%lld", ans);
    return 0;
}

Compilation message

tt.cpp: In function 'std::vector<std::complex<double> > mul(std::vector<std::complex<double> >, std::vector<std::complex<double> >)':
tt.cpp:30:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     int n = 1; while (n < a.size()+1 || n < b.size()+1) n *= 2; n *= 2;
      |                       ~~^~~~~~~~~~~~
tt.cpp:30:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     int n = 1; while (n < a.size()+1 || n < b.size()+1) n *= 2; n *= 2;
      |                                         ~~^~~~~~~~~~~~
tt.cpp: In function 'int main()':
tt.cpp:51:23: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   51 |         aa.push_back({k, 0});
      |                       ^
tt.cpp:55:23: warning: narrowing conversion of 'k' from 'int' to 'double' [-Wnarrowing]
   55 |         bb.push_back({k, 0});
      |                       ^
tt.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &N, &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~
tt.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~
tt.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d", &k);
      |         ~~~~~^~~~~~~~~~

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	212 KB	Output is correct
4	Correct	1 ms	468 KB	Output is correct
5	Correct	1 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	468 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	3356 KB	Output is correct
2	Correct	144 ms	22740 KB	Output is correct
3	Correct	128 ms	23080 KB	Output is correct
4	Correct	161 ms	24124 KB	Output is correct
5	Correct	149 ms	24468 KB	Output is correct
6	Correct	135 ms	24164 KB	Output is correct
7	Correct	144 ms	24548 KB	Output is correct
8	Correct	148 ms	24824 KB	Output is correct

Subtask #3

0 / 10.0

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