#1198848 (C++23) No.3798 algo to goal

• 問題: No.3798 algo to goal
• ユーザー: 👑 qand
• 提出日時: 2026-11-13 22:44:24
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 46 ms / 2,000 ms
• コード長: 8,028 bytes
• コンパイル時間: 4,891 ms
• コンパイル使用メモリ: 393,100 KB
• 実行使用メモリ: 9,816 KB
• 最終ジャッジ日時: 2026-11-13 22:44:41
• 合計ジャッジ時間: 8,888 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge1_0

ファイルパターン	結果
sample	AC * 1
other	AC * 40

ソースコード

#line 1 "a.cpp"
// https://qandori.github.io/cp-library/
#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using std::cin, std::cout, std::cerr;
#define vec vector
typedef long double ld;
#if LONG_MAX == 2147483647L
#undef long
#define long long long
#endif
#define uint unsigned int
#define ulong unsigned long
#define overload3(a, b, c, name, ...) name
#define rep3(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(i, n) rep3(i, 0, n)
#define rep1(n) rep2(__i__, n)
#define rep(...) overload3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per3(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define per2(i, n) per3(i, 0, n)
#define per1(n) per2(__i__, n)
#define per(...) overload3(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define CP_ALL_SELECT(first, ...) first
#define CP_ALL_RANGE(a) std::begin(a), std::end(a)
#define all(...) CP_ALL_SELECT(__VA_OPT__(CP_ALL_RANGE, ) all)(__VA_ARGS__)
#define UNIQUE(a) sort(all(a)), a.erase(unique(all(a)), a.end()), a.shrink_to_fit()
#define sz(a) static_cast<int>(a.size())
#ifndef DEBUG
#define cerr \
	if (false) cerr
#undef endl
#define endl '\n'
#endif
inline auto operator^=(vector<bool>::reference a, bool b) noexcept {
	if (b) a.flip();
	return a;
}
inline auto operator&=(vector<bool>::reference a, bool b) noexcept {
	if (!b) a = false;
	return a;
}
inline auto operator|=(vector<bool>::reference a, bool b) noexcept {
	if (b) a = true;
	return a;
}
inline ostream &operator<<(ostream &os, __int128_t value) {
	ostream::sentry s(os);
	if (s) {
		__uint128_t tmp = value;
		if (value < 0) tmp = -tmp;
		char buffer[128];
		char *d = std::end(buffer);
		do {
			--d;
			*d = "0123456789"[tmp % 10];
			tmp /= 10;
		} while (tmp != 0);
		if (value < 0) --d, *d = '-';
		const int len = std::end(buffer) - d;
		if (os.rdbuf()->sputn(d, len) != len) os.setstate(std::ios_base::badbit);
	}
	return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> a) {
	return os << a.first << ' ' << a.second;
};
template <typename T>
ostream &operator<<(ostream &os, vector<T> a) {
	const int n = a.size();
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T, typename S>
istream &operator>>(istream &is, pair<T, S> &a) {
	return is >> a.first >> a.second;
}
template <typename T, size_t n>
ostream &operator<<(ostream &os, array<T, n> a) {
	rep(i, n) {
		os << a[i];
		if (i + 1 != n) os << " ";
	}
	return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &a) {
	for (T &i : a) is >> i;
	return is;
}
template <typename T, typename S>
bool chmin(T &x, S y) {
	if ((T)y < x) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T, typename S>
bool chmax(T &x, S y) {
	if (x < (T)y) {
		x = (T)y;
		return true;
	}
	return false;
}
template <typename T>
void operator++(vector<T> &a) {
	for (T &i : a) ++i;
}
template <typename T>
void operator--(vector<T> &a) {
	for (T &i : a) --i;
}
template <typename T>
void operator++(vector<T> &a, int) {
	for (T &i : a) i++;
}
template <typename T>
void operator--(vector<T> &a, int) {
	for (T &i : a) i--;
}
void init(), solve();
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);
	cerr << fixed << setprecision(20);
	init();
	int t = 1;
	cin >> t;
	while (t--) solve();
}
// #define COMB_MAX 1e6
// #include "lib/math/comb.hpp"
// #include "lib/fps/fps.hpp"
// #include "lib/math/mint.hpp"
void init() {}
void solve_() {
	int n;
	cin >> n;
	set<vec<int>> s;
	queue<vec<int>> q;
	{
		vec<int> a(n);
		iota(all(a), 0);
		s.insert(a);
		q.push(a);
	}
	while (!q.empty()) {
		auto a = q.front();
		q.pop();
		rep(i, n - 3) {
			auto b = a;
			swap(b[i], b[i + 2]);
			swap(b[i + 1], b[i + 3]);
			if (s.contains(b)) continue;
			s.insert(b);
			q.push(b);
		}
	}
	cout << sz(s) << endl;
	for (auto &a : s) cout << a << endl;
}
#line 1 "lib/sequence/inversion_count.hpp"



