#746551 (C++17(clang)) No.1881 Everything is the same...

• 問題: No.1881 Everything is the same...
• ユーザー: 👑 cologne
• 提出日時: 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,577 ms
• コンパイル使用メモリ: 129,980 KB
• 実行使用メモリ: 5,376 KB
• 最終ジャッジ日時: 2024-04-10 12:59:56
• 合計ジャッジ時間: 3,482 ms
• ジャッジサーバーID （参考情報）: judge4 / judge1

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	3 ms; 5,248 KB
testcase_01	AC	3 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	AC	3 ms; 5,376 KB
testcase_07	AC	2 ms; 5,376 KB
testcase_08	AC	2 ms; 5,376 KB
testcase_09	AC	3 ms; 5,376 KB
testcase_10	AC	18 ms; 5,376 KB
testcase_11	AC	9 ms; 5,376 KB
testcase_12	AC	18 ms; 5,376 KB
testcase_13	AC	18 ms; 5,376 KB
testcase_14	AC	18 ms; 5,376 KB
testcase_15	AC	18 ms; 5,376 KB
testcase_16	AC	18 ms; 5,376 KB
testcase_17	AC	18 ms; 5,376 KB
testcase_18	AC	18 ms; 5,376 KB
testcase_19	AC	18 ms; 5,376 KB
testcase_20	AC	18 ms; 5,376 KB
testcase_21	AC	17 ms; 5,376 KB
testcase_22	AC	16 ms; 5,376 KB
testcase_23	AC	19 ms; 5,376 KB
testcase_24	AC	17 ms; 5,376 KB
testcase_25	AC	17 ms; 5,376 KB
testcase_26	AC	17 ms; 5,376 KB
testcase_27	AC	19 ms; 5,376 KB
testcase_28	AC	17 ms; 5,376 KB
testcase_29	AC	18 ms; 5,376 KB
testcase_30	AC	17 ms; 5,376 KB
testcase_31	AC	18 ms; 5,376 KB
testcase_32	AC	18 ms; 5,376 KB
testcase_33	AC	17 ms; 5,376 KB
testcase_34	AC	17 ms; 5,376 KB
testcase_35	AC	18 ms; 5,376 KB
testcase_36	AC	18 ms; 5,376 KB
testcase_37	AC	18 ms; 5,376 KB
testcase_38	AC	17 ms; 5,376 KB
testcase_39	AC	17 ms; 5,376 KB
testcase_40	AC	18 ms; 5,376 KB
testcase_41	AC	18 ms; 5,376 KB
testcase_42	AC	3 ms; 5,376 KB
testcase_43	AC	3 ms; 5,376 KB
testcase_44	AC	3 ms; 5,376 KB
testcase_45	AC	3 ms; 5,376 KB
testcase_46	AC	3 ms; 5,376 KB
testcase_47	AC	3 ms; 5,376 KB
testcase_48	AC	2 ms; 5,376 KB
testcase_49	AC	3 ms; 5,376 KB
testcase_50	AC	2 ms; 5,376 KB
testcase_51	AC	3 ms; 5,376 KB

ソースコード

#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');
}