結果

問題 No.387 ハンコ
コンテスト
ユーザー anta
提出日時 2016-06-23 21:42:32
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2,552 ms / 5,000 ms
コード長 2,804 bytes
コンパイル時間 1,934 ms
コンパイル使用メモリ 181,144 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2024-10-11 18:52:00
合計ジャッジ時間 14,859 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
static const int INF = 0x3f3f3f3f; static const long long INFL = 0x3f3f3f3f3f3f3f3fLL;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> static void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> static void amax(T &x, U y) { if(x < y) x = y; }

template<typename Op>
void shiftOp(uint64_t *x, const uint64_t *y, int N, int shift, Op op) {
	if(N <= 0) return;
	x += shift / 64;
	shift %= 64;
	if(shift == 0) {
		for(int i = 0; i < N; ++ i)
			x[i] = op(x[i], y[i]);
	} else {
		x[0] = op(x[0], y[0] << shift);
		for(int i = 0; i < N - 1; ++ i)
			x[i + 1] = op(x[i + 1], op(y[i + 1] << shift, y[i] >> (64 - shift)));
		x[N] = op(x[N], y[N - 1] >> (64 - shift));
	}
}
void shiftOr(uint64_t *x, const uint64_t *y, int N, int shift) {
	shiftOp(x, y, N, shift, bit_or<uint64_t>());
}
void shiftXor(uint64_t *x, const uint64_t *y, int N, int shift) {
	shiftOp(x, y, N, shift, bit_xor<uint64_t>());
}
template<int LogH>
void verticalAddition(array<uint64_t, LogH> &x, uint64_t y) {
	uint64_t c = y;
	for(int i = 0; i < LogH - 1; ++ i) {
		uint64_t t = x[i] & c;
		x[i] ^= c;
		c = t;
	}
	x[LogH - 1] ^= c;
}
int main() {
	int N;
	while(~scanf("%d", &N)) {
		vector<int> a(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &a[i]);
		vector<int> b(N);
		for(int i = 0; i < N; ++ i)
			scanf("%d", &b[i]);
		const int H = 64, LogH = 6;
		const int X = (N - 1) / 64 + 1;
		vector<uint64_t> B(X * 2 + 2);
		rep(i, N) if(b[i] == 1)
			B[i / 64] |= 1ULL << (i % 64);
		vector<int> values = a;
		sort(values.begin(), values.end());
		values.erase(unique(values.begin(), values.end()), values.end());
		int V = (int)values.size();
		vector<vi> shifts(V);
		rep(i, N) {
			int k = (int)(lower_bound(values.begin(), values.end(), a[i]) - values.begin());
			shifts[k].push_back(i);
		}
		vector<uint64_t> row(X * 2 + 2);
		vector<array<uint64_t, LogH>> sums(X * 2 + 2);
		vector<int> ans(X * 2 * 64, 0);
		for(int i = 0; i < V; ) {
			memset(sums.data(), 0, sizeof(uint64_t) * LogH * (X * 2));
			for(int y = 0; y < H && i < V; ++ y, ++ i) {
				memset(row.data(), 0, sizeof(uint64_t) * (X * 2));
				for(int shift : shifts[i])
					shiftOr(row.data(), B.data(), X, shift);
				rep(j, X * 2)
					verticalAddition<LogH>(sums[j], row[j]);
			}
			rep(j, X * 2) {
				rep(k, LogH) {
					uint64_t t = sums[j][k];
					rep(x, 64) {
						ans[j * 64 + x] += (int)((t & 1) << k);
						t >>= 1;
					}
				}
			}
		}
		rep(i, N * 2 - 1)
			puts(ans[i] % 2 ? "ODD" : "EVEN");
	}
	return 0;
}
0