제출 #433223

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
433223		hhhhaura	XOR Sum (info1cup17_xorsum)	C++14	0 / 100	170 ms	131076 KiB

xorsum

#define wiwihorz
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma loop-opt(on)

#define rep(i, a, b) for(int i = a; i <= b; i ++)
#define rrep(i, a, b) for(int i = b; i >= a; i--)
#define all(x) x.begin(), x.end()
#define ceil(a, b) ((a + b - 1) / (b))

#define INF 1000000000000000000
#define MOD 1000000007
#define eps (1e-9)

using namespace std;

#define int long long int
#define lld double
#define pii pair<int, int>
#define random mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count())

#ifdef wiwihorz
#define print(a...) kout("[" + string(#a) + "] = ", a) 
void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
void kout() { cerr << endl; }
template<class T1, class ... T2> void kout(T1 a, T2 ... e) { cerr << a << " ", kout(e...); }
#else
#define print(...) 0
#define vprint(...) 0
#endif
namespace FFT {
	typedef vector<complex<lld>> poly;
	typedef complex<lld> cd;
	const lld PI = acos(-1);
	const cd I = {0, 1};
	int lg; poly A, B;
	vector<int> rev;
	vector<poly> a;
	void init_(vector<int> _a, vector<int> _b) {
		lg = 32 - __builtin_clz(_a.size() +_b.size());
		print(lg);
		A.assign(1 << lg, {0, 0});
		B.assign(1 << lg, {0, 0});
		a.assign(1 << lg, poly());
		rep(i, 0, signed(_a.size()) - 1) A[i] = _a[i];
		rep(i, 0, signed(_b.size()) - 1) B[i] = _b[i];
		rev.assign(1 << lg, 0);
		rep(i, 0, (1 << lg) - 1) {
			rep(j, 0, lg - 1) {
				rev[i] <<= 1;
				rev[i] |= ((i >> j) & 1);
			}
		}		
	}
	poly fft(poly p, bool inv) {
		rep(i, 0, (1 << lg) - 1) a[i].assign(1, p[i]);
		rep(s, 1, lg) {
			int len = 1 << (s - 1);
			cd w = {1, 0};
			cd it_w = exp(2 * PI * I / (lld)(2 * len));
			if(inv) it_w = cd(1) / it_w;
			for(int i = 0; i < (1 << lg); i += 2 * len) a[rev[i]].resize(2 * len);
			rep(j, 0, len - 1) {
				for(int i = 0; i < (1 << lg); i += 2 * len) {
					int x = rev[i], y = rev[i + len];
					cd t = a[y][j] * w;
					a[x][j + len] = a[x][j] - t;
					a[x][j] = a[x][j] + t;
				}
				w = w * it_w;
			}	
			for(int i = len; i < (1 << lg); i += 2 * len) a[rev[i]].clear();
		}
		if(inv) for(auto &i : a[0]) i /= cd(1 << lg);
		return a[0];
	}
	vector<int> solve() {
		poly ans = poly(1 << lg, {0, 0});
		A = fft(A, 0);
		B = fft(B, 0);
		rep(i, 0, (1 << lg) - 1) ans[i] = A[i] * B[i];
		ans = fft(ans, 1);
		vector<int> ans_int;
		rep(i, 0, (1 << lg)- 1) 
			ans_int.push_back(round(abs(ans[i])));
		return ans_int;
	}
};
namespace solver {
	int n, mx = 1000000;
	vector<int> cnt;
	void init_() {cnt.assign(mx + 1, 0);}
	int solve() {
		int ans = 0;
		rep(i, 0, mx) if(cnt[i] & 1) ans ^= 2 * i;
		FFT::init_(cnt, cnt);
		vector<int> cnt1 = FFT::solve();
		rep(i, 0, mx) cnt1[2 * i] -= (cnt[i] * cnt[i] / 2);
		rep(i, 1, cnt1.size() - 1) {
			cnt1[i] /= 2;
			if(cnt1[i] & 1) ans ^= i;
		}
		return ans;
	}

};
using namespace solver;
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int n; cin >> n;
	init_();
	rep(i, 1, n) {
		int x; cin >> x;
		cnt[x] ++;
	}	
	cout << solve() << "\n";
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp:4: warning: ignoring '#pragma loop ' [-Wunknown-pragmas]
    4 | #pragma loop-opt(on)
      | 
xorsum.cpp:24:13: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |             ^~~~
xorsum.cpp:24:21: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   24 | void vprint(auto L, auto R) { while(L < R) cerr << *L << " \n"[next(L) == R], ++L;}
      |                     ^~~~
xorsum.cpp: In function 'long long int solver::solve()':
xorsum.cpp:6:39: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, a, b) for(int i = a; i <= b; i ++)
......
   99 |   rep(i, 1, cnt1.size() - 1) {
      |       ~~~~~~~~~~~~~~~~~~~~~            
xorsum.cpp:99:3: note: in expansion of macro 'rep'
   99 |   rep(i, 1, cnt1.size() - 1) {
      |   ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23