Submission #15040

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
15040	2015-07-11T06:26:09 Z	cki86201	씽크스몰 (kriii3_TT)	C++	20 / 30	2909 ms	34444 KB

tt

#include<stdio.h>
#include<vector>
#include<math.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<double,double> Pd;

const double PI = 3.141592653589793238;

inline Pd mul(Pd A,Pd B){return Pd(A.X * B.X - A.Y * B.Y, A.X * B.Y + A.Y * B.X);}
inline Pd OMG(double x){return Pd(cos(2*PI/x), sin(2*PI/x));}
inline Pd pls(Pd A,Pd B,int t){return Pd(A.X + t*B.X, A.Y + t*B.Y);}

typedef vector<Pd> vb;

void DFT(vb &F,int L,int t)
{
	if(L==1)return;
	vb A(L/2),B(L/2);
	int i;
	for(i=0;i<L;i++){
		if(i&1)B[i>>1] = F[i];
		else A[i>>1] = F[i];
	}
	DFT(A,L/2,t);
	DFT(B,L/2,t);
	Pd now = Pd(1,0);
	for(i=0;i<L/2;i++){
		F[i] = pls(A[i], mul(now,B[i]), 1);
		F[L/2+i] = pls(A[i], mul(now,B[i]), -1);
		now = OMG((double)L/(i+1)*t);
	}
}
ll change(double x){return x>0?(ll)(x+0.1):(ll)(x-0.1);}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	int i;
	for(i=0;max(n,m)>=1<<i;i++);
	int expo = 1<<(i+1);
	vb A(expo), B(expo);
	for(i=n;i>=0;i--)scanf("%lf",&A[i].X);
	for(i=m;i>=0;i--)scanf("%lf",&B[i].X);
	DFT(A,expo,1), DFT(B,expo,1);
	for(i=0;i<expo;i++)A[i] = mul(A[i],B[i]);
	DFT(A,expo,-1);
	for(i=0;i<expo;i++)A[i].X /= expo;
	int lim = expo-1;
	while(lim){
		if(fabs(A[lim].X) > 1e-1)break;
		lim--;
	}
	ll ans = 0;
	for(i=lim;i>=0;i--)ans ^= change(A[i].X);
	printf("%lld",ans);
	return 0;
}

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	1676 KB	Output is correct
2	Correct	0 ms	1676 KB	Output is correct
3	Correct	1 ms	1676 KB	Output is correct
4	Correct	9 ms	1676 KB	Output is correct
5	Correct	9 ms	1676 KB	Output is correct
6	Correct	9 ms	1676 KB	Output is correct
7	Correct	9 ms	1676 KB	Output is correct
8	Correct	9 ms	1676 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	165 ms	3692 KB	Output is correct
2	Correct	1390 ms	18052 KB	Output is correct
3	Correct	1385 ms	18052 KB	Output is correct
4	Correct	1406 ms	18052 KB	Output is correct
5	Correct	1408 ms	18052 KB	Output is correct
6	Correct	1406 ms	18052 KB	Output is correct
7	Correct	1418 ms	18052 KB	Output is correct
8	Correct	1421 ms	18052 KB	Output is correct

Subtask #3

0.0 / 10.0

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