#782979 (C++17) No.5007 Steiner Space Travel

提出ソース
結果

問題	No.5007 Steiner Space Travel
ユーザー	094
提出日時	2022-07-30 15:24:08
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	952 ms / 1,000 ms
コード長	35,570 bytes
コンパイル時間	2,352 ms
実行使用メモリ	6,952 KB
スコア	3,217,731
最終ジャッジ日時	2022-07-30 15:24:52
合計ジャッジ時間	33,686 ms
ジャッジサーバーID （参考情報）	judge12 / judge11
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	952 ms 4,900 KB
testcase_01	AC	952 ms 4,900 KB
testcase_02	AC	951 ms 6,948 KB
testcase_03	AC	952 ms 4,904 KB
testcase_04	AC	951 ms 4,904 KB
testcase_05	AC	952 ms 4,904 KB
testcase_06	AC	951 ms 4,904 KB
testcase_07	AC	951 ms 6,952 KB
testcase_08	AC	952 ms 4,900 KB
testcase_09	AC	952 ms 4,900 KB
testcase_10	AC	952 ms 4,904 KB
testcase_11	AC	952 ms 4,900 KB
testcase_12	AC	952 ms 4,904 KB
testcase_13	AC	952 ms 4,900 KB
testcase_14	AC	952 ms 4,900 KB
testcase_15	AC	951 ms 4,908 KB
testcase_16	AC	952 ms 6,948 KB
testcase_17	AC	952 ms 4,904 KB
testcase_18	AC	952 ms 6,952 KB
testcase_19	AC	950 ms 6,948 KB
testcase_20	AC	952 ms 4,904 KB
testcase_21	AC	952 ms 4,904 KB
testcase_22	AC	952 ms 3,816 KB
testcase_23	AC	952 ms 4,900 KB
testcase_24	AC	952 ms 4,904 KB
testcase_25	AC	952 ms 4,900 KB
testcase_26	AC	952 ms 4,904 KB
testcase_27	AC	952 ms 4,904 KB
testcase_28	AC	952 ms 4,900 KB
testcase_29	AC	952 ms 6,948 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
// made by https://github.com/094-gengar/add_lib_to_templ
#if !__INCLUDE_LEVEL__
#include __FILE__

const int alpha = 5;
int N, M;
vpii planets;
vpii stations;
// p1 -D=10-> p2                              => alpha^2*10^2            = 1000
// p1 -D=5-> s and s -D=5-> p2                => alpha*5^2+alpha*5^2     = 250
// p1 -D=3-> s and s -D=4-> s and s -D=3-> p2 => alpha*3^2+4^2+alpha*3^2 = 106
vvi dist;

int euclid2(pii a, pii b)
{ return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second); }
int euclid2(int x1, int y1, int x2, int y2)
{ return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2); }
pii middle(pii a, pii b)
{ return pii{(a.first + b.first) / 2, (a.second + b.second) / 2}; }
pii format(int x) { return pii{1 + (x >= N), (x % N) + 1}; }

void input();

int main()
{
	input();
	
	dist.assign(N + M, vi(N + M, 1 << 29));
	Vec<std::pair<int, pii>> distList{};
	vvpii g(N + M);
	rep(i, N)rep(j, i, N)
	{
		dist[i][j] = dist[j][i] = euclid2(planets[i], planets[j]) * alpha * alpha;
		g[i].eb(dist[i][j], j);
		g[j].eb(dist[j][i], i);
		distList.eb(dist[i][j], pii{i, j});
	}
	vb used(N, false);
	Vec<std::pair<int, vi>> groups{};
	rSort(distList);
	stations.assign(M, pii{-1, -1});
	int cnt{N};
	rep(i, M)
	{
		cauto[x, y] = distList[i].second;
		stations[i] = \
			middle(planets[x], planets[y]);
		dist[N + i][x] = dist[x][N + i] = euclid2(stations[i], planets[x]);
		dist[N + i][y] = dist[y][N + i] = euclid2(stations[i], planets[y]);
		g[N + i].eb(dist[N + i][x], x);
		g[x].eb(dist[x][N + i], N + i);
		g[N + i].eb(dist[N + i][y], y);
		g[y].eb(dist[y][N + i], N + i);

		groups.eb(dist[x][N + i] * alpha + dist[N + i][y] * alpha, vi{x, N + i, y});
		used[x] = true;
		used[y] = true;
	}
	rep(i, N)if(not used[i])groups.eb(0, vi{i});
	int SIZ = groups.size();
	rep(i, SIZ)rep(j, groups[i].second.size())if(groups[i].second[j] == 0)break_with(std::swap(groups[0], groups[i]));
	rep(i, M)m9::print(stations[i]);


	// 一回適当に書く
	auto eval = [&](Vec<std::pair<int, vi>> groups) -> int {
		int res{};

		res += groups[0].first;
		rep(i, SIZ - 1)
		{
			res += dist[groups[i].second.back()][groups[i + 1].second[0]];
			res += groups[i + 1].first;
		}
		return round(1e9 / (1000 + sqrt(res + dist[groups[SIZ - 1].second.back()][groups[0].second[0]])));
	};

	int bestScore{};
	while(timer.get_time() < 1000)
	{
		int i1 = ri.roll(SIZ - 1) + 1, i2 = ri.roll(SIZ - 1) + 1;
		std::swap(groups[i1], groups[i2]);
		int curScore = eval(groups);
		if(chmax(bestScore, curScore))
		{
			continue;
		}
		std::swap(groups[i1], groups[i2]);
	}
	assert(not groups.empty());

	vi salesman{};
	for(cauto p : groups)for(cauto x : p.second)salesman.eb(x);
	m9::print(salesman.size() + 1);
	for(cauto x : salesman)m9::print(format(x));
	m9::print(format(salesman[0]));
	fflush(stdout);
}

void input()
{
	using namespace m9;
	IN(N, M);
	planets.resize(N);
	IN(planets);
}