#line 10 "lib/sequence/inversion_count.hpp"
#include <ranges>
#include <type_traits>
#line 13 "lib/sequence/inversion_count.hpp"

template<class Range, class Compare = std::less<>>
	requires std::ranges::random_access_range<const Range> && std::ranges::sized_range<const Range>
std::int64_t inversion_count(const Range &a, Compare compare = {}) {
	assert(std::ranges::size(a) <= std::size_t(std::numeric_limits<int>::max()));
	const std::size_t n = std::ranges::size(a);
	auto first = std::ranges::begin(a);
	std::size_t ordered = 1;
	while (ordered < n && !compare(first[ordered], first[ordered - 1])) ++ordered;
	if (ordered >= n) return 0;
	std::int64_t equal_pairs = 0;
	std::size_t run = 1, reversed = 1;
	for (; reversed < n && !compare(first[reversed - 1], first[reversed]); ++reversed) {
		if (compare(first[reversed], first[reversed - 1])) run = 1;
		else equal_pairs += static_cast<std::int64_t>(run++);
	}
	if (reversed == n) return static_cast<std::int64_t>(n) * (n - 1) / 2 - equal_pairs;
	using T = std::ranges::range_value_t<const Range>;
	constexpr bool cached = std::is_trivially_copyable_v<T> && sizeof(T) <= 16 &&
		std::is_default_constructible_v<T> && std::is_copy_constructible_v<T> &&
		std::is_copy_assignable_v<T> && !std::is_same_v<T, bool>;
	using Stored = std::conditional_t<cached, T, int>;
	std::vector<Stored> current(n), buffer(n);
	for (std::size_t i = 0; i < n; ++i) {
		if constexpr (cached) current[i] = first[i];
		else current[i] = static_cast<int>(i);
	}
	auto value = [&](const Stored &x) -> decltype(auto) {
		if constexpr (cached) return (x);
		else return first[x];
	};
	std::int64_t result = 0;
	constexpr std::size_t block = 8;
	for (std::size_t l = 0; l < n; l += block) {
		const auto end = std::min(l + block, n);
		for (std::size_t i = l + 1; i < end; ++i) {
			Stored x = current[i];
			std::size_t j = i;
			while (j > l && compare(value(x), value(current[j - 1]))) current[j] = current[j - 1], --j;
			current[j] = x;
			result += static_cast<std::int64_t>(i - j);
		}
	}
	for (std::size_t width = block; width < n; width *= 2) {
		for (std::size_t l = 0; l < n; l += 2 * width) {
			const auto mid = std::min(l + width, n), r = std::min(l + 2 * width, n);
			if (mid == r || !compare(value(current[mid]), value(current[mid - 1]))) {
				std::copy(current.begin() + l, current.begin() + r, buffer.begin() + l);
				continue;
			}
			if (compare(value(current[r - 1]), value(current[l]))) {
				result += static_cast<std::int64_t>(mid - l) * (r - mid);
				std::copy(current.begin() + mid, current.begin() + r, buffer.begin() + l);
				std::copy(current.begin() + l, current.begin() + mid, buffer.begin() + (l + r - mid));
				continue;
			}
			std::size_t i = l, j = mid, k = l;
			while (i < mid && j < r) {
				if (compare(value(current[j]), value(current[i]))) {
					buffer[k++] = current[j++];
					result += static_cast<std::int64_t>(mid - i);
				} else buffer[k++] = current[i++];
			}
			std::copy(current.begin() + i, current.begin() + mid, buffer.begin() + k);
			std::copy(current.begin() + j, current.begin() + r, buffer.begin() + (k + mid - i));
		}
		current.swap(buffer);
	}
	return result;
}


#line 169 "a.cpp"
void solve() {
	string s, t;
	cin >> s >> t;
	const int n = sz(s);
	assert(sz(t) == n);
	if (s == t) {
		cout << "Yes" << endl;
		return;
	}
	if (n == 4) {
		swap(t[0], t[2]);
		swap(t[1], t[3]);
		if (s == t) {
			cout << "Yes" << endl;
			return;
		}
		cout << "No" << endl;
		return;
	}
	vec<int> ty;
	rep(c, 2) {
		vec<int> cnt1(26), cnt2(26);
		for (int i = c; i < n; i += 2) {
			cnt1[s[i] - 'a']++;
			cnt2[t[i] - 'a']++;
		}
		bool kabu = false;
		rep(i, 26) {
			if (cnt1[i] != cnt2[i]) {
				cout << "No" << endl;
				return;
			}
			kabu |= cnt1[i] >= 2;
		}
		if (kabu) continue;
		unordered_map<char, int> mp;
		for (int i = c; i < n; i += 2) mp[s[i]] = sz(mp);
		vec<int> pq(sz(mp));
		for (int i = c; i < n; i += 2) pq[mp[t[i]]] = (i - c) / 2;
		ty.push_back(inversion_count(pq) % 2);
	}
	if (sz(ty) == 2 && ty[0] != ty[1]) {
		cout << "No" << endl;
		return;
	}
	cout << "Yes" << endl;
	return;
}