#955780 (C++23) No.5020 Averaging

提出ソース
結果

問題	No.5020 Averaging
ユーザー	さはら
提出日時	2024-02-25 17:24:51
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	914 ms / 1,000 ms
コード長	55,648 bytes
コンパイル時間	4,991 ms
コンパイル使用メモリ	260,008 KB
実行使用メモリ	26,676 KB
スコア	29,359,140
最終ジャッジ日時	2024-02-25 17:25:45
合計ジャッジ時間	53,178 ms
ジャッジサーバーID （参考情報）	judge11 / judge13
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	876 ms 26,676 KB
testcase_01	AC	893 ms 26,676 KB
testcase_02	AC	865 ms 26,676 KB
testcase_03	AC	891 ms 26,676 KB
testcase_04	AC	886 ms 26,676 KB
testcase_05	AC	855 ms 26,676 KB
testcase_06	AC	875 ms 26,676 KB
testcase_07	AC	862 ms 26,676 KB
testcase_08	AC	876 ms 26,676 KB
testcase_09	AC	862 ms 26,676 KB
testcase_10	AC	902 ms 26,676 KB
testcase_11	AC	904 ms 26,676 KB
testcase_12	AC	870 ms 26,676 KB
testcase_13	AC	844 ms 26,676 KB
testcase_14	AC	876 ms 26,676 KB
testcase_15	AC	867 ms 26,676 KB
testcase_16	AC	868 ms 26,676 KB
testcase_17	AC	878 ms 26,676 KB
testcase_18	AC	887 ms 26,676 KB
testcase_19	AC	873 ms 26,676 KB
testcase_20	AC	897 ms 26,676 KB
testcase_21	AC	880 ms 26,676 KB
testcase_22	AC	856 ms 26,676 KB
testcase_23	AC	894 ms 26,676 KB
testcase_24	AC	844 ms 26,676 KB
testcase_25	AC	863 ms 26,676 KB
testcase_26	AC	899 ms 26,676 KB
testcase_27	AC	872 ms 26,676 KB
testcase_28	AC	857 ms 26,676 KB
testcase_29	AC	892 ms 26,676 KB
testcase_30	AC	885 ms 26,676 KB
testcase_31	AC	886 ms 26,676 KB
testcase_32	AC	860 ms 26,676 KB
testcase_33	AC	876 ms 26,676 KB
testcase_34	AC	880 ms 26,676 KB
testcase_35	AC	883 ms 26,676 KB
testcase_36	AC	857 ms 26,676 KB
testcase_37	AC	883 ms 26,676 KB
testcase_38	AC	875 ms 26,676 KB
testcase_39	AC	847 ms 26,676 KB
testcase_40	AC	885 ms 26,676 KB
testcase_41	AC	906 ms 26,676 KB
testcase_42	AC	876 ms 26,676 KB
testcase_43	AC	861 ms 26,676 KB
testcase_44	AC	886 ms 26,676 KB
testcase_45	AC	908 ms 26,676 KB
testcase_46	AC	899 ms 26,676 KB
testcase_47	AC	914 ms 26,676 KB
testcase_48	AC	884 ms 26,676 KB
testcase_49	AC	865 ms 26,676 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#else
#undef NDEBUG
#endif

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <concepts>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <mutex>
#include <numeric>
#include <optional>
#include <queue>
#include <ranges>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <thread>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

namespace shr {
	namespace basic {
		using namespace std;
		using uchar = unsigned char;
		using uint = unsigned int;
		using ushort = unsigned short;
		using ull = unsigned long long;
		using ll = long long;
		using pii = pair<int, int>;
		using pdi = pair<double, int>;

		template <class T>
		concept printable = requires(T t, ostream& out) { out << t; };

		int len(const string& a) {
			return (int) a.length();
		}

		template <class T>
		int len(const vector<T>& a) {
			return (int) a.size();
		}

		template <class T>
		int len(const set<T>& a) {
			return (int) a.size();
		}

		template <class T>
		int len(const deque<T>& a) {
			return (int) a.size();
		}

		template <class T>
		int len(const priority_queue<T>& a) {
			return (int) a.size();
		}

		template <class T, int N>
		int len(const T (&a)[N]) {
			return N;
		}

		template <class T, int N>
		void clear_with(T (&a)[N], int val) {
			memset(a, val, sizeof(a));
		}

		template <totally_ordered T>
		bool update_min(T candidate, T& current_min) {
			if (candidate < current_min) {
				current_min = candidate;
				return true;
			}
			return false;
		}

		template <totally_ordered T>
		bool update_min_eq(T candidate, T& current_min) {
			if (candidate <= current_min) {
				current_min = candidate;
				return true;
			}
			return false;
		}

		template <totally_ordered T>
		bool update_max(T candidate, T& current_max) {
			if (candidate > current_max) {
				current_max = candidate;
				return true;
			}
			return false;
		}

		template <totally_ordered T>
		bool update_max_eq(T candidate, T& current_max) {
			if (candidate >= current_max) {
				current_max = candidate;
				return true;
			}
			return false;
		}

		template <class T>
		string tos(T a) {
			return to_string(a);
		}

		template <printable T>
		string tos(T a) {
			ostringstream os;
			os << a;
			return os.str();
		}

		constexpr double linearstep(double edge0, double edge1, double t) {
			return clamp((t - edge0) / (edge1 - edge0), 0.0, 1.0);
		}

		constexpr double smoothstep(double edge0, double edge1, double t) {
			t = linearstep(edge0, edge1, t);
			return t * t * (3 - 2 * t);
		}

		double exp_interp(double from, double to, double t) {
			return pow(from, 1 - t) * pow(to, t);
		}
	} // namespace basic
	using namespace basic;

	namespace timer {
		double time_scale = 1.0;

		// return in ms
		int timer(bool reset = false) {
			static auto st = chrono::system_clock::now();
			if (reset) {
				st = chrono::system_clock::now();
				return 0;
			} else {
				auto en = chrono::system_clock::now();
				int elapsed = (int) chrono::duration_cast<chrono::milliseconds>(en - st).count();
				return (int) round(elapsed / time_scale);
			}
		}
	} // namespace timer

	namespace tracer {
		bool debug = true;

		template <class T>
		concept is_pair = requires(T t) {
			t.first;
			t.second;
		};

		template <class T>
		concept has_str = requires(T t) {
			{ t.str() } -> convertible_to<string>;
		};

		template <printable T>
		void tracen(T&& t) {
			if (!debug)
				return;
			cerr << t;
		}

		template <class T>
		requires(has_str<T> && !printable<T>)
		void tracen(T&& t) {
			if (!debug)
				return;
			cerr << t.str();
		}

		template <class T, class U>
		void tracen(pair<T, U>& t) { // <- ?????????????????????? need this for trace(<iterable of pairs>)
			if (!debug)
				return;
			cerr << "(";
			tracen(t.first);
			cerr << ", ";
			tracen(t.second);
			cerr << ")";
		}

		template <class T, class U>
		void tracen(pair<T, U>&& t) { // <- ?????????????????????? need this for trace(make_pair(1, 2))
			if (!debug)
				return;
			cerr << "(";
			tracen(t.first);
			cerr << ", ";
			tracen(t.second);
			cerr << ")";
		}

		template <class T>
		requires(!printable<T>)
		void tracen(T&& t) {
			if (!debug)
				return;
			bool first = true;
			auto from = t.begin();
			auto until = t.end();
			cerr << "{";
			while (from != until) {
				if (first) {
					first = false;
				} else {
					cerr << ", ";
				}
				tracen(*from);
				from++;
			}
			cerr << "}";
		}

		template <class T, int N>
		requires(!same_as<decay_t<T>, char>)
		void tracen(T (&a)[N]) {
			if (!debug)
				return;
			cerr << "{";
			for (int i = 0; i < N; i++) {
				if (i > 0)
					cerr << ", ";
				tracen(a[i]);
			}
			cerr << "}";
		}