#else

// #line 2 "graph/Graph.hpp"
#include <cassert>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits>

namespace m9 {
template<class T> struct Graph {
	template<class _T> inline bool chmin(_T& a, const _T& b)
	{
		if(b < a) { a = b; return true; }
		else return false;
	}
	int SIZ;
	bool isOffset;
	bool isDirected;
	std::vector<std::vector<T>> G;
	Graph(int n, bool offset, bool directed) : SIZ(n), isOffset(offset), isDirected(directed), G(n) {}
	void init(int m)
	{
		T a, b;
		for(int i{}; i < m; i++)
		{
#ifdef MY_FASTIO
			io.IN(a, b);
#else
#ifdef MY_FASTIO_VER2
			IN(a, b);
#else
			std::cin >> a >> b;
#endif
#endif
			a -= isOffset; b -= isOffset;
			assert(0 <= a and a < SIZ);
			assert(0 <= b and b < SIZ);
			G[a].emplace_back(b);
			if(not isDirected)G[b].emplace_back(a);
		}
	}
	void init(std::vector<std::vector<T>> g) { G = g; }
	std::vector<T> bfs(T s, T t = -1)
	{
		assert(0 <= s and s < SIZ);
		assert((t == -1) or (0 <= s or s < SIZ));
		std::vector<T> dist(SIZ, std::numeric_limits<T>::max() / 2);
		std::vector<bool> vis(SIZ, false);
		dist[s] = 0;
		std::queue<T> q{};
		q.emplace(s);
		while(!q.empty())
		{
			T cur = q.front(); q.pop();
			for(const auto& e : G[cur])if(chmin(dist[e], dist[cur] + 1))q.emplace(e);
		}
		return (t == -1 ? dist : std::vector<T>{dist[t]});
	}
};

#include <utility>

template<class T> struct weightedGraph {
	using PTT = std::pair<T, T>;
	template<class _T> inline bool chmin(_T& a, const _T& b)
	{
		if(b < a) { a = b; return true; }
		else return false;
	}
	int SIZ;
	bool isOffset;
	bool isDirected;
	std::vector<std::vector<PTT>> G;
	weightedGraph(int n, bool os, bool drc) : SIZ(n), isOffset(os), isDirected(drc), G(n) {}
	void init(int m)
	{
		T a, b, cst;
		for(int i{}; i < m; i++)
		{
#ifdef MY_FASTIO
			io.IN(a, b, cst);
#else
#ifdef MY_FASTIO_VER2
			IN(a, b, cst);
#else
			std::cin >> a >> b >> cst;
#endif
#endif
			a -= isOffset; b -= isOffset;
			assert(0 <= a and a < SIZ);
			assert(0 <= b and b < SIZ);
			G[a].emplace_back(cst, b);
			if(not isDirected)G[b].emplace_back(cst, a);
		}
	}
	void init(std::vector<std::vector<PTT>> g) { G = g; }
	std::vector<T> bfs(T s, T t = -1)
	{
		assert(0 <= s and s < SIZ);
		assert((t == -1) or (0 <= s or s < SIZ));
		std::vector<T> dist(SIZ, std::numeric_limits<T>::max() / 2);
		std::vector<bool> vis(SIZ, false);
		dist[s] = 0;
		std::queue<PTT> q{};
		q.emplace(0, s);
		while(!q.empty())
		{
			const auto [curCst, curE]= q.front(); q.pop();
			if(curCst > dist[curE])continue;
			for(const auto&[cst, e] : G[curE])if(chmin(dist[e], dist[curE] + cst))q.emplace(dist[e], e);
		}
		return (t == -1 ? dist : std::vector<T>{dist[t]});
	}
	std::vector<T> dijk(T s, T t = -1)
	{
		assert(0 <= s and s < SIZ);
		assert((t == -1) or (0 <= s or s < SIZ));
		std::vector<T> dist(SIZ, std::numeric_limits<T>::max() / 2);
		std::vector<bool> vis(SIZ, false);
		dist[s] = 0;
		std::priority_queue<PTT, std::vector<PTT>, std::greater<>> pq{};
		pq.emplace(0, s);
		while(!pq.empty())
		{
			const auto [curCst, curE]= pq.top(); pq.pop();
			if(curCst > dist[curE])continue;
			for(const auto&[cst, e] : G[curE])if(chmin(dist[e], dist[curE] + cst))pq.emplace(dist[e], e);
		}
		return (t == -1 ? dist : std::vector<T>{dist[t]});
	}
};
} // namespace m9

// #line 2 "graph/SCC.hpp"
#include <cassert>
#include <vector>
#include <algorithm>
#include <set>

namespace m9 {
class SCC {
	int SIZ;
	std::vector<std::vector<int>> g, rg;
	std::vector<int> ord, comp;
	std::vector<bool> used;
public:
	void dfs(int cur)
	{
		used[cur] = true;
		for(const auto& e : g[cur])if(not used[e])dfs(e);
		ord.emplace_back(cur);
	}
	void rdfs(int cur, int k)
	{
		comp[cur] = k;
		for(const auto& e : rg[cur])if(comp[e] == -1)rdfs(e, k);
	}
	SCC(std::vector<std::vector<int>>& tmp) : g(tmp)
	{
		SIZ = static_cast<int>(g.size());
		rg.resize(SIZ);
		comp.assign(SIZ, -1);
		used.assign(SIZ, false);
		for(int v{}; v < SIZ; v++)
			for(const auto& e : g[v])
				rg[e].emplace_back(v);
		for(int v{}; v < SIZ; v++)if(not used[v])dfs(v);
		int k{};
		std::reverse(std::begin(ord), std::end(ord));
		for(const auto& v: ord)if(comp[v] == -1)rdfs(v, k++);
	}
	bool same(int u, int v)
	{
		assert(0 <= u and u < SIZ);
		assert(0 <= v and v < SIZ);
		return comp[u] == comp[v];
	}
	std::vector<std::vector<int>> rebuild()
	{
		int MX = *std::max_element(std::begin(comp), std::end(comp)) + 1;
		std::vector<std::vector<int>> rebuildedGraph(SIZ);
		std::set<std::pair<int, int>> conn{};
		for(int v{}; v < MX; v++)
			for(const auto& e : g[v])
				if(comp[v] != comp[e] and not conn.count(std::make_pair(v, e)))
					conn.emplace(v, e), rebuildedGraph[comp[v]].emplace_back(comp[e]);
		return rebuildedGraph;
	}
};
} // namespace m9

