oj.uz

답안 #22843

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
22843 2017-04-30T07:50:59 Z 카시코이(#958, xdoju, ntopia, pps789) Window XOR (KRIII5_WX) C++14
0 / 7
 1000 ms 17324 KB 
#include<cstdio>
#include<vector>
#include<complex>
#include<algorithm>
using namespace std;

const int NMAX = 100001;
const double PI = atan2(1, 0) * 2;

typedef complex<double> idouble;
typedef vector<idouble> poly;
typedef vector<int> vi;

int rev(int x, int sz) {
	int i, r = 0;
	for (i = 0; i < sz; i++) {
		r = r << 1 | x & 1;
		x >>= 1;
	}
	return r;
}

void fft(poly& a, bool f = false) {
	const int N = a.size();
	int sz = 0, t = 1;
	while (t < N) sz++, t <<= 1;
	idouble x, y, z;
	double w;
	int i, j, k;
	for (i = 0; i < N; i++) {
		j = rev(i, sz);
		if (i < j) {
			z = a[i];
			a[i] = a[j];
			a[j] = z;
		}
	}
	for (i = 1; i < N; i <<= 1) {
		w = PI / i;
		if (f) w = -w;
		x = idouble(cos(w), sin(w));
		for (j = 0; j < N; j += i << 1) {
			y = idouble(1);
			for (k = 0; k < i; k++) {
				z = a[i + j + k] * y;
				a[i + j + k] = a[j + k] - z;
				a[j + k] += z;
				y *= x;
			}
		}
	}
	if (f) for (i = 0; i < N; i++) a[i] /= N;
}

vi mult(const vi& A, const vi& B) {
	int t = max(A.size(), B.size());
	int N = 1; for (; N<t; N <<= 1); N <<= 1;
	poly a(N), b(N);
	for (int i = 0; i<A.size(); i++) a[i] = A[i];
	for (int i = 0; i<B.size(); i++) b[i] = B[i];

	fft(a); fft(b);
	poly ab(N);
	for (int i = 0; i<N; i++) ab[i] = a[i] * b[i];

	fft(ab, true);
	vi tmp(N);

	for (int i = 0; i < N; i++)
		tmp[i] = ((int)(ab[i].real() + 0.5)) & 1;

	vi ret(t);
	for (int i = 0; i < N; i++) {
		int j = i; while (j >= t) j -= t;
		ret[j] ^= tmp[i];
	}
	return ret;
}
typedef long long ll;

int A[NMAX];

vi polypow(const vi& V, ll y) {
	if (y == 1) return V;
	if (y % 2) return mult(polypow(V, y - 1), V);
	vi VV = polypow(V, y >> 1);
	return mult(VV, VV);
}

int ans[NMAX];

int main() {
	int N, K; ll T;
	scanf("%d%d%lld", &N, &K, &T);
	for (int i = 0; i < N; i++) scanf("%d", A + i);

	vi base(N);
	for (int i = 0; i < K; i++) base[i] = 1;

	vi trans = polypow(base, T);

	for (int bit = 0; bit < 31; bit++) {
		vi cur(N);
		for (int i = 0; i < N; i++) cur[i] = (A[i] & (1 << bit)) ? 1 : 0;
		auto res = mult(cur, trans);
		for (int i = 0; i < N; i++) if (res[i]) ans[i] ^= (1 << bit);
	}

	for (int i = 0; i < N; i++) printf("%d ", ans[i]);
}

Compilation message

WX.cpp: In function 'int rev(int, int)':
WX.cpp:17:18: warning: suggest parentheses around arithmetic in operand of '|' [-Wparentheses]
   r = r << 1 | x & 1;
                  ^
WX.cpp: In function 'vi mult(const vi&, const vi&)':
WX.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<A.size(); i++) a[i] = A[i];
                   ^
WX.cpp:60:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i<B.size(); i++) b[i] = B[i];
                   ^
WX.cpp: In function 'int main()':
WX.cpp:94:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%lld", &N, &K, &T);
                               ^
WX.cpp:95:48: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (int i = 0; i < N; i++) scanf("%d", A + i);
                                                ^

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2760 KB Output is correct
2 Correct 0 ms 2760 KB Output is correct
3 Correct 0 ms 2760 KB Output is correct
4 Execution timed out 1000 ms 17324 KB Execution timed out
5 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1000 ms 17324 KB Execution timed out
2 Halted 0 ms 0 KB -