		template <class T1, class T2, class... Rest>
		void tracen(T1&& t1, T2&& t2, Rest&&... rest) {
			if (!debug)
				return;
			tracen(forward<T1>(t1));
			tracen(forward<T2>(t2), forward<Rest>(rest)...);
		}

		void trace() {
			if (!debug)
				return;
			cerr << endl;
		}

		template <class T, class... Rest>
		void trace(T&& t, Rest&&... rest) {
			if (!debug)
				return;
			tracen(forward<T>(t), forward<Rest>(rest)...);
			cerr << endl;
		}

		template <class T>
		requires(!printable<T>)
		void trace2d(T&& t, int h, int w) {
			if (!debug)
				return;
			bool first = true;
			auto from = t.begin();
			auto until = t.end();
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (j > 0)
						tracen(" ");
					tracen(*from);
					from++;
					if (j == w - 1)
						trace();
				}
			}
		}

		template <class T, int N>
		requires(!same_as<decay_t<T>, char>)
		void trace2d(T (&a)[N], int h, int w) {
			if (!debug)
				return;
			int idx = 0;
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					if (j > 0)
						tracen(" ");
					tracen(a[idx]);
					idx++;
					if (j == w - 1)
						trace();
				}
			}
		}
	} // namespace tracer
	using namespace tracer;

	namespace random {
		class rngen {
		public:
			rngen() {
			}

			rngen(int s) {
				seed(s);
			}

			ull get_state() {
				return state;
			}

			void set_state(ull state) {
				this->state = state;
			}

			void seed(int s) {
				state = s + INCR;
				next32();
			}

			int next_int() {
				return next31();
			}

			int next_int(int mod) {
				assert(mod > 0);
				return (int) ((ull) next31() * mod >> 31);
			}

			int next_int(int min, int max) {
				return min + next_int(max - min + 1);
			}

			uint next_uint() {
				return next32();
			}

			ull next_ull() {
				return (ull) next32() << 32 | next32();
			}

			double next_float() {
				return (double) next31() / 0x80000000;
			}

			double next_float(double min, double max) {
				return min + next_float() * (max - min);
			}

			double next_normal() {
				return sqrt(-2 * log(next_float())) * cos(6.283185307179586 * next_float());
			}

			double next_normal(double mean, double sigma) {
				return mean + next_normal() * sigma;
			}

		private:
			static constexpr ull MULT = 0x8b46ad15ae59daadull;
			static constexpr ull INCR = 0xf51827be20401689ull;
			ull state = (ull) chrono::duration_cast<chrono::nanoseconds>(
			    chrono::system_clock::now().time_since_epoch())
			                .count();

			uint next32() {
				uint r = (uint) (state >> 59);
				state = state * MULT + INCR;
				state ^= state >> 18;
				uint t = (uint) (state >> 27);
				return t >> r | t << (-r & 31);
			}

			int next31() {
				return (int) (next32() & 0x7fffffff);
			}
		};

		void random_permutation(int* a, int n, rngen& rng) {
			assert(n >= 0);
			if (n == 0)
				return;
			a[0] = 0;
			for (int i = 1; i < n; i++) {
				a[i] = i;
				swap(a[i], a[rng.next_int(i + 1)]);
			}
		}

		template <class RandomAccessContainer>
		auto& random_pick(RandomAccessContainer& c, rngen& rng) {
			return c[rng.next_int(len(c))];
		}

		template <class RandomAccessContainer>
		const auto& random_pick(const RandomAccessContainer& c, rngen& rng) {
			return c[rng.next_int(len(c))];
		}

		template <class T, int N>
		T& random_pick(T (&c)[N], rngen& rng) {
			return c[rng.next_int(N)];
		}

		template <class T, int N>
		const T& random_pick(const T (&c)[N], rngen& rng) {
			return c[rng.next_int(N)];
		}
	} // namespace random
	using namespace random;

	namespace ds {
		// random access: O(1)
		// push: O(1)
		// insert: n/a
		// erase by position: O(1)
		// erase by element: n/a
		// max size: fixed
		template <class T, int N>
		class fast_vector {
		private:
			T data[N];
			int num = 0;

		public:
			using iterator = T*;
			using const_iterator = const T*;

			iterator begin() {
				return data;
			}

			iterator end() {
				return data + num;
			}

			const_iterator begin() const {
				return data;
			}

			const_iterator end() const {
				return data + num;
			}

			void push_back(T a) {
				assert(num < N);
				data[num++] = a;
			}

			template <class... Args>
			void emplace_back(Args&&... args) {
				push_back(T(forward<Args>(args)...));
			}

			void erase(iterator where) {
				assert(where >= begin() && where < end());
				*where = data[--num];
			}

			void pop_back() {
				assert(num > 0);
				num--;
			}

			T& operator[](int i) {
				assert(i >= 0 && i < num);
				return data[i];
			}

			const T& operator[](int i) const {
				assert(i >= 0 && i < num);
				return data[i];
			}

			int size() const {
				return num;
			}
		};

		// random access: O(1)
		// push: O(1)
		// insert: n/a
		// erase: n/a
		// reallocation: never
		template <class T, int UnitBits = 20>
		class increasing_vector {
		private:
			static constexpr int UNIT_SIZE = 1 << UnitBits;
			static constexpr int UNIT_MASK = UNIT_SIZE - 1;
			T** packs;
			int num_packs = 0;
			int num_total = 0;

		public:
			increasing_vector(const increasing_vector& vec) = delete;
			increasing_vector& operator=(const increasing_vector& vec) = delete;

			increasing_vector() : packs(new T*[65536]) {
			}

			~increasing_vector() {
				for (int i = 0; i < num_packs; i++) {
					delete[] packs[i];
				}
				delete[] packs;
			}

			T* next_pointer() {
				if ((num_total++ & UNIT_MASK) == 0) {
					packs[num_packs++] = new T[UNIT_SIZE];
				}
				return &(*this)[num_total - 1];
			}

			void push_back(T a) {
				*next_pointer() = a;
			}

			template <class... Args>
			void emplace_back(Args&&... args) {
				push_back(T(forward<Args>(args)...));
			}

			T& operator[](int i) {
				assert(i >= 0 && i < num_total);
				return packs[i >> UnitBits][i & UNIT_MASK];
			}

			const T& operator[](int i) const {
				assert(i >= 0 && i < num_total);
				return packs[i >> UnitBits][i & UNIT_MASK];
			}

			int size() const {
				return num_total;
			}
		};

		// random access: O(1)
		// insert: O(1)
		// erase: O(1)
		// check: O(1)
		// max value: fixed
		template <int N>
		class fast_iset {
		private:
			int data[N];
			int indices[N];
			int num = 0;

		public:
			using iterator = int*;
			using const_iterator = const int*;

			fast_iset() {
				memset(indices, -1, sizeof(indices));
			}

			iterator begin() {
				return data;
			}

			iterator end() {
				return data + num;
			}

			const_iterator begin() const {
				return data;
			}

			const_iterator end() const {
				return data + num;
			}

			bool insert(int a) {
				assert(a >= 0 && a < N);
				if (indices[a] != -1)
					return false;
				data[num] = a;
				indices[a] = num;
				num++;
				return true;
			}

			bool erase(int a) {
				assert(a >= 0 && a < N);
				int index = indices[a];
				if (index == -1)
					return false;
				assert(num > 0);
				indices[data[index] = data[--num]] = index;
				indices[a] = -1;
				return true;
			}

			void clear() {
				memset(indices, -1, sizeof(indices));
				num = 0;
			}

			bool contains(int a) const {
				return indices[a] != -1;
			}

			const int& operator[](int i) const {
				assert(i >= 0 && i < num);
				return data[i];
			}

			int size() const {
				return num;
			}

			bool empty() const {
				return num == 0;
			}
		};

		// insert: O(1)
		// get/set: O(1)
		// clear: O(1)
		// erase: n/a
		template <class T, int BucketBits = 20>
		class hash_imap {
		private:
			static constexpr int BUCKET_SIZE = 1 << BucketBits;
			static constexpr int BUCKET_MASK = BUCKET_SIZE - 1;

			ull* keys;
			T* values;
			ushort* access_time;
			ushort time = (ushort) -1;
			int num_elements = 0;
			int last_index = -1;
			ull last_key = -1;
			bool last_found = false;

		public:
			hash_imap()
			    : keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
			      access_time(new ushort[BUCKET_SIZE]) {
			}

			~hash_imap() {
				delete[] keys;
				delete[] values;
				delete[] access_time;
			}

			hash_imap(const hash_imap& map)
			    : keys(new ull[BUCKET_SIZE]), values(new T[BUCKET_SIZE]),
			      access_time(new ushort[BUCKET_SIZE]) {
				memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
				memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
				memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
				time = map.time;
				num_elements = map.num_elements;
				last_index = map.last_index;
				last_key = map.last_key;
				last_found = map.last_found;
			}

			hash_imap& operator=(const hash_imap& map) {
				if (this == &map)
					return *this;
				delete[] keys;
				delete[] values;
				delete[] access_time;
				keys = new ull[BUCKET_SIZE];
				values = new T[BUCKET_SIZE];
				access_time = new ushort[BUCKET_SIZE];
				memcpy(keys, map.keys, sizeof(ull[BUCKET_SIZE]));
				memcpy(values, map.values, sizeof(T[BUCKET_SIZE])); // can be potentially dangerous?
				memcpy(access_time, map.access_time, sizeof(ushort[BUCKET_SIZE]));
				time = map.time;
				num_elements = map.num_elements;
				last_index = map.last_index;
				last_key = map.last_key;
				last_found = map.last_found;
				return *this;
			}

			void clear() {
				num_elements = 0;
				last_found = false;
				last_index = -1;
				if (++time == 0) {
					memset(access_time, 0, sizeof(ushort[BUCKET_SIZE]));
					time = 1;
				}
			}

			bool access(ull key) {
				last_key = key;
				last_index = (int) (key & BUCKET_MASK);
				bool debug = false;
				while (true) {
					if (access_time[last_index] != time) {
						return last_found = false;
					} else if (keys[last_index] == key) {
						return last_found = true;
					}
					last_index = (last_index + 1) & BUCKET_MASK;
				}
			}

			T get() const {
				assert(last_found);
				return values[last_index];
			}

			void set(T value) {
				assert(last_index != -1);
				access_time[last_index] = time;
				keys[last_index] = last_key;
				values[last_index] = value;
				num_elements += !last_found;
				assert(("bucket size is too small", num_elements < 0.85 * BUCKET_SIZE));
			}
		};

		// a bitset, but cooler than std::bitset
		template <int Size>
		class rich_bitset {
		private:
			using word = ull;
			static_assert(has_single_bit(sizeof(word)));
			static constexpr int WORD_SHIFT = std::countr_zero(8 * sizeof(word));
			static constexpr int WORD_SIZE = 1 << WORD_SHIFT;
			static constexpr int WORD_MASK = WORD_SIZE - 1;
			static constexpr int NUM_WORDS = (Size + WORD_SIZE - 1) / WORD_SIZE;
			static constexpr int LAST_WORD = NUM_WORDS - 1;
			static constexpr word LAST_WORD_MASK =
			    (Size & WORD_MASK) == 0 ? word(-1) : (word(1) << (Size & WORD_MASK)) - 1;
#define REP_WORDS(i) for (int i = 0; i < NUM_WORDS; i++)
#define REP_INNER_WORDS(i) for (int i = 0; i < NUM_WORDS - 1; i++)
#define REP_WORDS_REV(i) for (int i = NUM_WORDS - 1; i >= 0; i--)
#define REP_INNER_WORDS_REV(i) for (int i = NUM_WORDS - 2; i >= 0; i--)

			// [LAST_WORD] [LAST_WORD - 1] [...] [1] [0]
			// <- higher bits              lower bits ->
			word data[NUM_WORDS];

			struct ref {
				rich_bitset<Size>& bs;
				const int pos;

				ref(rich_bitset<Size>& bs, int pos) : bs(bs), pos(pos) {
				}

				ref& operator=(bool val) {
					bs.set(pos, val);
					return *this;
				}

				operator bool() const {
					return bs.test(pos);
				}
			};

			void trim() {
				if constexpr ((Size & WORD_MASK) != 0) {
					data[LAST_WORD] &= LAST_WORD_MASK;
				}
			}

		public:
			rich_bitset(ull value = 0) {
				constexpr int BITS = sizeof(ull) * 8;
				for (int i = 0; i < (BITS + WORD_SIZE - 1) / WORD_SIZE; i++) {
					data[i] = value >> i * WORD_SIZE;
				}
				constexpr int OFFSET = (BITS + WORD_SIZE - 1) / WORD_SIZE;
				if constexpr (OFFSET < NUM_WORDS) {
					memset(data + OFFSET, 0, sizeof(word) * (NUM_WORDS - OFFSET));
				}
			}

			bool all() const {
				bool res = true;
				REP_INNER_WORDS(i) {
					res &= data[i] == word(-1);
				}
				res &= data[LAST_WORD] == LAST_WORD_MASK;
				return res;
			}

			bool none() const {
				bool res = true;
				REP_WORDS(i) {
					res &= data[i] == 0;
				}
				return res;
			}

			bool any() const {
				bool res = false;
				REP_WORDS(i) {
					res |= data[i] != 0;
				}
				return res;
			}

			int count() const {
				int res = 0;
				REP_WORDS(i) {
					res += popcount(data[i]);
				}
				return res;
			}

			int countr_zero() const {
				if constexpr (LAST_WORD == 0) {
					return std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
				} else {
					int res = std::countr_zero(data[0]);
					int mask = -(res == WORD_SIZE); // continue adding if -1
					for (int i = 1; i < NUM_WORDS - 1; i++) {
						int count = std::countr_zero(data[i]);
						res += count & mask;
						mask &= -(count == WORD_SIZE);
					}
					int count = std::countr_zero(word(data[LAST_WORD] | ~LAST_WORD_MASK));
					res += count & mask;
					return res;
				}
			}

			int countl_zero() const {
				constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
				int res = std::countl_zero(word(~(~data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE))));
				int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
				for (int i = NUM_WORDS - 2; i >= 0; i--) {
					int count = std::countl_zero(data[i]);
					res += count & mask;
					mask &= -(count == WORD_SIZE);
				}
				return res;
			}

			int countr_one() const {
				if constexpr (LAST_WORD == 0) {
					return std::countr_one(data[LAST_WORD]);
				} else {
					int res = std::countr_one(data[0]);
					int mask = -(res == WORD_SIZE); // continue adding if -1
					for (int i = 1; i < NUM_WORDS - 1; i++) {
						int count = std::countr_one(data[i]);
						res += count & mask;
						mask &= -(count == WORD_SIZE);
					}
					int count = std::countr_one(data[LAST_WORD]);
					res += count & mask;
					return res;
				}
			}

			int countl_one() const {
				constexpr int LAST_WORD_SIZE = popcount(LAST_WORD_MASK);
				int res = std::countl_one(word(data[LAST_WORD] << (WORD_SIZE - LAST_WORD_SIZE)));
				int mask = -(res == LAST_WORD_SIZE); // continue adding if -1
				for (int i = NUM_WORDS - 2; i >= 0; i--) {
					int count = std::countl_one(data[i]);
					res += count & mask;
					mask &= -(count == WORD_SIZE);
				}
				return res;
			}

			int size() const {
				return Size;
			}

			bool test(int pos) const {
				assert(pos >= 0 && pos < Size);
				return (data[pos >> WORD_SHIFT] >> (pos & WORD_MASK)) & 1;
			}

			uint to_uint() const {
				constexpr int BITS = sizeof(uint) * 8;
				for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
					assert(("uint overflow", data[i] == 0));
				}
				if constexpr (WORD_SIZE > BITS) {
					assert(("uint overflow", (data[0] >> BITS) == 0));
				}
				uint res = (uint) data[0];
				for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
					res |= (uint) data[i] << i * WORD_SIZE;
				}
				return res;
			}

			ull to_ull() const {
				constexpr int BITS = sizeof(ull) * 8;
				for (int i = (BITS + WORD_SIZE - 1) / WORD_SIZE; i < NUM_WORDS; i++) {
					assert(("ull overflow", data[i] == 0));
				}
				if constexpr (WORD_SIZE > BITS) {
					assert(("ull overflow", (data[0] >> BITS) == 0));
				}
				ull res = (ull) data[0];
				for (int i = 1; i < (BITS + WORD_SIZE - 1) / WORD_SIZE && i < NUM_WORDS; i++) {
					res |= (ull) data[i] << i * WORD_SIZE;
				}
				return res;
			}

			rich_bitset& set(int pos, bool val = true) {
				assert(pos >= 0 && pos < Size);
				word bit = word(1) << (pos & WORD_MASK);
				if (val) {
					data[pos >> WORD_SHIFT] |= bit;
				} else {
					data[pos >> WORD_SHIFT] &= ~bit;
				}
				return *this;
			}

			rich_bitset& reset(int pos) {
				assert(pos >= 0 && pos < Size);
				return set(pos, false);
			}

			rich_bitset& flip(int pos) {
				assert(pos >= 0 && pos < Size);
				word bit = word(1) << (pos & WORD_MASK);
				data[pos >> WORD_SHIFT] ^= bit;
				return *this;
			}

			rich_bitset& set() {
				clear_with(data, -1);
				trim();
				return *this;
			}

			rich_bitset& reset() {
				clear_with(data, 0);
				return *this;
			}

			rich_bitset& flip() {
				REP_INNER_WORDS(i) {
					data[i] ^= word(-1);
				}
				data[LAST_WORD] ^= LAST_WORD_MASK;
				return *this;
			}

			rich_bitset& operator&=(const rich_bitset& a) {
				REP_WORDS(i) {
					data[i] &= a.data[i];
				}
				return *this;
			}

			rich_bitset& operator|=(const rich_bitset& a) {
				REP_WORDS(i) {
					data[i] |= a.data[i];
				}
				return *this;
			}

			rich_bitset& operator^=(const rich_bitset& a) {
				REP_WORDS(i) {
					data[i] ^= a.data[i];
				}
				return *this;
			}

			rich_bitset& operator<<=(int amount) {
				assert(amount >= 0 && amount < Size);
				int nw = amount >> WORD_SHIFT;
				if (nw > 0) {
					REP_WORDS_REV(i) {
						data[i] = i - nw < 0 ? 0 : data[i - nw];
					}
				}
				int nb = amount & WORD_MASK;
				if (nb) {
					for (int i = NUM_WORDS - 1; i > 0; i--) {
						data[i] = data[i] << nb | data[i - 1] >> (WORD_SIZE - nb);
					}
					data[0] <<= nb;
				}
				trim();
				return *this;
			}

			rich_bitset& operator>>=(int amount) {
				assert(amount >= 0 && amount < Size);
				int nw = amount >> WORD_SHIFT;
				if (nw > 0) {
					REP_WORDS(i) {
						data[i] = i + nw >= NUM_WORDS ? 0 : data[i + nw];
					}
				}
				int nb = amount & WORD_MASK;
				if (nb) {
					REP_INNER_WORDS(i) {
						data[i] = data[i] >> nb | data[i + 1] << (WORD_SIZE - nb);
					}
					data[LAST_WORD] >>= nb;
				}
				return *this;
			}

			rich_bitset& operator+=(const rich_bitset& a) {
				word carry = 0;
				REP_WORDS(i) {
					word l = data[i];
					word r = a.data[i];
					word sum = l + r;
					data[i] = sum + carry;
					carry = (sum < l) | (data[i] < sum);
				}
				trim();
				return *this;
			}

			rich_bitset& operator-=(const rich_bitset& a) {
				word carry = 1;
				REP_WORDS(i) {
					word l = data[i];
					word r = ~a.data[i];
					word sum = l + r;
					data[i] = sum + carry;
					carry = (sum < l) | (data[i] < sum);
				}
				trim();
				return *this;
			}

			rich_bitset& operator++() {
				word carry = 1;
				REP_WORDS(i) {
					word l = data[i];
					data[i] = l + carry;
					carry = (data[i] < l);
				}
				trim();
				return *this;
			}

			rich_bitset operator++(int) {
				rich_bitset res = *this;
				operator++();
				return res;
			}

			rich_bitset& operator--() {
				word carry = 0;
				REP_WORDS(i) {
					word l = data[i];
					data[i] = l - 1 + carry;
					carry = (l | carry) != 0;
				}
				trim();
				return *this;
			}

			rich_bitset operator--(int) {
				rich_bitset res = *this;
				operator--();
				return res;
			}

			rich_bitset operator~() const {
				rich_bitset res = *this;
				res.flip();
				return res;
			}

			friend rich_bitset operator&(const rich_bitset& a, const rich_bitset& b) {
				rich_bitset res = a;
				res &= b;
				return res;
			}

			friend rich_bitset operator|(const rich_bitset& a, const rich_bitset& b) {
				rich_bitset res = a;
				res |= b;
				return res;
			}

			friend rich_bitset operator^(const rich_bitset& a, const rich_bitset& b) {
				rich_bitset res = a;
				res ^= b;
				return res;
			}

			friend rich_bitset operator<<(const rich_bitset& a, int amount) {
				rich_bitset res = a;
				res <<= amount;
				return res;
			}

			friend rich_bitset operator>>(const rich_bitset& a, int amount) {
				rich_bitset res = a;
				res >>= amount;
				return res;
			}

			friend rich_bitset operator+(const rich_bitset& a, const rich_bitset& b) {
				rich_bitset res = a;
				res += b;
				return res;
			}

			friend rich_bitset operator-(const rich_bitset& a, const rich_bitset& b) {
				rich_bitset res = a;
				res -= b;
				return res;
			}

			friend bool operator==(const rich_bitset& a, const rich_bitset& b) {
				return memcmp(a.data, b.data, sizeof(a.data)) == 0;
			}

			friend bool operator!=(const rich_bitset& a, const rich_bitset& b) {
				return memcmp(a.data, b.data, sizeof(a.data)) != 0;
			}

			friend int operator<=>(const rich_bitset& a, const rich_bitset& b) {
				REP_WORDS_REV(i) {
					if (a.data[i] != b.data[i])
						return a.data[i] < b.data[i] ? -1 : 1;
				}
				return 0;
			}

			ref operator[](int pos) {
				return {*this, pos};
			}

			bool operator[](int pos) const {
				return test(pos);
			}

			string str() const {
				ostringstream oss;
				oss << *this;
				return oss.str();
			}

			friend ostream& operator<<(ostream& out, const rich_bitset& bs) {
				for (int i = Size - 1; i >= 0; i--) {
					out << (bs.test(i) ? '1' : '0');
				}
				return out;
			}