// #line 2 "heuristic/RandInt.hpp"
#include <random>
#include <ctime>

namespace m9 {
struct RandInt {
private:
	std::mt19937 mt;
public:
	RandInt() { mt.seed((unsigned int)time(0)); }
	unsigned int next() { return mt(); }
	unsigned int roll(int high)
	{
		std::uniform_int_distribution<unsigned int> die(0, high - 1);
		return die(mt);
	}
} ri;
} // namespace m9
using m9::ri;

// #line 2 "heuristic/Timer.hpp"
#include <chrono>

namespace m9 {
struct Timer {
private:
	std::chrono::system_clock::time_point m_start;
public:
	Timer() : m_start(std::chrono::system_clock::time_point::min()) { (*this).start(); }
	void clear() { m_start = std::chrono::system_clock::time_point::min(); }
	bool is_started() const { return (m_start.time_since_epoch() != std::chrono::system_clock::duration(0)); }
	void start() { m_start = std::chrono::system_clock::now(); }
	unsigned long long get_time()
	{
		if(is_started())
		{
			std::chrono::system_clock::duration diff;
			diff = std::chrono::system_clock::now() - m_start;
			return (unsigned long long)std::chrono::duration_cast<std::chrono::milliseconds>(diff).count() + 50;
		}
		return 0;
	}
} timer;
} // namespace m9
using m9::timer;

// #line 2 "io/FastIO.hpp"
#include <cstdint>
#include <cassert>
#include <cmath>
#include <unistd.h>
#include <string>
#include <array>
#include <vector>

#define MY_FASTIO_VER2
//#define IS_OUTPUT_ONLY

