oj.uz

답안 #15040

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
15040 2015-07-11T06:26:09 Z cki86201 씽크스몰 (kriii3_TT) C++
20 / 30
 2909 ms 34444 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2909 ms 34444 KB Output isn't correct
2 Halted 0 ms 0 KB -