#undef REP_WORDS
#undef REP_INNER_WORDS
#undef REP_WORDS_REV
#undef REP_INNER_WORDS_REV
		};

		template <class T>
		class easy_stack {
		private:
			vector<T> data;

		public:
			auto begin() {
				return data.begin();
			}

			auto end() {
				return data.end();
			}

			auto begin() const {
				return data.begin();
			}

			auto end() const {
				return data.end();
			}

			void push_back(T a) {
				data.push_back(a);
			}

			template <class... Args>
			void emplace(Args&&... args) {
				data.emplace_back(forward<Args>(args)...);
			}

			T pop_back() {
				T res = data.back();
				data.pop_back();
				return res;
			}

			int size() const {
				return (int) data.size();
			}

			bool empty() const {
				return data.empty();
			}
		};

		template <int N>
		int len(const fast_iset<N>& a) {
			return a.size();
		}

		template <class T, int N>
		int len(const fast_vector<T, N>& a) {
			return a.size();
		}

		template <class T, int BucketBits>
		int len(const hash_imap<T, BucketBits>& a) {
			return a.size();
		}

		template <class T>
		int len(const easy_stack<T>& a) {
			return a.size();
		}
	} // namespace ds
	using namespace ds;

	namespace beam_search {
		// (state) -> score
		template <class T, class State, class Score>
		concept get_score =
		    totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;

		// (state, move) -> void
		template <class T, class State, class MoveId>
		concept apply_move =
		    invocable<T, State&, MoveId> && same_as<invoke_result_t<T, State&, MoveId>, void>;

		// (state) -> void
		template <class T, class State>
		concept undo_move = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;

		// (state) -> void
		// see also: add_candidate
		template <class T, class State>
		concept enumerate_candidates = invocable<T, State&> && same_as<invoke_result_t<T, State&>, void>;

		// (turn) -> void
		// see also: candidates_to_filter
		template <class T>
		concept filter_candidates = invocable<T, int> && same_as<invoke_result_t<T, int>, void>;

		template <class State, totally_ordered Score, class MoveId, MoveId UnusedMoveId, class CandidateData,
		    class Direction = greater<Score>, int HashBucketBits = 20>
		class beam_search {
		private:
			struct candidate {
				int index; // index in orig_candidates
				int parent;
				MoveId move_id;
				CandidateData data;
				ull hash;
			};
			struct orig_candidate {
				int parent;
				MoveId move_id;
				bool chosen;
			};

			Direction dir = {};
			int current_parent = 0;
			hash_imap<int, HashBucketBits> best_indices;
			bool enumerating = false;
			bool filtering = false;
			vector<candidate> candidates;
			vector<orig_candidate> orig_candidates;

			void clear_candidates() {
				candidates.clear();
				orig_candidates.clear();
			}

		public:
			Score best_score = 0;
			int max_turn = -1;

			beam_search() {
			}

			beam_search(Direction dir) : dir(dir) {
			}

			void add_candidate(MoveId move_id, CandidateData data, ull hash) {
				assert(("not enumerating now", enumerating));
				candidates.emplace_back((int) candidates.size(), current_parent, move_id, data, hash);
				orig_candidates.emplace_back(current_parent, move_id);
			}

			vector<candidate>& candidates_to_filter() {
				assert(("not filtering now", filtering));
				return candidates;
			}

			// CAUTION: not stable
			template <predicate<candidate&, candidate&> CandidateDirection>
			void remove_duplicates(CandidateDirection candidate_direction) {
				assert(("not filtering now", filtering));
				best_indices.clear();
				int n = (int) candidates.size();
				for (int i = 0; i < n; i++) {
					candidate& cand = candidates[i];
					if (best_indices.access(cand.hash)) {
						int j = best_indices.get();
						candidate& cand2 = candidates[j];
						if (candidate_direction(cand, cand2)) {
							swap(candidates[i], candidates[j]);
						}
						swap(candidates[i], candidates[--n]);
						i--;
					} else {
						best_indices.set(i);
					}
				}
				candidates.resize(n);
			}

			template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
			    enumerate_candidates<State> EnumerateCandidates, filter_candidates FilterCandidates>
			vector<MoveId> run(const State& initial_state, GetScore get_score, ApplyMove apply_move,
			    EnumerateCandidates enumerate_candidates, FilterCandidates filter_candidates) {
				struct node {
					State state;
					int history_index;
				};
				struct history {
					MoveId move_id;
					int parent;
				};
				vector<node> src;
				vector<node> dst;
				increasing_vector<history> hs;
				int turn = 0;

				// set initial state
				src.emplace_back(initial_state, -1);

				while (true) {
					int num_states = (int) src.size();

					clear_candidates();
					if (max_turn == -1 || turn < max_turn) {
						// enumerate candidates
						enumerating = true;
						for (int i = 0; i < num_states; i++) {
							current_parent = i;
							enumerate_candidates(src[i].state);
						}
						enumerating = false;

						// filer candiadtes
						filtering = true;
						filter_candidates(turn);
						filtering = false;
					}

					// check if finished
					if (candidates.empty()) {
						assert(("no states at the end", num_states > 0));

						// pick the best state
						best_score = get_score(src[0].state);
						int best_index = 0;
						for (int i = 1; i < num_states; i++) {
							Score score = get_score(src[i].state);
							if (dir(score, best_score)) {
								best_score = score;
								best_index = i;
							}
						}

						// restore moves
						vector<MoveId> res;
						int history_top = src[best_index].history_index;
						while (history_top != -1) {
							history& h = hs[history_top];
							res.push_back(h.move_id);
							history_top = h.parent;
						}
						reverse(res.begin(), res.end());
						return res;
					}

					// compute next states
					dst.clear();
					for (const auto& cand : candidates) {
						const auto& src_node = src[cand.parent];
						dst.emplace_back(src_node.state, hs.size());
						apply_move(dst.back().state, cand.move_id);
						hs.emplace_back(cand.move_id, src_node.history_index);
					}
					src.swap(dst);
					turn++;
				}
			}

			template <get_score<State, Score> GetScore, apply_move<State, MoveId> ApplyMove,
			    undo_move<State> UndoMove, enumerate_candidates<State> EnumerateCandidates,
			    filter_candidates FilterCandidates>
			vector<MoveId> run_tree(const State& initial_state, GetScore get_score, ApplyMove apply_move,
			    UndoMove undo_move, EnumerateCandidates enumerate_candidates,
			    FilterCandidates filter_candidates) {
				constexpr MoveId UNDO = UnusedMoveId;
				struct tour {
					vector<MoveId> src;
					vector<MoveId> dst;

					void move(const MoveId& move_id) {
						dst.push_back(move_id);
					}

					int position() {
						return (int) dst.size();
					}

					void swap() {
						src.swap(dst);
						dst.clear();
					}
				} tour;
				vector<MoveId> global_path;
				vector<MoveId> path;
				vector<orig_candidate> leaves;
				State st = initial_state;
				int turn = 0;
				int level = 0;
				int next_start_pos = 0;

				auto global_move = [&](const MoveId& move_id) {
					apply_move(st, move_id);
					global_path.push_back(move_id);
					level++;
				};

				auto global_undo = [&]() {
					undo_move(st);
					global_path.pop_back();
					level--;
				};

				while (true) {
					bool has_next_turn = max_turn == -1 || turn < max_turn;

					// compute the next tour
					int pos = next_start_pos;
					int prev_root_level = level;
					int next_root_level = numeric_limits<int>::max();
					orig_candidate best_leaf = {-1, MoveId{}, false};
					enumerating = true;
					clear_candidates();
					if (turn == 0) {
						best_score = get_score(st);
						best_leaf.chosen = true;
						if (has_next_turn) {
							current_parent = tour.position();
							enumerate_candidates(st);
						}
					} else {
						for (const orig_candidate& leaf : leaves) {
							int parent_pos = leaf.parent;

							// visit the parent of the leaf node
							if (pos < parent_pos) {
								// visit the LCA
								path.clear();
								do {
									auto move = tour.src[pos++];
									if (move == UNDO) {
										if (path.empty()) {
											global_undo();
											tour.move(UNDO);
											next_root_level = min(next_root_level, level);
										} else {
											path.pop_back();
										}
									} else {
										path.push_back(move);
									}
								} while (pos < parent_pos);

								// go directly to the parent
								for (auto move : path) {
									global_move(move);
									tour.move(move);
								}
							} // now we are at the parent of the leaf node

							// visit the leaf node
							apply_move(st, leaf.move_id);
							tour.move(leaf.move_id);

							Score score = get_score(st);
							if (!best_leaf.chosen || dir(score, best_score)) {
								best_score = score;
								best_leaf = leaf;
							}
							if (has_next_turn) {
								current_parent = tour.position();
								enumerate_candidates(st);
							}

							// leave the leaf node
							undo_move(st);
							tour.move(UNDO);
						}
					}
					next_root_level = min(next_root_level, level);
					enumerating = false;

					filtering = true;
					filter_candidates(turn);
					filtering = false;

					if (candidates.empty()) {
						assert(best_leaf.chosen);
						// undo to the root level
						while (level > prev_root_level) {
							global_undo();
						}
						// visit the best leaf
						pos = next_start_pos;
						while (pos < best_leaf.parent) {
							auto move = tour.src[pos++];
							if (move == UNDO) {
								global_undo();
							} else {
								global_move(move);
							}
						}
						if (best_leaf.parent != -1) {
							global_move(best_leaf.move_id);
						}
						return global_path;
					}

					// finalize the next tour
					tour.swap();
					turn++;

					// collect the next leaf nodes, in the original order
					leaves.clear();
					for (const candidate& cand : candidates) {
						orig_candidates[cand.index].chosen = true;
					}
					for (const orig_candidate& cand : orig_candidates) {
						if (!cand.chosen)
							continue;
						leaves.push_back(cand);
					}

					// undo to the next root level
					while (level > next_root_level) {
						global_undo();
					}

					// adjust the next starting position
					next_start_pos = next_root_level - prev_root_level;
				}
			}
		};

		class beam_width_manager {
		private:
			double prev_time = 0;
			double moving_average_time = 0;
			vector<double> progress_history;
			vector<double> time_history;
			vector<int> width_history;
			int last_width = 0;
			int count = 0;

		public:
			int window_size = 50;
			int default_width;

			beam_width_manager(int default_width) : default_width(default_width) {
			}

			int next(double progress, double time, double time_limit) {
				progress_history.push_back(progress);
				time_history.push_back(time);
				width_history.push_back(last_width);
				count++;
				if (count <= window_size) {
					return last_width = default_width;
				}
				int i1 = count - 1 - window_size;
				int i2 = count - 1;
				double progress_sum = progress_history[i2] - progress_history[i1];
				double time_sum = time_history[i2] - time_history[i1];
				if (progress_sum == 0 || time_sum == 0) {
					// window size is too small
					window_size *= 2;
					return last_width = default_width;
				}
				int width_sum = 0;
				for (int i = i1 + 1; i <= i2; i++) {
					width_sum += width_history[i];
				}
				double progress_per_turn = progress_sum / window_size;
				double time_per_width = time_sum / width_sum;
				double left_time = time_limit - time;
				double left_progress = 1 - progress;
				if (left_time <= 0 || left_progress <= 0)
					return 1;
				double left_turn = left_progress / progress_per_turn;
				double left_time_per_turn = left_time / left_turn;
				double left_width_per_turn = left_time_per_turn / time_per_width;
				return last_width = round(left_width_per_turn);
			}

			void report(int actual_last_width) {
				last_width = actual_last_width;
			}
		};
	} // namespace beam_search

	namespace simulated_annealing {
		// (state) -> score
		template <class T, class State, class Score>
		concept get_score =
		    totally_ordered<Score> && invocable<T, State&> && same_as<invoke_result_t<T, State&>, Score>;

		// (iter) -> progress
		template <class T>
		concept update_progress = invocable<T, int> && same_as<invoke_result_t<T, int>, double>;

		// (state, tolerance) -> accepted
		template <class T, class State>
		concept try_transition =
		    invocable<T, State&, double> && same_as<invoke_result_t<T, State&, double>, bool>;

		template <class State, totally_ordered Score, class Direction = greater<Score>>
		class simulated_annealing {
		private:
			Direction dir = {};

		public:
			int clock_interval = 10;
			double t_from = 100;
			double t_to = 0.01;
			double progress = 0;
			int num_iterations = 0;
			int num_acceptances = 0;
			int num_rejections = 0;
			bool use_linear_temp = false;
			Score best_score = 0;

			simulated_annealing() {
			}

			simulated_annealing(Direction dir) : dir(dir) {
			}

			template <get_score<State, Score> GetScore, update_progress UpdateProgress,
			    try_transition<State> TryTransition>
			State run(const State& initial_state, rngen& rng, GetScore get_score,
			    UpdateProgress update_progress, TryTransition try_transition,
			    function<void(State&, Score, int, double)> best_updated = nullptr) {
				State state = initial_state;
				Score score = get_score(state);
				State best_state = state;
				best_score = score;

				num_iterations = 0;
				num_acceptances = 0;
				num_rejections = 0;
				int interval = clock_interval;
				progress = 0;
				double t = t_from;
				while (true) {
					if (--interval <= 0) {
						progress = update_progress(num_iterations);
						if (progress >= 1)
							break;
						t = use_linear_temp ? lerp(t_from, t_to, progress)
						                    : exp_interp(t_from, t_to, progress);
						interval = clock_interval;
					}
					double tolerance = t * -log(rng.next_float());
					if (try_transition(state, tolerance)) {
						num_acceptances++;
						score = get_score(state);
						if (dir(score, best_score)) {
							best_state = state;
							best_score = score;
							if (best_updated) {
								best_updated(state, score, num_iterations, t);
							}
						}
					} else {
						num_rejections++;
					}
					num_iterations++;
				}
				return best_state;
			}
		};
	} // namespace simulated_annealing

	namespace dijkstra {
		// (vertex) -> index
		template <class T, class Vertex>
		concept get_index = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, int>;

		// (vertex) -> is_goal
		template <class T, class Vertex>
		concept is_goal = invocable<T, Vertex> && same_as<invoke_result_t<T, Vertex>, bool>;

		// (vertex, distance) -> void
		template <class T, class Vertex, class Weight>
		concept visit_adjacent_vertices =
		    invocable<T, Vertex, Weight> && same_as<invoke_result_t<T, Vertex, Weight>, void>;

		template <class Vertex, class Weight, Weight Infinity, int MaxVertexIndex>
		requires(integral<Weight> || floating_point<Weight>)
		class dijkstra {
		private:
			using vw = pair<Vertex, Weight>;
			static constexpr int VERTEX_ARRAY_SIZE = MaxVertexIndex + 1;
			vector<vw> toVisit;
			bool visiting = false;

		public:
			array<bool, VERTEX_ARRAY_SIZE> visited;
			array<Weight, VERTEX_ARRAY_SIZE> distance;
			array<optional<Vertex>, VERTEX_ARRAY_SIZE> previous;

			dijkstra() {
			}

			template <get_index<Vertex> GetIndex, is_goal<Vertex> IsGoal,
			    visit_adjacent_vertices<Vertex, Weight> VisitAdjacentVertices>
			void run(const vector<Vertex>& starts, GetIndex get_index, IsGoal is_goal,
			    VisitAdjacentVertices visit_adjacent_vertices) {
				auto comp = [](vw& a, vw& b) {
					return a.second > b.second;
				};

				visited.fill(false);
				previous.fill(nullopt);
				distance.fill(Infinity);
				priority_queue<vw, vector<vw>, decltype(comp)> q(comp);
				for (auto& st : starts) {
					distance[get_index(st)] = Weight(0);
					q.emplace(st, Weight(0));
				}

				int loop = 0;
				while (!q.empty()) {
					if (++loop % 10 == 0)
						trace(loop, " ", timer::timer());
					auto [from, dist] = q.top();
					q.pop();
					int fromi = get_index(from);
					if (visited[fromi])
						continue;
					visited[fromi] = true;
					if (is_goal(from)) {
						return;
					}

					visiting = true;
					toVisit.clear();
					visit_adjacent_vertices(from, dist);
					visiting = false;

					for (vw& pair : toVisit) {
						Vertex to = pair.first;
						int toi = get_index(to);
						Weight new_dist = pair.second;
						if (new_dist < distance[toi]) {
							distance[toi] = new_dist;
							previous[toi] = from;
							q.emplace(to, new_dist);
						}
					}
				}
			}

			void visit(Vertex vertex, Weight total_distance) {
				assert(("not visiting now", visiting));
				toVisit.emplace_back(vertex, total_distance);
			}

			template <get_index<Vertex> GetIndex>
			vector<Vertex> restore_path(Vertex goal, GetIndex get_index) {
				assert(("goal not reached", visited[get_index(goal)]));
				vector<Vertex> res;
				Vertex v = goal;
				while (true) {
					res.push_back(v);
					if (!previous[get_index(v)])
						break;
					v = previous[get_index(v)].value();
				}
				reverse(res.begin(), res.end());
				return res;
			}
		};
	}; // namespace dijkstra

	namespace file {
		string pad4(int n) {
			return (n < 0 || n >= 1000 ? "" : n < 10 ? "000" : n < 100 ? "00" : "0") + tos(n);
		}

		string input_file_name(int seed) {
			return "in/" + pad4(seed) + ".txt";
		}

		string output_file_name(int seed) {
			return "out/" + pad4(seed) + ".txt";
		}

		string movie_file_name(int seed) {
			return "mov/" + pad4(seed) + ".smv";
		}

		bool write_text(string fileName, string text, bool append = false) {
			ofstream fout;
			fout.open(fileName, append ? ios::out | ios::app : ios::out);
			if (!fout)
				return false;
			fout << text;
			fout.close();
			return true;
		}

		pair<string, bool> read_text(string fileName) {
			ifstream fin;
			fin.open(fileName, ios::in);
			if (!fin)
				return make_pair("", false);
			string res;
			string line;
			while (getline(fin, line)) {
				res += line;
				res += "\n";
			}
			return make_pair(res, true);
		}

		void write_text_assert(string fileName, string text, bool append = false) {
			auto res = write_text(fileName, text, append);
			assert(res);
		}

		string read_text_assert(string fileName) {
			auto res = read_text(fileName);
			assert(res.second);
			return res.first;
		}
	} // namespace file
} // namespace shr
using namespace shr::basic;
using namespace shr::ds;
using namespace shr::beam_search;
using namespace shr::simulated_annealing;
using namespace shr::dijkstra;
using namespace shr::random;
using namespace shr::timer;
using namespace shr::tracer;
using namespace shr::file;