namespace m9 {
struct fastin
{
	std::array<signed char, 1048576> _buf;
	ssize_t n_w, n_r;
#ifdef IS_OUTPUT_ONLY
	fastin() {}
#else
	fastin() { _do_read(); }
#endif
	long long rd_ll() noexcept
	{
		long long ret = 0, sgn = 1;
		signed char ch = _current_char();
		while(ch == ' ' || ch == '\n')ch = _next_char();
		if(ch == '-') sgn *= -1, ch = _next_char();
		for(; '0' <= ch && ch <= '9'; ch = _next_char())
		{
			ret = (ret * 10) + ch - '0';
		}
		return sgn * ret;
	}
	int rd_int() noexcept
	{
		long long _result = rd_ll();
		assert(-2147483648ll <= _result && _result <= 2147483647ll);
		return static_cast<int>(_result);
	}
	std::string rd_str() noexcept
	{
		std::string _res{};
		signed char ch = _current_char();
		while(ch == ' ' || ch == '\n')ch = _next_char();
		for(; ch != -1 && ch != '\n' && ch != ' '; ch = _next_char())
		{
			_res += std::string(1, ch);
		}
		return _res;
	}
	char rd_chr() noexcept
	{
		signed char ch = _current_char();
		while(ch == ' ' || ch == '\n')ch = _next_char();
		signed char discard = _next_char();
		return ch;
	}
private:
	void _do_read() noexcept
	{
		ssize_t r = read(0, &_buf[0], _buf.size());
		assert(r >= 0);
		n_w = r, n_r = 0;
	}
	inline signed char _next_char() noexcept
	{
		if(++n_r == n_w)_do_read();
		return _current_char();
	}
	inline signed char _current_char() noexcept
	{
		return (n_r == n_w ? -1 : _buf[n_r]);
	}
} fi;

struct fastout
{
	unsigned _wt_double_digit = 15;
	inline void wt_bool(bool x) noexcept { putchar_unlocked(x ? '1' : '0'); }
	inline void wt_ll(long long x) noexcept
	{
		std::array<signed char, 32> _buf;
		ssize_t _siz = 0;
		if(x < 0)
		{
			x *= -1;
			putchar_unlocked('-');
		}
		if(x == 0)putchar_unlocked('0');
		while(x > 0)
		{
			_buf[_siz++] = x % 10 + '0';
			x /= 10;
		}
		while(_siz--)putchar_unlocked(_buf[_siz]);
	}
	inline void wt_int(int x) noexcept { wt_ll(static_cast<long long>(x)); }
	inline void wt_ull(unsigned long long x) noexcept
	{
		std::array<signed char, 32> _buf;
		ssize_t _siz = 0;
		if(x < 0)
		{
			x *= -1;
			putchar_unlocked('-');
		}
		if(x == 0)putchar_unlocked('0');
		while(x > 0)
		{
			_buf[_siz++] = x % 10 + '0';
			x /= 10;
		}
		while(_siz--)putchar_unlocked(_buf[_siz]);
	}
	inline void wt_chr(char x) noexcept { putchar_unlocked(x); }
	inline void wt_str(std::string x) noexcept
	{
		ssize_t _siz = static_cast<ssize_t>(x.length());
		for(ssize_t i = 0; i < _siz; i++)putchar_unlocked(x[i]);
	}
	inline void wt_dbl(double x) noexcept
	{
		int k, r = 0;
		double v = 1;
		if(x < 0)
		{
			x *= -1;
			putchar_unlocked('-');
		}
		x += 0.5 * pow(0.1, _wt_double_digit);
		while(x >= 10 * v)v *= 10, r++;
		while(r-- >= 0)
		{
			k = floor(x / v);
			if(k >= 10)k = 9;
			if(k <= -1)k = 0;
			x -= k * v;
			v *= 0.1;
			putchar_unlocked(k + '0');
		}
		if(_wt_double_digit > 0)
		{
			putchar_unlocked('.');
			v = 1;
			for(ssize_t _ = 0; _ < _wt_double_digit; _++)
			{
				v *= 0.1;
				k = floor(x / v);
				if(k >= 10)k = 9;
				if(k <= -1)k = 0;
				x -= k * v;
				putchar_unlocked(k + '0');
			}
		}
	}
	const char* END = "\n";
	const char* SPLIT = " ";
} fo;

inline void set_digit(unsigned d) { fo._wt_double_digit = d; }
inline void scan(int& x) noexcept { x = fi.rd_int(); }
inline void scan(long& x) noexcept { x = (sizeof(long) == 32 ? fi.rd_int() : fi.rd_ll()); }
inline void scan(long long& x) noexcept { x = fi.rd_ll(); }
inline void scan(unsigned& x) noexcept
{
	int a = fi.rd_int();
	assert(a >= 0);
	x = a;
}
inline void scan(unsigned long& x) noexcept
{
	long a;
	scan(a);
	assert(a >= 0l);
	x = a;
}
inline void scan(unsigned long long& x) noexcept
{
	long long a = fi.rd_ll();
	assert(a >= 0ll);
	x = a;
}
inline void scan(double& x) noexcept { x = static_cast<double>(fi.rd_ll()); }
inline void scan(char& x) noexcept { x = fi.rd_chr(); }
inline void scan(std::string& x) noexcept { x = fi.rd_str(); }
template<class T, class U>
inline void scan(std::pair<T, U>& x) { scan(x.first); scan(x.second); }
template<class T>
inline void scan(std::vector<T>& x) { for(auto& e : x)scan(e); }
void IN() {}
template<class Car, class... Cdr>
void IN(Car&& car, Cdr &&...cdr)
{
	scan(car);
	IN(std::forward<Cdr>(cdr)...);
}

inline void wt_any(const bool& x) noexcept { fo.wt_bool(x); }
inline void wt_any(const int& x) noexcept { fo.wt_int(x); }
inline void wt_any(const long& x) noexcept { fo.wt_ll(static_cast<long>(x)); }
inline void wt_any(const long long& x) noexcept { fo.wt_ll(x); }
inline void wt_any(const unsigned& x) noexcept { fo.wt_ull(static_cast<unsigned long long>(x)); }
inline void wt_any(const unsigned long& x) noexcept { fo.wt_ull(static_cast<unsigned long long>(x)); }
inline void wt_any(const unsigned long long& x) noexcept { fo.wt_ull(x); }
inline void wt_any(const double& x) noexcept { fo.wt_dbl(x); }
inline void wt_any(const char& x) noexcept { fo.wt_chr(x); }
inline void wt_any(const char x[]) noexcept
{
	size_t _siz = 0;
	while(x[_siz] != '\0')fo.wt_chr(x[_siz++]);
}
inline void wt_any(const std::string& x) noexcept { fo.wt_str(x); }
template<class T, class U>
inline void wt_any(const std::pair<T, U>& x)
{
	wt_any(x.first);
	wt_any(fo.SPLIT);
	wt_any(x.second);
}
template<class T>
inline void wt_any(const std::vector<T>& x)
{
	size_t _siz = x.size();
	for(size_t i = 0; i < _siz - 1; i++)wt_any(x[i]), wt_any(fo.SPLIT);
	wt_any(x.back());
}
int print() { wt_any(fo.END); return 0; }
template<class T>
int print(const T& t)
{
	wt_any(t);
	wt_any(fo.END);
	return 0;
}
template<class Car, class... Cdr>
int print(const Car& car, const Cdr &...cdr)
{
	wt_any(car);
	wt_any(fo.SPLIT);
	print(cdr...);
	return 0;
}
void yn(bool fl = true) { print(fl ? "Yes" : "No"); }
template<class T>
void drop(T x) { print(x); exit(0); }
void dyn(bool fl = true) { print(fl ? "Yes" : "No"); exit(0); }
void setEND(const char* c) { fo.END = c; }
void setSPLIT(const char* c) { fo.SPLIT = c; }

#define INT(...)  int __VA_ARGS__; IN(__VA_ARGS__)
#define LL(...)  long long __VA_ARGS__; IN(__VA_ARGS__)
#define ULL(...)  unsigned long long __VA_ARGS__; IN(__VA_ARGS__)
#define STR(...)  std::string __VA_ARGS__; IN(__VA_ARGS__)
#define CHR(...)  char __VA_ARGS__; IN(__VA_ARGS__)
#define DBL(...)  double __VA_ARGS__; IN(__VA_ARGS__)

using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

#define VEC(a, type, n) std::vector<type> (a)(n); IN(a)
#define VVEC(a, type, h, w) std::vector<std::vector<type>> (a)(h, std::vector<type>(w)); IN(a)

#define VI(a, n) VEC(a, int, n)
#define VVI(a, h, w) VVEC(a, int, h, w)
#define VPII(a, n) VEC(a, pii, n)
#define VVPII(a, h, w) VVEC(a, pii, h, w)
#define VLL(a, n) VEC(a, ll, n)
#define VVLL(a, h, w) VVEC(a, ll, h, w)
#define VPLL(a, n) VEC(a, pll, n)
#define VVPLL(a, h, w) VVEC(a, pll, h, w)
#define VULL(a, n) VEC(a, ull, n)
#define VVULL(a, h, w) VVEC(a, ull, h, w)
#define VC(a, n) VEC(a, char, n)
#define VVC(a, h, w) VVEC(a, char, h, w)
#define VD(a, n) VEC(a, double, n)
#define VVD(a, h, w) VVEC(a, double, h, w)
#define VS(a, n) VEC(a, std::string, n)
} // namespace m9


// #line 2 "math/ArgSort.hpp"
#include <utility>

