結果

問題 No.1881 Everything is the same...
ユーザー colognecologne
提出日時 2022-03-18 12:06:49
言語 C++17(clang)
(17.0.6 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 2,912 bytes
コンパイル時間 1,995 ms
コンパイル使用メモリ 131,900 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 15:02:41
合計ジャッジ時間 3,796 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 3 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 2 ms
5,248 KB
testcase_09 AC 2 ms
5,248 KB
testcase_10 AC 18 ms
5,248 KB
testcase_11 AC 8 ms
5,248 KB
testcase_12 AC 18 ms
5,248 KB
testcase_13 AC 18 ms
5,248 KB
testcase_14 AC 19 ms
5,248 KB
testcase_15 AC 17 ms
5,248 KB
testcase_16 AC 18 ms
5,248 KB
testcase_17 AC 18 ms
5,248 KB
testcase_18 AC 18 ms
5,248 KB
testcase_19 AC 18 ms
5,248 KB
testcase_20 AC 17 ms
5,248 KB
testcase_21 AC 18 ms
5,248 KB
testcase_22 AC 18 ms
5,248 KB
testcase_23 AC 18 ms
5,248 KB
testcase_24 AC 18 ms
5,248 KB
testcase_25 AC 18 ms
5,248 KB
testcase_26 AC 18 ms
5,248 KB
testcase_27 AC 18 ms
5,248 KB
testcase_28 AC 18 ms
5,248 KB
testcase_29 AC 18 ms
5,248 KB
testcase_30 AC 18 ms
5,248 KB
testcase_31 AC 17 ms
5,248 KB
testcase_32 AC 17 ms
5,248 KB
testcase_33 AC 18 ms
5,248 KB
testcase_34 AC 17 ms
5,248 KB
testcase_35 AC 18 ms
5,248 KB
testcase_36 AC 17 ms
5,248 KB
testcase_37 AC 18 ms
5,248 KB
testcase_38 AC 16 ms
5,248 KB
testcase_39 AC 17 ms
5,248 KB
testcase_40 AC 18 ms
5,248 KB
testcase_41 AC 18 ms
5,248 KB
testcase_42 AC 3 ms
5,248 KB
testcase_43 AC 3 ms
5,248 KB
testcase_44 AC 2 ms
5,248 KB
testcase_45 AC 2 ms
5,248 KB
testcase_46 AC 3 ms
5,248 KB
testcase_47 AC 2 ms
5,248 KB
testcase_48 AC 2 ms
5,248 KB
testcase_49 AC 2 ms
5,248 KB
testcase_50 AC 2 ms
5,248 KB
testcase_51 AC 3 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <algorithm>
#include <cstring>
#include <map>
#include <utility>
#include <vector>

#include <cstdio>
#include <cinttypes>
#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
char *p;
struct Input
{
	Input()
	{
		struct stat st;
		fstat(0, &st);
		p = (char *)mmap(0, st.st_size, PROT_READ, MAP_SHARED, 0, 0);
	}
} inp;

inline uint32_t readU32()
{
	int t;
	uint32_t r;
	for (r = *p++ - 48; (t = *p++ - 48) >= 0; r = r * 10 + t)
		(void)0;
	return r;
}

using namespace std;

const int MAXN = 100000;
int F[MAXN + 1];
void factor_init()
{
	for (int i = 2; i <= MAXN; i++)
		if (!F[i])
		{
			F[i] = i;
			for (long j = 1L * i * i; j <= MAXN; j += i)
				if (!F[j])
					F[j] = i;
		}
}

vector<pair<int, int>> factorize(int N)
{
	vector<pair<int, int>> ret;
	while (N != 1)
	{
		int d = F[N];
		if (ret.empty() || ret.back().first != d)
			ret.emplace_back(d, 1);
		else
			ret.back().second++;
		N /= d;
	}
	return ret;
}

vector<int> T(vector<int> A)
{
	if (A.empty())
		return {};
	vector<int> ret(*max_element(A.begin(), A.end()));
	for (int a : A)
		for (int i = 0; i < a; i++)
			ret[i]++;
	return ret;
}

vector<vector<int>> bktk(vector<int> A)
{
	int tot = 1;
	for (int a : A)
		tot *= a;
	vector<vector<int>> R;
	for (int i = 0; i < tot; ++i)
	{
		int c = i;
		vector<int> X;
		for (int a : A)
		{
			X.push_back(c % a);
			c /= a;
		}
		R.push_back(X);
	}
	return R;
}

int calc(vector<int> A)
{
	static map<vector<int>, int> memo;
	if (memo.count(A))
		return memo[A];

	vector<int> grundy;

	vector<int> cA(A.size());
	for (int i = 0; i < (int)A.size(); ++i)
		cA[i] = 1 + A[i] - (i == 0 ? 0 : A[i - 1]);
	for (auto dA : bktk(cA))
	{
		vector<int> B(A.size());
		for (int i = 0; i < (int)A.size(); ++i)
			B[i] = A[i] - dA[i];
		if (!B.empty() && B.front() == 0)
			B.erase(B.begin());
		if (B != A)
			grundy.push_back(calc(B));
	}

	sort(grundy.begin(), grundy.end());
	grundy.erase(unique(grundy.begin(), grundy.end()), grundy.end());
	for (int i = 0;; ++i)
		if (i >= (int)grundy.size() || grundy[i] != i)
			return memo[A] = i;
}

int smemo[MAXN + 1];
void solve_init()
{
	memset(smemo, -1, sizeof smemo);
}
int solve(int x)
{
	if (~smemo[x])
		return smemo[x];
	map<int, vector<int>> C;
	auto add = [&](int p, int k)
	{
		if (!C.count(p))
			C[p] = {};
		C[p].push_back(k);
	};
	for (auto [p, k] : factorize(x))
	{
		if (p == 2)
		{
			if (k >= 2)
				add(p, 1);
			if (k >= 3)
				add(p, k - 2);
		}
		else
		{
			if (k >= 2)
				add(p, k - 1);
			for (auto [q, t] : factorize(p - 1))
				add(q, t);
		}
	}
	vector<int> part;
	for (auto [p, v] : C)
	{
		auto Tv = T(v);
		part.insert(part.end(), Tv.begin(), Tv.end());
	}
	part = T(part);
	reverse(part.begin(), part.end());
	return smemo[x] = calc(part);
}

int main()
{
	factor_init();
	solve_init();
	int N = readU32();
	int G = 0;
	for (int i = 0; i < N; i++)
		G ^= solve(readU32());
	printf("%c\n", G ? 'Y' : 'X');
}
0