//
// --- macros ---
//

#define rep(i, from, until) for (int i = (from); i < (until); i++)
#define repr(i, from, until) for (int i = (until) -1; i >= (from); i--)
#define rep0(i, until) rep(i, 0, until)
#define rep0r(i, until) repr(i, 0, until)

//
// --- movie lib ---
//

class movie {
private:
	bool is_open = false;
	string file_name;
	ofstream out;

#ifdef ONLINE_JUDGE
	void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
	}
#else
	void write_instruction(const string& it, const vector<double>& argf, const vector<string>& args) {
		assert(("file name is not set", file_name != ""));
		if (!is_open) {
			is_open = true;
			out = ofstream(file_name, ios_base::out | ios_base::binary);
			out.write("smv", 3);
		}
		write_string(it);
		for (double f : argf) {
			write_float(f);
		}
		for (auto& s : args) {
			write_string(s);
		}
		if (it == "n") {
			out.flush(); // flush at the end of each frame
		}
	}

	void write_float(double a) {
		float f = (float) a;
		out.write((char*) &f, 4);
	}

	void write_string(const string& str) {
		out.write(str.c_str(), str.length() + 1);
	}
#endif

public:
	static constexpr int LEFT = 0;
	static constexpr int CENTER = 1;
	static constexpr int RIGHT = 2;

	movie() {
	}

	void set_file(string file) {
		assert(!is_open);
		file_name = file;
	}

	void close_file() {
		if (!is_open)
			return;
		is_open = false;
		out.close();
	}

	void fill(double rgb, double a = 1.0) {
		fill(rgb, rgb, rgb, a);
	}

	void fill(double r, double g, double b, double a = 1.0) {
		write_instruction("f", {r, g, b, a}, {});
	}

	void stroke(double rgb, double a = 1.0) {
		stroke(rgb, rgb, rgb, a);
	}

	void stroke(double r, double g, double b, double a = 1.0) {
		write_instruction("s", {r, g, b, a}, {});
	}

	void no_fill() {
		write_instruction("nf", {}, {});
	}

	void no_stroke() {
		write_instruction("ns", {}, {});
	}

	void comment(string text) {
		write_instruction("cm", {}, {text});
	}

	void tooltip(string text) {
		write_instruction("tt", {}, {text});
	}

	void no_tooltip() {
		write_instruction("nt", {}, {});
	}

	void stroke_weight(double weight) {
		write_instruction("sw", {weight}, {});
	}

	void text_size(double size) {
		write_instruction("ts", {size}, {});
	}

	void text_align(int align) {
		write_instruction("ta", {(double) align}, {});
	}

	void rect(double x, double y, double w, double h) {
		write_instruction("r", {x, y, w, h}, {});
	}

	void circle(double x, double y, double r) {
		write_instruction("c", {x, y, r}, {});
	}

	void ellipse(double x, double y, double rx, double ry) {
		write_instruction("e", {x, y, rx, ry}, {});
	}

	void line(double x1, double y1, double x2, double y2) {
		write_instruction("l", {x1, y1, x2, y2}, {});
	}

	void text(string str, double x, double y) {
		write_instruction("t", {x, y}, {str});
	}

	void transform(double e00, double e01, double e10, double e11) {
		write_instruction("tf", {e00, e01, e10, e11}, {});
	}

	void translate(double tx, double ty) {
		write_instruction("tr", {tx, ty}, {});
	}

	void rotate(double ang) {
		write_instruction("ro", {ang}, {});
	}

	void scale(double s) {
		scale(s, s);
	}

	void scale(double sx, double sy) {
		write_instruction("sc", {sx, sy}, {});
	}

	void push() {
		write_instruction("pu", {}, {});
	}

	void pop() {
		write_instruction("po", {}, {});
	}

	void end_frame() {
		write_instruction("n", {}, {});
	}

	void target(string name) {
		write_instruction("tg", {}, {name});
	}
};