namespace m9 {
template<class T> bool arg_cmp(const std::pair<T, T>& p, const std::pair<T, T>& q)
{
	auto area = [](const std::pair<T, T>& a) -> int {
		const auto&[x, y] = a;
		if(y < 0)return -1;
		else if(y == 0 and 0 <= x)return 0;
		else return 1;
	};
	const int ap = area(p);
	const int aq = area(q);
	if(ap != aq)return ap < aq;
	else
	{
		const auto& [px, py] = p;
		const auto& [qx, qy] = q;
		return (0 < (px * qy - py * qx));
	}
}
} // namespace m9

// #line 2 "math/Combination.hpp"
#include <cassert>
#include <vector>

namespace m9 {
template<class T> struct combination {
	using ll = long long;
	ll N;
	std::vector<T> fct;
	combination(ll n) : N(n)
	{
		fct.resize(N + 1);
		fct[0] = 1;
		for(ll i{1}; i <= N; i++)fct[i] = fct[i - 1] * i;
	}
	T nPr(ll n, ll r) { return n < 0 || r < 0 || n < r ? (T)(0) : fct[n] / fct[n - r]; }
	T nCr(ll n, ll r) { return n < 0 || r < 0 || n < r ? (T)(0) : nPr(n, r) / fct[r]; }
	T nHr(ll n, ll r) {return n < 0 || r + n - 1 < 0 || n < r + n - 1 ? (T)(0) : nCr(r + n - 1, r); }
};
} // namespace m9

// #line 2 "math/DivisorList.hpp"
#include <vector>
#include <algorithm>

namespace m9 {
template<class T> std::vector<T> divisorList(const T& N)
{
	std::vector<T> result{};
	for(T i{1}; i * i <= N; i++)
	{
		if(N % i == 0)
		{
			result.emplace_back(i);
			if(i * i != N)result.emplace_back(N / i);
		}
	}
	std::sort(std::begin(result), std::end(result));
	return result;
}
} // namespace m9

// #line 2 "math/ModInt.hpp"
#include <iostream>

namespace m9 {
#define MY_MODINT
template<long long Mod> struct modInt {
	long long x;
	constexpr modInt() noexcept : x() {}
	template<class T>
	constexpr modInt(T v = 0) noexcept : x(v% Mod) { if(x < 0)x += Mod; }
	constexpr long long val() const noexcept { return x; }
	constexpr modInt operator-() const noexcept { return x ? Mod - x : 0; }
	constexpr modInt operator+(const modInt& r) const noexcept { return modInt(*this) += r; }
	constexpr modInt operator-(const modInt& r) const noexcept { return modInt(*this) -= r; }
	constexpr modInt operator*(const modInt& r) const noexcept { return modInt(*this) *= r; }
	constexpr modInt operator/(const modInt& r) const noexcept { return modInt(*this) /= r; }
	constexpr modInt& operator+=(const modInt& r) noexcept { x += r.x; if(x >= Mod)x -= Mod; return *this; }
	constexpr modInt& operator-=(const modInt& r) noexcept { x -= r.x; if(x < 0)x += Mod; return *this; }
	constexpr modInt& operator*=(const modInt& r) noexcept { x = x * r.x % Mod; return *this; }
	constexpr modInt& operator/=(const modInt& r) noexcept { x = x * r.inv().val() % Mod; return *this; }
	constexpr modInt powm(long long n) noexcept
	{
		if(n < 0)return powm(-n).inv();
		modInt x = *this, r = 1;
		for(; n; x *= x, n >>= 1)if(n & 1)r *= x;
		return r;
	}
	constexpr modInt inv() const noexcept
	{
		long long a = x, b = Mod, u = 1, v = 0;
		while(b)
		{
			long long t = a / b;
			a -= t * b;
			std::swap(a, b);
			u -= t * v;
			std::swap(u, v);
		}
		return modInt(u);
	}
	constexpr modInt comb(long long a) noexcept
	{
		modInt n = *this, s = 1;
		for(int i = 0; i < a; i++)s *= (n - modInt(i));
		modInt m = 1;
		for(int i = 1; i <= a; i++)m *= modInt(i);
		return s * m.powm(Mod - 2);
	}
	constexpr bool operator==(const modInt& r) { return this->x == r.x; }
	constexpr bool operator!=(const modInt& r) { return this->x != r.x; }
	friend std::ostream& operator<<(std::ostream& os, const modInt<Mod>& a) { return os << a.x; }
	friend std::istream& operator>>(std::istream& is, modInt<Mod>& a)
	{
		long long v;
		is >> v;
		a = modInt<Mod>(v);
		return is;
	}
};

using mint = modInt<1000000007>;
using mint2 = modInt<998244353>;
} // namespace m9

// #line 2 "math/PrimeFactor.hpp"
#include <vector>

namespace m9 {
template<class T> std::vector<std::pair<T, T>> prime_factor(T n)
{
	std::vector<std::pair<T, T>> ret;
	for(T i{2}; i * i <= n; i++)
	{
		if(n % i != 0)continue;
		T tmp = 0;
		while(n % i == 0)
		{
			tmp++;
			n /= i;
		}
		ret.push_back(std::make_pair(i, tmp));
	}
	if(n != 1)
		ret.push_back(std::make_pair(n, 1));
	return ret;
}
} // namespace m9

// #line 2 "other/Integers.hpp"
#include <iostream>

