Submission #22626

#	Time	Username	Problem	Language	Result	Execution time	Memory
22626		카시코이 (#40)	Window Xor (KRIII5_WX)	C++14	0 / 7	1000 ms	16932 KiB

WX

#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 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);
	vector<int> g; for (int i = 0; i < N; i++) if (trans[i]) g.push_back(i);

	for (int i = 0; i < N; i++) {
		int cur = 0;
		for (int d : g) cur ^= A[(i + d) % N];
		printf("%d ", cur);
	}

}

Compilation message (stderr)

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:92: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:93: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
• Subtask 2: 0 / 5