movie mov;

// --------------------------------------------------
// main part
// --------------------------------------------------

bool isLocal = false;
bool render = false;

// define N and stuff here
constexpr int N = 45;
constexpr int N2 = N * 2;
constexpr int M = 50;
#define repn(i) rep0(i, N)
#define repm(i) rep0(i, M)

class Problem {
private:
public:
	array<array<ll, 2>, N> vs;

	void load(istream& in) {
		// read input here
		int n;
		in >> n;
		assert(n == N);
		repn(i) {
			in >> vs[i][0] >> vs[i][1];
		}
	}
};

struct SolverResult {
	ll score = 0;
};

class Solver {
public:
	int seed;
	rngen rng;
	SolverResult result;
	Problem p;

	Solver() : rng() {
	}

	void load(istream& in, int seed = -1) {
		p.load(in);
		mov.set_file(movie_file_name(seed));
		init();
	}

	void load(int seed) {
		this->seed = seed;
		istringstream in(read_text_assert(input_file_name(seed)));
		isLocal = true;
		load(in, seed);
	}

	void solve() {
		if (isLocal) {
			ostringstream out;
			solveMain(out);
			mov.close_file();
			write_text(output_file_name(seed), out.str());
		} else {
			solveMain(cout);
		}
	}

private:
	void init() {
	}