namespace m9 {
struct cent_t {
private:
	__int128_t N;
public:
	template<class T>
	constexpr cent_t(T n) : N(static_cast<__int128_t>(n)) {}
	friend std::ostream& operator<<(std::ostream& os, const cent_t& a)
		{ if(a.N > INT64_MAX)return os << "too big integer"; else return os << static_cast<long long>(a.N); }
	friend std::istream& operator>>(std::istream& is, cent_t& a)
		{ long long tmp{}; is >> tmp; a.N = static_cast<__int128_t>(tmp); return is; }
	constexpr __int128_t val() const noexcept { return N; }
	constexpr cent_t operator-() const noexcept { return -N; }
	template<class INTEGER> constexpr cent_t operator+(const INTEGER& x) const noexcept { return N + x.N; }
	template<class INTEGER> constexpr cent_t operator-(const INTEGER& x) const noexcept { return N - x.N; }
	template<class INTEGER> constexpr cent_t operator*(const INTEGER& x) const noexcept { return N * x.N; }
	template<class INTEGER> constexpr cent_t operator/(const INTEGER& x) const noexcept { return N / x.N; }
	template<class INTEGER> constexpr cent_t operator+=(const INTEGER& x) noexcept { N += x.N; return *this; }
	template<class INTEGER> constexpr cent_t operator-=(const INTEGER& x) noexcept { N -= x.N; return *this; }
	template<class INTEGER> constexpr cent_t operator*=(const INTEGER& x) noexcept { N *= x.N; return *this; }
	template<class INTEGER> constexpr cent_t operator/=(const INTEGER& x) noexcept { N /= x.N; return *this; }
	constexpr cent_t operator++() noexcept { N += 1; return *this; }
	constexpr cent_t operator--() noexcept { N -= 1; return *this; }
	template<class INTEGER> constexpr bool operator==(const INTEGER& x) { return this->N == x.N; }
	template<class INTEGER> constexpr bool operator!=(const INTEGER& x) { return this->N != x.N; }
	template<class INTEGER> constexpr bool operator<(const INTEGER& x) { return this->N < x.N; }
	template<class INTEGER> constexpr bool operator>(const INTEGER& x) { return this->N > x.N; }
	template<class INTEGER> constexpr bool operator<=(const INTEGER& x) { return this->N <= x.N; }
	template<class INTEGER> constexpr bool operator>=(const INTEGER& x) { return this->N >= x.N; }
};
} // namespace m9

using i8 = signed char;
using u8 = unsigned char;
using i32 = signed int;
using u32 = unsigned int;
using i64 = signed long long;
using u64 = unsigned long long;

i8 operator"" _i8(unsigned long long x) { return static_cast<i8>(x); }
u8 operator"" _u8(unsigned long long x) { return static_cast<u8>(x); }
i32 operator"" _i32(unsigned long long x) { return static_cast<i32>(x); }
u32 operator"" _u32(unsigned long long x) { return static_cast<u32>(x); }
i64 operator"" _i64(unsigned long long x) { return static_cast<i64>(x); }
u64 operator"" _u64(unsigned long long x) { return static_cast<u64>(x); }
m9::cent_t operator"" _i128(unsigned long long x) { return m9::cent_t(x); }

using f32 = float;
using f64 = double;
double operator"" _f32(unsigned long long x) { return static_cast<f32>(x); }
double operator"" _f64(unsigned long long x) { return static_cast<f64>(x); }

// #line 2 "other/others.hpp"
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstdint>
#include <cstring>
#include <ctime>
#include <chrono>
//#include <bit>
#include <iterator>
#include <bitset>
#include <numeric>
#include <list>
#include <iomanip>
#include <cassert>
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>
#include <random>
#include <regex>
//#define INCLUDE_BOOST
#ifdef INCLUDE_BOOST
#if __has_include(<boost/range/irange.hpp>)
#include <boost/range/irange.hpp>
#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/join.hpp>
#include <boost/algorithm/string/replace.hpp>
#include <boost/algorithm/string/classification.hpp>
#endif
#endif
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,fma,abm,mmx,avx,avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define all(x) std::begin(x), std::end(x)
#define Sort(x) sort(all(x))
#define rSort(x) sort(all(x)); reverse(all(x))
#define UNIQUE(v) v.erase(unique(all(v)), v.end())
#define uniq(v) sort(all(v)); UNIQUE(v)
#define l_b(c, x) distance(begin(c), lower_bound(all(c), (x)))
#define u_b(c, x) distance(begin(c), upper_bound(all(c), (x)))
#define fi first
#define se second
#define m_p make_pair
#define m_t make_tuple
#define pb push_back
#define eb emplace_back
#define cauto const auto&
#define _rep_overload(_1, _2, _3, _4, name, ...) name
#define _rep1(i, n) _rep2(i, 0, n)
#define _rep2(i, a, b) for(int i = (a); i < (b); i++)
#define _rep3(i, a, b, c) for(int i = (a); i < (b); i += c)
#define rep(...) _rep_overload(__VA_ARGS__, _rep3, _rep2, _rep1)(__VA_ARGS__)
#define myceil(a, b) ((a) + ((b) - 1)) / (b)
#define continue_with(...) ({__VA_ARGS__; continue;})
#define break_with(...) ({__VA_ARGS__; break;})

#include <utility>

//#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
using pll = std::pair<ll, ll>;

#include <vector>
#include <string>

template<class T>
using Vec = std::vector<T>;
using vb = Vec<bool>;
using vi = Vec<int>;
using vu = Vec<unsigned>;
using vll = Vec<ll>;
using vull = Vec<ull>;
using vd = Vec<double>;
using vc = Vec<char>;
using vs = Vec<std::string>;
using vpii = Vec<pii>;
using vpll = Vec<pll>;

using vvb = Vec<vb>;
using vvi = Vec<vi>;
using vvu = Vec<vu>;
using vvll = Vec<vll>;
using vvull = Vec<vull>;
using vvd = Vec<vd>;
using vvc = Vec<vc>;
using vvs = Vec<vs>;
using vvpii = Vec<vpii>;
using vvpll = Vec<vpll>;

template <class T>
inline bool chmin(T& a, const T& b)
{
	if(b < a)
	{
		a = b;
		return true;
	}
	return false;
}
template <class T>
inline bool chmax(T& a, const T& b)
{
	if(a < b)
	{
		a = b;
		return true;
	}
	return false;
}

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
ll fact(ll n, ll m)
{
	ll f = n;
	for(ll i = n - 1; i >= 1; i--)
	{
		f *= i;
		if(m != -1)f %= m;
	}
	return f;
}
constexpr ll inf = 0x1fffffffffffffff;
constexpr ll mod = 1000000007LL;
constexpr ll mod2 = 998244353LL;
constexpr double eps = 1e-8;
constexpr double pi = 3.141592653589793238462643383279;

