結果

問題 No.387 ハンコ
コンテスト
ユーザー anta
提出日時 2016-06-23 03:29:51
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 305 ms / 5,000 ms
コード長 3,886 bytes
コンパイル時間 2,298 ms
コンパイル使用メモリ 179,296 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-11 19:53:06
合計ジャッジ時間 5,219 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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; }

class FastInput {
	bool _end;
public:
	FastInput() : _end(false) {}

	operator void*() { return _end ? 0 : (void*)this; }

	template<typename T>
	void read_signed(T *res) {
		char c = skip();
		bool sign = false;
		if(c == '-') sign = true, c = gc();
		T x = 0;
		for(; '0' <= c && c <= '9'; c = gc())
			x = x * 10 + (c - '0');
		*res = !sign ? x : -x;
	}

	FastInput &operator()(int &res) { read_signed(&res); return *this; }

private:
	static char gc() {
#if defined(__GNUC__) && !defined(__MINGW32__)
		return (char)getchar_unlocked();
#elif defined(_MSC_VER)
		return (char)_getchar_nolock();
#else
		return (char)getchar();
#endif
	}

	static bool is_delim(char c) {
		return c == ' ' || c == '\t' || c == '\n' || c == '\r' || c == EOF;
	}

	char skip() {
		if(_end) return EOF;
		char c;
		for(c = gc(); c != -1 && is_delim(c); c = gc());
		if(c == EOF) _end = true;
		return c;
	}
} in;

class FastOutput {
public:
	void print_c_string(const char *str) {
		for(const char *p = str; *p; ++ p)
			pc(*p);
	}

	FastOutput &operator()(const char *str) { print_c_string(str); return *this; }

private:
	static void pc(char c) {
#if defined(__GNUC__) && !defined(__MINGW32__)
		putchar_unlocked(c);
#elif defined(_MSC_VER)
		_putchar_nolock(c);
#else
		putchar(c);
#endif
	}
} out;

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>());
}

unsigned xor128() {
	static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;
	unsigned t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = w ^ (w >> 19) ^ (t ^ (t >> 8));
}
inline int popcount(unsigned x) {
	x = x - ((x >> 1) & 0x55555555);
	x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
	return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
int main() {
	int N;
	while(in(N)) {
		vector<int> a(N);
		rep(i, N) in(a[i]);
		vector<int> b(N);
		rep(i, N) in(b[i]);
		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<pair<int, int>> ais(N);
		rep(i, N)
			ais[i] = make_pair(a[i], i);
		sort(ais.begin(), ais.end());
		vector<uint64_t> C(X * 2 + 2), A(X * 2 + 2);
		vector<int> shifts; shifts.reserve(N);
		for(int i = 0, j; i < N; i = j) {
			int base = ais[i].second;
			shifts.clear();
			for(j = i + 1; j < N && ais[j].first == ais[i].first; ++ j) {
				int shift = ais[j].second - base;
				shifts.push_back(shift);
			}
			int Y = shifts.empty() ? 0 : (shifts.back() - 1) / 64 + 1;
			memcpy(A.data(), B.data(), sizeof(uint64_t) * (X + Y));
			for(int shift : shifts)
				shiftOr(A.data(), B.data(), X, shift);
			shiftXor(C.data(), A.data(), X + Y, base);
		}
		rep(i, N * 2 - 1)
			out((C[i / 64] >> (i % 64) & 1) ? "ODD\n" : "EVEN\n");
	}
	return 0;
}
0