	void solveMain(ostream& out) { // write answer to out
		constexpr ll TARGET = (ll) (5e17);
		array<ll, N2> cs;
		repn(i) {
			cs[i << 1] = p.vs[i][0];
			cs[i << 1 | 1] = p.vs[i][1];
		}
		auto op = [&](int i, int j) {
			return make_pair(cs[i << 1] + cs[j << 1] >> 1, cs[i << 1 | 1] + cs[j << 1 | 1] >> 1);
		};
		auto getScore = [&](ll a, ll b) {
			return 20000000 - 100000 * log10(max(abs(a - TARGET), abs(b - TARGET)) + 1);
		};
		// vector<pii> ops;
		// repm(iter) {
		// 	double score = getScore(cs[0], cs[1]);
		// 	double bestScore = score;
		// 	int bestI = -1;
		// 	rep(i, 1, N) {
		// 		auto [a, b] = op(0, i);
		// 		double score = getScore(a, b);
		// 		if (update_max(score, bestScore)) {
		// 			bestI = i;
		// 		}
		// 	}
		// 	if (bestI == -1)
		// 		break;
		// 	auto [a, b] = op(0, bestI);
		// 	cs[0] = a;
		// 	cs[1] = b;
		// 	cs[bestI << 1 | 0] = a;
		// 	cs[bestI << 1 | 1] = b;
		// 	trace(bestI, " ", log10(max(abs(a - TARGET), abs(b - TARGET))), " ", bestScore, " ", iter);
		// }
		// out << len(ops) << endl;
		// for (auto [a, b] : ops) {
		// 	out << a + 1 << " " << b + 1 << endl;
		// }
		struct State {
			ll cs[N2];
			ll hist[M * 4];
			int ihist[M * 2];
			int turn = 0;
		};
		auto diff = [&](ll cs[N2], int i) {
			return max(abs(cs[i << 1] - TARGET), abs(cs[i << 1 | 1] - TARGET));
		};
		auto apply = [&](State& st, short move) {
			int i = move >> 8 & 0xff;
			int j = move & 0xff;
			ll ai = st.cs[i << 1];
			ll bi = st.cs[i << 1 | 1];
			ll aj = st.cs[j << 1];
			ll bj = st.cs[j << 1 | 1];
			ll a = ai + aj >> 1;
			ll b = bi + bj >> 1;
			st.hist[st.turn << 2 | 0] = ai;
			st.hist[st.turn << 2 | 1] = bi;
			st.hist[st.turn << 2 | 2] = aj;
			st.hist[st.turn << 2 | 3] = bj;
			st.ihist[st.turn << 1 | 0] = i;
			st.ihist[st.turn << 1 | 1] = j;
			st.cs[i << 1] = a;
			st.cs[i << 1 | 1] = b;
			st.cs[j << 1] = a;
			st.cs[j << 1 | 1] = b;
			st.turn++;
		};
		auto undo = [&](State& st) {
			st.turn--;
			int i = st.ihist[st.turn << 1 | 0];
			int j = st.ihist[st.turn << 1 | 1];
			ll ai = st.hist[st.turn << 2 | 0];
			ll bi = st.hist[st.turn << 2 | 1];
			ll aj = st.hist[st.turn << 2 | 2];
			ll bj = st.hist[st.turn << 2 | 3];
			ll a = st.cs[i << 1];
			ll b = st.cs[i << 1 | 1];
			st.cs[i << 1] = ai;
			st.cs[i << 1 | 1] = bi;
			st.cs[j << 1] = aj;
			st.cs[j << 1 | 1] = bj;
		};
		beam_search<State, ll, short, -1, ll, less<ll>, 24> bs;
		bs.max_turn = M;
		State st;
		repn(i) {
			st.cs[i << 1] = cs[i << 1];
			st.cs[i << 1 | 1] = cs[i << 1 | 1];
		}
		auto res = bs.run_tree(
		    st,
		    [&](State& st) {
			    return max(abs(st.cs[0] - TARGET), abs(st.cs[1] - TARGET));
		    },
		    apply, undo,
		    [&](State& st) {
			    auto getScore = [&]() {
				    ll res = diff(st.cs, 0);
				    res += diff(st.cs, 1) >> 1;
				    res += diff(st.cs, 2) >> 2;
				    res += diff(st.cs, 3) >> 3;
				    res += diff(st.cs, 4) >> 4;
				    res += diff(st.cs, 5) >> 5;
				    return res;
			    };
			    ll cscore = getScore();
			    bs.add_candidate(0, cscore, 0);
			    rep0(i, N - 1) {
				    rep(j, i + 1, N) {
					    apply(st, i << 8 | j);
					    ll score = getScore();
					    undo(st);
					    bs.add_candidate(i << 8 | j, score, 0);
				    }
			    }
		    },
		    [&](int turn) {
			    auto& cands = bs.candidates_to_filter();
			    int bw = 300;
			    auto better = [&](auto& a, auto& b) {
				    return a.data < b.data;
			    };
			    trace(turn, " ", len(cands));
			    static hash_imap<int> counts;
			    counts.clear();
			    if (len(cands) > bw) {
				    ranges::sort(cands, better);
				    erase_if(cands, [&](auto& a) {
					    if (counts.access(a.parent)) {
						    int num = counts.get();
						    if (num > 10)
							    return true;
						    counts.set(num + 1);
					    } else {
						    counts.set(1);
					    }
					    return false;
				    });
				    if (len(cands) > bw) {
					    nth_element(cands.begin(), cands.begin() + bw, cands.end(), better);
					    cands.resize(bw);
				    }
			    }
		    });
		erase_if(res, [&](auto move) {
			return move == 0;
		});
		trace(round(2e6 - 1e5 * log10(bs.best_score)) * 50);
		out << len(res) << endl;
		for (short move : res) {
			out << (move >> 8 & 0xff) + 1 << " " << (move & 0xff) + 1 << endl;
			// trace(move >> 8 & 0xff, " ", move & 0xff);
		}
	}
};