#include <vector>
#include <algorithm>
#include <string>

struct sorted_operator {
	template<class T> friend std::vector<T> operator>>(std::vector<T>a, sorted_operator)
		{ std::sort(std::begin(a), std::end(a)); return a; }
	friend std::string operator>>(std::string a, sorted_operator)
		{ std::sort(std::begin(a), std::end(a)); return a; }
} Sor;
struct reversed_operator {
	template<class T> friend std::vector<T> operator>>(std::vector<T> a, reversed_operator)
		{ std::reverse(std::begin(a), std::end(a)); return a; }
	friend std::string operator>>(std::string a, reversed_operator)
		{ std::reverse(std::begin(a), std::end(a)); return a; }
} Rev;
struct unique_operator {
	template<class T> friend std::vector<T> operator>>(std::vector<T> a, unique_operator)
		{ a.erase(unique(std::begin(a), std::end(a)), std::end(a)); return a; }
	friend std::string operator>>(std::string a, unique_operator)
		{ a.erase(unique(std::begin(a), std::end(a)), std::end(a)); return a; }	
} Set;
template <class T>
void INCVEC(std::vector<T>& a) { for(T& e : a)e++; }
template <class T>
void DECVEC(std::vector<T>& a) { for(T& e : a)e--; }
struct inc_operator {
	template<class T> friend std::vector<T> operator>>(std::vector<T> a, inc_operator)
		{ INCVEC(a); return a; }
} Inc;
struct dec_operator {
	template<class T> friend std::vector<T> operator>>(std::vector<T> a, dec_operator)
		{ DECVEC(a); return a; }
} Dec;
template <class T, class F>
auto operator>> (std::vector<T> a, F f) -> std::vector<decltype(f(a.front()))>
{
	std::vector<decltype(f(a.front()))> res{};
	for(const T& e : a)res.emplace_back(f(e));
	return res;
}

#include <iostream>

namespace m9 {
#ifdef ONLINE_JUDGE
#define dbg(...) void(0)

#else
#define dbg(...) _DEBUG(#__VA_ARGS__, __VA_ARGS__)

template<class Car, class... Cdr>
void _DEBUG(const char* s, Car&& car, Cdr&&... cdr)
{
	constexpr const char* open_br = sizeof...(cdr) == 0 ? "" : "(";
	constexpr const char* close_br = sizeof...(cdr) == 0 ? "" : ")";
#ifdef MY_FASTIO
	io.wt_any(open_br); io.wt_any(s); io.wt_any(close_br);
	io.wt_any(" : ");
	io.wt_any(open_br); io.wt_any(std::forward<Car>(car));
	((io.wt_any(", "), io.wt_any(std::forward<Cdr>(cdr))), ...);
	io.wt_any(close_br); io.wt_any("\n");
#else
#ifdef MY_FASTIO_VER2
	wt_any(open_br); wt_any(s); wt_any(close_br);
	wt_any(" : ");
	wt_any(open_br); wt_any(std::forward<Car>(car));
	((wt_any(", "), wt_any(std::forward<Cdr>(cdr))), ...);
	wt_any(close_br); wt_any("\n");
#else
	std::cerr << open_br << s << close_br << " : " << open_br << std::forward<Car>(car);
	((std::cerr << ", " << std::forward<Cdr>(cdr)), ...);
	std::cerr << close_br << "\n";
#endif
#endif
}
#endif
} // namespace m9

// #line 2 "structure/BinaryIndexedTree.hpp"
#include <cassert>
#include <vector>

namespace m9 {
template<class T> class BIT {
	int SIZ;
	std::vector<T> tree;
public:
	BIT(int n = 0, T x = 0) : SIZ(n), tree(n, x) {}
	T sum(int i)
	{
		assert(0 <= i and i <= SIZ);
		T result{0};
		for(; i > 0; i -= (i & -i))result += tree[i - 1];
		return result;
	}
	T sum(int l, int r) { return sum(r) - sum(l); }
	void add(int i, T a) { assert(0 <= i and i < SIZ); for(i++; i <= SIZ; i += (i & -i))tree[i - 1] += a; }
	int lowerBound(T k)
	{
		if(k <= 0)return 0;
		int result{0}, i{1};
		for(; (i << 1) <= SIZ; )i <<= 1;
		for(; i; i >>= 1)if(result + i <= SIZ and tree[result + i] < k)k -= tree[result += i];
		return result;
	}
};
} // namespace m9

// #line 2 "structure/CompressVec.hpp"
#include <map>

namespace m9 {
template<class T> struct compress {
private:
	int SIZ;
public:
	std::vector<T> C;
	compress(std::vector<T> a)
	{
		SIZ = a.size();
		C = a;
		std::map<T, T> mp{};
		for(int i{}; i < SIZ; i++)mp[C[i]] = -1;
		int c{};
		for(auto&[key, value] : mp)value = c++;
		for(int i{}; i < SIZ; i++)C[i] = mp[C[i]];
	}
	void init(std::vector<T> a)
	{
		SIZ = a.size();
		C = a;
		std::map<T, T> mp{};
		for(int i{}; i < SIZ; i++)mp[C[i]] = -1;
		int c{};
		for(auto&[key, value] : mp)value = c++;
		for(int i{}; i < SIZ; i++)C[i] = mp[C[i]];
	}
	T operator[](int idx) { assert(0 <= idx and idx < SIZ); return C[idx]; }
};
} // namespace m9

// #line 2 "structure/Cumsum.hpp"
#include <cassert>

namespace m9 {
template<class T> struct cumsum {
private:
	int SIZ;
public:
	std::vector<T> S;
	cumsum(std::vector<T> a)
	{
		SIZ = a.size();
		S.assign(SIZ + 1, 0);
		for(int i{}; i < SIZ; i++)S[i + 1] = S[i] + a[i];
	}
	void init(std::vector<T> a)
	{
		SIZ = a.size();
		S.assign(SIZ + 1, 0);
		for(int i{}; i < SIZ; i++)S[i + 1] = S[i] + a[i];
	}
	T operator[](int idx) { assert(0 <= idx and idx <= SIZ); return S[idx]; }
};
} // namespace m9

// #line 2 "structure/SegmentTree.hpp"
#include <cassert>
#include <vector>

namespace m9 {
template<class M> class segmentTree {
	using T = typename M::valueType;
	std::vector<T> seg;
	int SIZ;
public:
	segmentTree(int n) { for(SIZ = 1; SIZ < n; )SIZ <<= 1; seg.assign(2 * SIZ, M::id);}
	void update(int k, const T& x) { assert(0 <= k and k < SIZ); for(seg[k += SIZ] = x; k>>= 1; )seg[k] = M::op(seg[2 * k], seg[2 * k + 1]); }
	void set(int k, const T& x) { assert(0 <= k and k < SIZ); seg[k + SIZ] = x; }
	T operator[](const int& k) const { assert(0 <= k and k < SIZ); return seg[k + SIZ]; }
	void build() { for(int k = SIZ - 1; k > 0; k--)seg[k] = M::op(seg[2 * k], seg[2 * k + 1]); }
	T query(int a, int b)
	{
		assert(0 <= a and a <= b and b <= SIZ);
		auto L = M::id;
		auto R = M::id;
		for(a += SIZ, b += SIZ; a < b; a >>= 1, b >>= 1)
		{
			if(a & 1)L = M::op(L, seg[a++]);
			if(b & 1)R = M::op(seg[--b], R);
		}
		return M::op(L, R);
	}
	template<class C> int findSubtree(int a, const C& check, T& mono, bool type)
	{
		for(; a < SIZ; )
		{
			auto next = M::op(seg[2 * a + type], mono);
			if(check(next))a = 2 * a + type;
			else mono = next, a = 2 * a + !type;
		}
		return (a - SIZ);
	}
	template<class C> int findFirst(int a, const C& check)
	{
		assert(0 <= a and a <= SIZ);
		auto L = M::id;
		if(a <= 0)return (check(M::op(L, seg[1])) ? findSubtree(1, check, L, false) : -1);
		int b = SIZ;
		for(a += SIZ, b += SIZ; a < b; a >>= 1, b >>= 1)
		{
			if(a & 1)
			{
				auto next = M::op(L, seg[a]);
				if(check(next))return findSubtree(a, check, L, false);
				L = next;
				a++;
			}
		}
		return -1;
	}
	template<class C> int findLast(int b, const C& check)
	{
		assert(0 <= b and b <= SIZ);
		auto R = M::id;
		if(b >= SIZ)return (check(M::op(seg[1], R)) ? findSubtree(1, check, R, true) : -1);
		int a = SIZ;
		for(b += SIZ; a < b; a >>= 1, b >>= 1)
		{
			if(b & 1)
			{
				auto next = M::op(seg[--b], R);
				if(check(next))return findSubtree(b, check, R, true);
				R = next;
			}
		}
		return -1;
	}
};

struct RSumQ {
	using valueType = int;
	static int op(int a, int b) { return a + b; }
	static inline int id{0};
};
struct RSumQLL {
	using valueType = long long;
	static long long op(long long a, long long b) { return a + b; }
	static inline long long id{0};
};
struct RMaxQ {
	using valueType = int;
	static int op(int a, int b) { return std::max(a, b); }
	static inline int id{-(1 << 29)};
};
struct RMaxQLL {
	using valueType = long long;
	static long long op(long long a, long long b) { return std::max(a, b); }
	static inline long long id{-(1ll << 60)};
};
struct RminQ {
	using valueType = int;
	static int op(int a, int b) { return std::min(a, b); }
	static inline int id{1 << 29};
};
struct RminQLL {
	using valueType = long long;
	static long long op(long long a, long long b) { return std::min(a, b); }
	static inline long long id{1ll << 60};
};
} // namespace m9

// #line 2 "structure/UnionFind.hpp"
#include <cassert>
#include <vector>
#include <algorithm>

namespace m9 {
class UnionFind {
	int SIZ;
	std::vector<int> a;
public:
	UnionFind(int n) : SIZ(n), a(n) { for(int i{}; i < SIZ; i++)a[i] = -1; }
	int root(int x) { assert(x < SIZ); return (a[x] < 0 ? x : (a[x] = root(a[x]))); }
	bool same(int x, int y) { assert(x < SIZ); assert(y < SIZ); return root(x) == root(y); }
	void merge(int x, int y)
	{
		assert(x < SIZ);
		assert(y < SIZ);
		x = root(x), y = root(y);
		if(x == y)return;
		if(a[x] > a[y])std::swap(x, y);
		a[x] += a[y], a[y] = x;
	}
	int size(int x) { assert(x < SIZ); return -a[root(x)]; }
	std::vector<std::vector<int>> groups()
	{
		std::vector<int> rootBuf(SIZ), groupSize(SIZ);
		for(int i{}; i < SIZ; i++)groupSize[rootBuf[i] = root(i)]++;
		std::vector<std::vector<int>> result(SIZ);
		for(int i{}; i < SIZ; i++)result[i].reserve(groupSize[i]);
		for(int i{}; i < SIZ; i++)result[rootBuf[i]].emplace_back(i);
		result.erase( \
			remove_if(std::begin(result),
				std::end(result),
				[&](const std::vector<int>& v) -> bool { return v.empty(); }),
			std::end(result));
		return result;
	}
};

using uni = UnionFind;
} // namespace m9

#endif
yukicoder

結果

テストケース

ソースコード