int main() {
#if 0 || ONLINE_JUDGE
	isLocal = false;
	render = false;
	timer(true);
	Solver sol;
	sol.load(cin);
	sol.solve();
#elif 0
	compareScores("cut", "nocut");
	// compareScores("new6", "new10");
#elif 0
	// for local and remote testers
	debug = false;
	render = false;
	int seed;
	cin >> seed;
	cin >> time_scale;

	timer(true);
	Solver sol;
	sol.load(seed);
	cout << sol.result.score << endl;
#elif 1
	// single-threaded test, handy but slow
	time_scale = 1.0;
	int num = 50;
	int from = 0;
	int stride = 1;
	int single = 0;
	debug = true;
	render = false;

	struct TestCase {
		int seed;
		int time;
		ll score;
	};
	vector<TestCase> cases;

	vector<int> seedList = {};
	if (seedList.empty()) {
		if (single == -1) {
			rep0(t, num) {
				seedList.push_back(from + t * stride);
			}
		} else {
			seedList.push_back(single);
		}
	}

	bool doTrace = debug;
	debug = true;
	for (int seed : seedList) {
		timer(true);
		trace("------------ SOLVING SEED ", seed, " ------------");
		debug = doTrace;
		Solver s;
		s.load(seed);
		s.solve();
		debug = true;
		int time = timer();
		trace("score: ", s.result.score, " (time ", time, " ms)\n");
		if (s.result.score != -1)
			cases.emplace_back(seed, time, s.result.score);
	}

	auto print = [&](const TestCase& c) {
		int seed = c.seed;
		string space = seed < 10 ? "   " : seed < 100 ? "  " : seed < 1000 ? " " : "";
		trace("  seed ", space, seed, ": ", c.score, " (time ", c.time, " ms)");
	};

	if (len(cases) > 1) {
		trace("------------ summary ------------");

		trace("sort by seed:");
		sort(cases.begin(), cases.end(), [&](auto a, auto b) {
			return a.seed < b.seed;
		});
		for (auto& c : cases)
			print(c);

		trace("sort by score:");
		sort(cases.begin(), cases.end(), [&](auto a, auto b) {
			return a.score > b.score;
		});
		for (auto& c : cases)
			print(c);

		ll scoreSum = 0;
		double logScoreSum = 0;
		for (auto& c : cases) {
			scoreSum += c.score;
			logScoreSum += log(c.score);
		}
		double invDenom = 1.0 / len(cases);
		trace("total score: ", scoreSum, ", mean: ", (ll) (scoreSum * invDenom * 100 + 0.5) / 100.0,
		    ", mean(log2): ", (ll) (logScoreSum * invDenom * 1000 + 0.5) / 1000.0);
	}
#endif
}
yukicoder

結果

テストケース

ソースコード
