#723842 (C++17) No.5004 Room Assignment

提出ソース
結果

問題	No.5004 Room Assignment
ユーザー	bowwowforeach
提出日時	2021-12-12 23:17:25
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,044 ms / 5,000 ms
コード長	49,125 bytes
コンパイル時間	6,407 ms
実行使用メモリ	22,380 KB
スコア	140,896,756
平均クエリ数	7636.80
最終ジャッジ日時	2021-12-12 23:19:12
合計ジャッジ時間	107,185 ms
ジャッジサーバーID （参考情報）	judge12 / judge15
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	896 ms 21,768 KB
testcase_01	AC	896 ms 21,960 KB
testcase_02	AC	957 ms 21,792 KB
testcase_03	AC	900 ms 21,780 KB
testcase_04	AC	816 ms 21,948 KB
testcase_05	AC	914 ms 21,960 KB
testcase_06	AC	1,000 ms 21,924 KB
testcase_07	AC	947 ms 21,912 KB
testcase_08	AC	876 ms 21,984 KB
testcase_09	AC	953 ms 21,780 KB
testcase_10	AC	1,001 ms 21,948 KB
testcase_11	AC	891 ms 21,948 KB
testcase_12	AC	852 ms 21,924 KB
testcase_13	AC	897 ms 22,140 KB
testcase_14	AC	960 ms 22,116 KB
testcase_15	AC	855 ms 21,792 KB
testcase_16	AC	957 ms 22,104 KB
testcase_17	AC	834 ms 21,948 KB
testcase_18	AC	918 ms 21,948 KB
testcase_19	AC	748 ms 22,116 KB
testcase_20	AC	840 ms 21,936 KB
testcase_21	AC	919 ms 22,152 KB
testcase_22	AC	817 ms 22,104 KB
testcase_23	AC	902 ms 21,888 KB
testcase_24	AC	872 ms 22,224 KB
testcase_25	AC	908 ms 21,888 KB
testcase_26	AC	848 ms 22,140 KB
testcase_27	AC	885 ms 21,948 KB
testcase_28	AC	922 ms 22,128 KB
testcase_29	AC	866 ms 21,924 KB
testcase_30	AC	952 ms 21,960 KB
testcase_31	AC	946 ms 21,900 KB
testcase_32	AC	877 ms 21,900 KB
testcase_33	AC	941 ms 21,972 KB
testcase_34	AC	859 ms 22,140 KB
testcase_35	AC	886 ms 21,900 KB
testcase_36	AC	873 ms 22,080 KB
testcase_37	AC	928 ms 21,912 KB
testcase_38	AC	896 ms 21,936 KB
testcase_39	AC	1,031 ms 21,924 KB
testcase_40	AC	1,020 ms 21,972 KB
testcase_41	AC	956 ms 21,936 KB
testcase_42	AC	918 ms 22,152 KB
testcase_43	AC	900 ms 21,900 KB
testcase_44	AC	920 ms 21,948 KB
testcase_45	AC	924 ms 22,100 KB
testcase_46	AC	895 ms 21,900 KB
testcase_47	AC	935 ms 21,912 KB
testcase_48	AC	906 ms 22,116 KB
testcase_49	AC	961 ms 21,948 KB
testcase_50	AC	924 ms 21,960 KB
testcase_51	AC	948 ms 21,924 KB
testcase_52	AC	832 ms 21,912 KB
testcase_53	AC	971 ms 21,912 KB
testcase_54	AC	889 ms 21,936 KB
testcase_55	AC	869 ms 21,900 KB
testcase_56	AC	921 ms 22,128 KB
testcase_57	AC	937 ms 22,152 KB
testcase_58	AC	1,044 ms 22,020 KB
testcase_59	AC	909 ms 21,924 KB
testcase_60	AC	939 ms 21,972 KB
testcase_61	AC	932 ms 21,792 KB
testcase_62	AC	946 ms 21,936 KB
testcase_63	AC	924 ms 21,912 KB
testcase_64	AC	1,018 ms 22,020 KB
testcase_65	AC	998 ms 21,936 KB
testcase_66	AC	852 ms 22,124 KB
testcase_67	AC	926 ms 22,020 KB
testcase_68	AC	1,041 ms 21,936 KB
testcase_69	AC	1,021 ms 21,936 KB
testcase_70	AC	826 ms 22,152 KB
testcase_71	AC	913 ms 21,912 KB
testcase_72	AC	876 ms 21,948 KB
testcase_73	AC	872 ms 21,924 KB
testcase_74	AC	941 ms 21,792 KB
testcase_75	AC	917 ms 21,912 KB
testcase_76	AC	952 ms 21,972 KB
testcase_77	AC	958 ms 21,936 KB
testcase_78	AC	940 ms 21,900 KB
testcase_79	AC	947 ms 21,912 KB
testcase_80	AC	917 ms 21,984 KB
testcase_81	AC	924 ms 21,924 KB
testcase_82	AC	1,016 ms 21,936 KB
testcase_83	AC	931 ms 21,948 KB
testcase_84	AC	982 ms 21,780 KB
testcase_85	AC	889 ms 21,948 KB
testcase_86	AC	900 ms 21,924 KB
testcase_87	AC	854 ms 22,020 KB
testcase_88	AC	971 ms 22,140 KB
testcase_89	AC	920 ms 21,924 KB
testcase_90	AC	973 ms 21,792 KB
testcase_91	AC	877 ms 21,972 KB
testcase_92	AC	841 ms 21,780 KB
testcase_93	AC	995 ms 21,924 KB
testcase_94	AC	959 ms 21,924 KB
testcase_95	AC	827 ms 21,780 KB
testcase_96	AC	1,033 ms 22,380 KB
testcase_97	AC	891 ms 22,140 KB
testcase_98	AC	937 ms 22,116 KB
testcase_99	AC	874 ms 21,948 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define _CRT_SECURE_NO_WARNINGS


#define SUBMIT 1
#define CODETEST 0
#define PERFORMANCE 0

#define OPTUNE 0
#define EVAL 0

#define TIME_LIMIT 4950
#define TIME_LIMIT_US (TIME_LIMIT * 1000)

#define NOT_SUBMIT 0
#define VALIDATION 0

#define IO_FILE 0

#define OUTPUT_INFO 0
#define OUTPUT_FINAL_INFO 0
#define OUTPUT_LOG 0
#define OUTPUT_VISUAL 0

#define FIX_RESULT 0

#ifndef _MSC_VER 
#pragma GCC target ("avx2")
#pragma GCC optimize "O3,omit-frame-pointer,inline"
#pragma GCC optimize ("unroll-loops")



#pragma GCC diagnostic ignored "-Wunused-parameter"
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wunused-variable"

#endif

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;


#define FOR(i, s, e) for (int i = int(s); i < int(e); ++i)
#define RFOR(i, s, e) for (int i = int(e) - 1; i >= int(s); --i)
#define REP(i, n) for (int i = 0, i##_size = int(n); i < i##_size; ++i)
#define RREP(i, n) for (int i = int(n) - 1; i >= 0; --i)

template <class T> inline void chmin(T& a, T b) { if (b < a) { a = b; } }
template <class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template <class T> inline constexpr T square(T v) { return v * v; }


using TimePoint = chrono::steady_clock::time_point;

struct Timer {
private:
	TimePoint startTime_;
	TimePoint endTime_;

public:
	inline void Init() {
		startTime_ = chrono::steady_clock::now();
	}

	inline void StartMs(int limit) {
		endTime_ = startTime_ + chrono::milliseconds(limit);
	}
	inline void StartUs(int limit) {
		endTime_ = startTime_ + chrono::microseconds(limit);
	}

	inline void Join() {
	}

	inline bool IsOver() const {
		return chrono::steady_clock::now() >= endTime_;
	}

	inline int ElapseTimeMs() const {
		return (int)chrono::duration_cast<chrono::milliseconds>(chrono::steady_clock::now() - startTime_).count();
	}
	inline int ElapseTimeUs() const {
		return (int)chrono::duration_cast<chrono::microseconds>(chrono::steady_clock::now() - startTime_).count();
	}
	inline int LeftToUS(const TimePoint& limit) const {
		return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::steady_clock::now()).count();
	}

	inline double NowRate() const {
		return (chrono::steady_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
	}

	inline TimePoint Now() const {
		return chrono::steady_clock::now();
	}
	inline TimePoint EndTime() const {
		return endTime_;
	}

	TimePoint GetLimitTimePointUs(int limit) const {
		return startTime_ + chrono::microseconds(limit);
	}
};

Timer timer;

template <class T>
void InstanceRun(int argc, const char* argv[]) {
	timer.Init();
	T* m = new T;
	m->Run(argc, argv);
	quick_exit(0);
}

struct Main;

signed main(int argc, const char* argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(0);
	InstanceRun<Main>(argc, argv);
}

struct ValidateException {};
struct MemoryException {};


#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)


#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)



#include <cstdint>

using u8 = uint8_t;
using u16 = uint16_t;
using u32 = uint32_t;
using u64 = uint64_t;
using s8 = int8_t;
using s16 = int16_t;
using s32 = int32_t;
using s64 = int64_t;

template <class A, class B>
struct pr {
	union {
		A a;
		A key;
		A first;
		A x;
	};
	union {
		B b;
		B value;
		B second;
		B y;
	};

	bool operator == (pr const& r) const { return a == r.a && b == r.b; }
	bool operator != (pr const& r) const { return !((*this) == r); }
	bool operator < (pr const& r) const {
		if (a == r.a) {
			return b < r.b;
		}
		return a < r.a;
	}

	pr& operator += (pr const& v) {
		a += v.a;
		b += v.b;
		return *this;
	}
	pr& operator -= (pr const& v) {
		a -= v.a;
		b -= v.b;
		return *this;
	}
	pr operator + (pr const& v) const { return pr{ a, b } += v; }
	pr operator - (pr const& v) const { return pr{ a, b } -= v; }
	pr operator - () const { return pr{ -a, -b }; }

	template <class C, class D>
	operator pr<C, D>() const {
		return { C(a), D(b) };
	}

	template <class T>
	auto operator * (T const& v) const -> pr<decltype(x * v), decltype(y * v)> {
		return { x * v, y * v };
	}
	template <class T>
	auto operator / (T const& v) const -> pr<decltype(x / v), decltype(y / v)> {
		return { x / v, y / v };
	}

	template <class T>
	pr& operator *= (T const& v) {
		x *= v;
		y *= v;
		return *this;
	}
	template <class T>
	pr& operator /= (T const& v) {
		x /= v;
		y /= v;
		return *this;
	}

	void flip() { swap(x, y); }

	friend istream& operator>>(istream& is, pr& p) {
		is >> p.a >> p.b;
		return is;
	}
	friend ostream& operator<<(ostream& os, pr const& p) {
		os << p.a << " " << p.b;
		return os;
	}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;

static_assert(is_pod<pint>::value, "not pod");

template <class T>
struct arr : public vector<T> {
	arr() {}
	arr(initializer_list<T> il) : vector<T>(il) {}
	explicit arr(int n, T v = T()) : vector<T>(n, v) {}

	T& operator()(int i) { return (*this)[i]; }
	T const& operator()(int i) const { return (*this)[i]; }
	void init(int n, T v = T()) {
		this->assign(n, v);
	}
	int sz() const { return (int)this->size(); }
	void pb(T v) { this->push_back(v); }
	void sort() { std::sort(this->begin(), this->end()); }
	template <class F> void sort(F&& f) { std::sort(this->begin(), this->end(), f); }
	void rsort() { std::sort(this->begin(), this->end(), greater<T>()); }
	void reverse() { std::reverse(this->begin(), this->end()); }
	void unique_erase() { this->erase(std::unique(this->begin(), this->end()), this->end()); }
	bool next_permutation() { return std::next_permutation(this->begin(), this->end()); }
	int lower_bound(T const& v, function<bool(T, T)> p) { return std::lower_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int lower_bound(T const& v) { return std::lower_bound(this->begin(), this->end(), v) - this->begin(); }
	int upper_bound(T const& v, function<bool(T, T)> p) { return std::upper_bound(this->begin(), this->end(), v, p) - this->begin(); }
	int upper_bound(T const& v) { return std::upper_bound(this->begin(), this->end(), v) - this->begin(); }

	int find_sorted_nearest(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			--i;
		}
		else if ((*this)[i] != v) {
			int p = i - 1;
			if (p >= 0) {
				int id = abs((*this)[i] - v);
				int pd = abs((*this)[p] - v);
				if (pd < id) {
					i = p;
				}
			}
		}
		return i;
	}

	int find_sorted(T const& v) {
		int i = this->lower_bound(v);
		if (i >= sz()) {
			return -1;
		}
		if ((*this)[i] != v) {
			return -1;
		}
		return i;
	}

	int find(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return -1;
		}
		return it - this->begin();
	}
	bool is_contains(T const& v) const {
		auto it = std::find(this->begin(), this->end(), v);
		if (it == this->end()) {
			return false;
		}
		return true;
	}

	template <class P>
	void remove_if_erase(P&& predicate) { this->erase(std::remove_if(this->begin(), this->end(), predicate), this->end()); }

	T& emplace_back_ref() {
		this->emplace_back();
		return this->back();
	}

};
using ints = arr<int>;

template <class T>
struct arr2 {
	vector<vector<T>>	m_vec;
	int			m_width;
	int			m_height;

	arr2() : m_width(0), m_height(0) {}
	arr2(int w, int h, T const& value = T()) : m_width(w), m_height(h) {
		m_vec.resize(h, vector<T>(w, value));
	}
	arr2(arr2 const& r) {
		m_vec = r.m_vec;
		m_width = r.m_width;
		m_height = r.m_height;
	}
	arr2(arr2&& r) {
		m_vec = move(r.m_vec);
		m_width = r.m_width;
		m_height = r.m_height;
	}
	arr2& operator=(arr2 const& r) {
		m_vec = r.m_vec;
		m_width = r.m_width;
		m_height = r.m_height;
		return *this;
	}
	arr2& operator=(arr2&& r) {
		m_vec = move(r.m_vec);
		m_width = r.m_width;
		m_height = r.m_height;
		return *this;
	}

	bool operator ==(arr2 const& r) const {
		return m_vec = r.m_vec;
	}

	bool operator <(arr2 const& r) const {
		if (m_width != r.m_width) {
			return m_width < r.m_width;
		}
		if (m_height != r.m_height) {
			return m_height < r.m_height;
		}
		REP(y, m_height) {
			REP(x, m_width) {
				if ((*this)(x, y) != r(x, y)) {
					return (*this)(x, y) < r(x, y);
				}
			}
		}
		return false;
	}

	pint size() const { return pint{ m_width, m_height }; }
	int width() const { return m_width; }
	int height() const { return m_height; }

	void clear() {
		m_vec.clear();
		m_width = 0;
		m_height = 0;
	}

	void init(int w, int h, T const& value = T()) {
		m_vec.clear();
		m_vec.resize(h, vector<T>(w, value));
		m_width = w;
		m_height = h;
	}
	void init(pint size, T const& value = T()) {
		init(size.x, size.y, value);
	}


	T& operator()(int x, int y) {
		return m_vec[y][x];
	}
	T const& operator()(int x, int y) const {
		return m_vec[y][x];
	}

	T& operator()(pint p) {
		return m_vec[p.y][p.x];
	}
	T const& operator()(pint p) const {
		return m_vec[p.y][p.x];
	}

	T& operator[](pint p) {
		return m_vec[p.y][p.x];
	}
	T const& operator[](pint p) const {
		return m_vec[p.y][p.x];
	}

	vector<T>& operator[](int row) {
		return m_vec[row];
	}
	vector<T> const& operator[](int row) const {
		return m_vec[row];
	}

	bool isIn(int x, int y) const {
		return
			x >= 0 && x < m_width&&
			y >= 0 && y < m_height;
	}
	bool isIn(pint p) const { return isIn(p.x, p.y); }
	bool isOut(int x, int y) const {
		return
			x < 0 || x >= m_width ||
			y < 0 || y >= m_height;
	}
	bool isOut(pint p) const { return isOut(p.x, p.y); }

	void disp(ostream& os, int w = 2) {
		REP(y, m_height) {
			REP(x, m_width) {
				os << setw(w) << (*this)(x, y) << " ";
			}
			os << endl;
		}
		os << endl;
	}
};

template <class T, int CAPACITY>
class CapacityArray {
private:
	array<T, CAPACITY> array_ = {};
	int count_ = 0;

public:
	inline void Clear() {
		count_ = 0;
	}

	inline void Resize(int count) {
		count_ = count;
	}

	inline T* PushBack() {
		return &array_[count_++];
	}

	inline void PushBack(const T& e) {
		array_[count_++] = e;
	}

	inline void PopBack() {
		--count_;
	}

	inline void RemoveSlide(int i) {
		array_[i] = array_[count_ - 1];
		--count_;
	}

	inline int GetCount() const {
		return count_;
	}
	inline int size() const {
		return count_;
	}

	inline bool empty() const {
		return count_ == 0;
	}

	inline T& operator[](int index) {
		return array_[index];
	}

	inline const T& operator[](int index) const {
		return array_[index];
	}

	inline auto begin() -> decltype(array_.begin()) {
		return array_.begin();
	}

	inline auto end() -> decltype(array_.begin()) {

		return array_.begin() + count_;
	}

	inline auto begin() const -> decltype(array_.begin()) {
		return array_.begin();
	}

	inline auto end() const -> decltype(array_.begin()) {

		return array_.begin() + count_;
	}

	inline bool IsContain(const T& value) const {
		for (const auto& v : *this) {
			if (v == value) {
				return true;
			}
		}
		return false;
	}


	inline void MemOverride(int dstIndex, int dstCount, const T* srcPtr, int srcCount) {
		memmove(&array_[dstIndex + srcCount], &array_[dstIndex + dstCount], sizeof(T) * (count_ - (dstIndex + dstCount)));
		memcpy(&array_[dstIndex], srcPtr, sizeof(T) * srcCount);
		count_ += srcCount - dstCount;
	}

};





template <int CAPACITY>
struct CapacitySet {
private:
	CapacityArray<int, CAPACITY> elemens;
	array<int, CAPACITY> indexTable;

public:
	CapacitySet() {
		fill(indexTable.begin(), indexTable.end(), -1);
	}

	void Clear() {
		elemens.Clear();
		fill(indexTable.begin(), indexTable.end(), -1);
	}

	inline void Add(int ai) {
		indexTable[ai] = elemens.GetCount();
		elemens.PushBack(ai);
	}

	inline void ForceAdd(int ai) {
		if (indexTable[ai] >= 0) {
			return;
		}
		indexTable[ai] = elemens.GetCount();
		elemens.PushBack(ai);
	}

	inline void Remove(int ai) {
		int removeIndex = indexTable[ai];
		int lastIndex = elemens.GetCount() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.PopBack();
		indexTable[ai] = -1;
	}

	inline void ForceRemove(int ai) {
		if (indexTable[ai] < 0) {
			return;
		}
		int removeIndex = indexTable[ai];
		int lastIndex = elemens.GetCount() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.PopBack();
		indexTable[ai] = -1;
	}

	inline bool IsContain(int ai) const {
		return indexTable[ai] >= 0;
	}

	inline int GetCount() const {
		return elemens.GetCount();
	}
	inline int size() const {
		return elemens.GetCount();
	}

	inline int At(int index) const {
		return elemens[index];
	}

	inline int operator[](int index) const {
		return elemens[index];
	}

	inline auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	inline auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};


struct SizeSet {
private:
	vector<int> elemens;
	vector<int> indexTable;

public:
	void InitSize(int size) {
		elemens.clear();
		elemens.reserve(size);
		indexTable.assign(size, -1);
	}

	void Clear() {
		elemens.clear();
		indexTable.assign(indexTable.size(), -1);
	}

	inline void Add(int ai) {
		indexTable[ai] = (int)elemens.size();
		elemens.emplace_back(ai);
	}

	inline void ForceAdd(int ai) {
		if (indexTable[ai] >= 0) {
			return;
		}
		indexTable[ai] = (int)elemens.size();
		elemens.emplace_back(ai);
	}

	inline void Remove(int ai) {
		int removeIndex = indexTable[ai];
		int lastIndex = (int)elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.pop_back();
		indexTable[ai] = -1;
	}

	inline void ForceRemove(int ai) {
		if (indexTable[ai] < 0) {
			return;
		}
		int removeIndex = indexTable[ai];
		int lastIndex = (int)elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable[elemens[lastIndex]] = removeIndex;
		}
		elemens.pop_back();
		indexTable[ai] = -1;
	}

	inline bool IsContain(int ai) const {
		return indexTable[ai] >= 0;
	}

	inline int GetCount() const {
		return (int)elemens.size();
	}

	inline int At(int index) const {
		return elemens[index];
	}

	inline int operator[](int index) const {
		return elemens[index];
	}

	inline auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	inline auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	inline auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};


struct CheckMap {
private:
    vector<u32> checked_;
    u32 mark_ = 0;

public:
    void SetSize(int size) {
        checked_.resize(size, mark_);
    }
    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_.assign(checked_.size(), 0);
            ++mark_;
        }
    }
    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }
};

template <class T>
struct CheckMapData {
private:
    vector<T> data_;
    vector<u32> checked_;
    u32 mark_ = 0;

public:
    void SetSize(int size) {
        checked_.resize(size, mark_);
        data_.resize(size);
    }

    void Clear() {
        ++mark_;

        if (mark_ == 0) {
            checked_.assign(checked_.size(), 0);
            ++mark_;
        }
    }

    bool IsChecked(int i) const {
        return checked_[i] == mark_;
    }
    void Check(int i) {
        checked_[i] = mark_;
    }

    void Set(int i, const T& value) {
        checked_[i] = mark_;
        data_[i] = value;
    }

    void Reset(int i) {
        checked_[i] = mark_ - 1;
    }
    const T& Get(int i) const {
        return data_[i];
    }
    T& Ref(int i) {
        return data_[i];
    }
};

struct BiasDistribution {
	discrete_distribution<int> dist_;

	template <class ITERATOR>
	void set(ITERATOR&& begin, ITERATOR&& end) {
		dist_.param(discrete_distribution<int>::param_type(begin, end));
	}

	template <class ENGINE>
	int operator()(ENGINE& engine) {
		return dist_(engine);
	}

};

#include <cstdint>

struct XorShift {
	uint32_t x;
	uint32_t y;
	uint32_t z;
	uint32_t w;

	inline XorShift(uint32_t seed = 0) {
		x = 123456789;
		y = 362436069;
		z = 521288629;
		w = 88675123 + seed;
	}

	inline uint32_t operator()() {
		uint32_t t = x ^ (x << 11);
		x = y;
		y = z;
		z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}

	inline uint32_t operator()(uint32_t l, uint32_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint32_t operator()(uint32_t r) {
		return (*this)() % r;
	}
};

struct Xor64 {
	uint64_t x;
	inline Xor64(uint64_t seed = 0) {
		x = 88172645463325252ULL + seed;
	}

	inline uint64_t operator()() {
		x = x ^ (x << 7);
		return x = x ^ (x >> 9);
	}

	inline uint64_t operator()(uint64_t l, uint64_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint64_t operator()(uint64_t r) {
		return (*this)() % r;
	}
};

struct Xor32 {
	using result_type = uint32_t;
	static constexpr result_type min() { return 0; }
	static constexpr result_type max() { return UINT32_MAX; }

	uint32_t x;
	inline Xor32(uint32_t seed = 0) {
		x = 2463534242 + seed;
	}

	inline uint32_t operator ()(void) {
		x = x ^ (x << 13);
		x = x ^ (x >> 17);
		return x = x ^ (x << 5);
	}

	inline uint32_t operator()(uint32_t l, uint32_t r) {
		return ((*this)() % (r - l)) + l;
	}

	inline uint32_t operator()(uint32_t r) {
		return (*this)() % r;
	}
};

struct Random {
	static inline Xor32& Instnce() {
		static Xor32 x;
		return x;
	}

	static inline uint32_t Get() {
		return Instnce()();
	}
	static inline uint32_t Get(uint32_t l, uint32_t r) {
		return Instnce()(l, r);
	}
	static inline uint32_t Get(uint32_t r) {
		return Instnce()(r);
	}

	static inline void Get2(uint32_t N, uint32_t& a, uint32_t& b) {
	}

	static inline double GetDouble() {
		return Get() / (double)UINT32_MAX;
	}
};



#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue;




constexpr
struct {
	REGIST_PARAM(ESTIMATE_STEP_COUNT, int, 29);

	REGIST_PARAM(EstimatePhaseTurn, int, 1);          
	REGIST_PARAM(EstimatePhaseGeta, int, 248);
	REGIST_PARAM(EstimateMoveWidth, int, 24);

	REGIST_PARAM(AreaSpawnBaseRate, double, 1.926734588287346);          
	REGIST_PARAM(AreaSpawnCenterB, double, 0.9028711031473236);
	REGIST_PARAM(AreaSpawnCenterC, double, 0.944961464534612);

	REGIST_PARAM(ExpectValuePlayerCountA, double, 2.6414616524112673);          
	REGIST_PARAM(ExpectValuePlayerCountE, double, 0.41446193496664735);
	REGIST_PARAM(ExpectValueTurnA, double, 0.9610466431184533);
	REGIST_PARAM(ExpectValueTurnE, double, 1.3373020602261079);
	REGIST_PARAM(ExpectValueRangeA, double, 3.584080512244427);
	REGIST_PARAM(ExpectValueRangeE, double, 2.0993163643741855);

	REGIST_PARAM(GroupEvalCenterA, double, 0.04470682328235353);          
	REGIST_PARAM(GroupEvalCenterE, double, 0.9219452669424091);
	REGIST_PARAM(GroupEvalCenterMaxA, double, 0.055399574807733616);
	REGIST_PARAM(GroupEvalCenterMaxE, double, 0.9958985777589286);
	REGIST_PARAM(GroupEvalPlayerCountA, double, 4.295776030147873);
	REGIST_PARAM(GroupEvalPlayerCountE, double, 1.4023745537494616);	
	REGIST_PARAM(GroupEvalRangeA, double, 1.6704653267548553);
	REGIST_PARAM(GroupEvalRangeE, double, 1.4990519387141583);

	REGIST_PARAM(GroupRelationCrossA, double, 18.417356240790927);          
	REGIST_PARAM(GroupRelationCrossE, double, 0.7457956907792467);

	REGIST_PARAM(FinishGroupCheckTurn1, int, 138);
	REGIST_PARAM(FinishGroupCheckTurn2, int, 151);
	REGIST_PARAM(FinishGroupCheckTurn3, int, 139);
	REGIST_PARAM(FutureScoreRate, double, 8.984796263992141);

} HYPER_PARAM;

constexpr int T_MAX = 3600;		
constexpr int R_MAX = 4;		
constexpr int N_MAX = 5400;		

constexpr int S_MIN = 0;		
constexpr int S_MAX = 100;		
constexpr int S_CENTER = 50;	

constexpr int PlayerCountBonusTable[4] = {
	0, 1, 3, 6
};


struct UnionFind {
	struct Node {
		Node*	parent = nullptr;
		int		count = 1;

		Node* Root() {
			if (parent == nullptr) {
				return this;
			}
			return parent = parent->Root();
		}
	};
	vector<Node> nodes;
	int groupCount;

	UnionFind(int count) {
		nodes.resize(count);
		groupCount = count;
	}

	UnionFind() {
	}
	void Init(int count) {
		nodes.resize(count);
		groupCount = count;
	}

	void Join(int a, int b) {
		Node* rootA = nodes[a].Root();
		Node* rootB = nodes[b].Root();
		if (rootA == rootB) {
			return;
		}

		if (rootA->count > rootB->count) {
			swap(rootA, rootB);
		}

		rootB->count += rootA->count;
		rootA->parent = rootB;
		rootA->count = 0;
		--groupCount;
	}

	bool IsReachable(int a, int b) {
		Node* rootA = nodes[a].Root();
		Node* rootB = nodes[b].Root();
		return rootA == rootB;
	}

	int Count(int a) {
		return nodes[a].Root()->count;
	}

	int GetGroupCount() const {
		return groupCount;
	}

	vector<vector<int>> Groups() {
		std::map<UnionFind::Node*, vector<int>> m;
		for (int i = 0; i < (int)nodes.size(); ++i) {
			auto& node = nodes[i];
			m[node.Root()].push_back(i);
		}

		vector<vector<int>> groups(m.size());
		int i = 0;
		for (auto& p : m) {
			groups[i++] = std::move(p.second);
		}
		return groups;
	}
};


struct Player {
	int startTurn;
	int skill;
};

struct IOServer {
	int T;
	int R;
	int turn;
	arr<Player> players;
	arr<int> newPlayers;				


	void Init() {
		istream& is = cin;
		is >> T >> R;
		turn = 0;
		players.reserve(N_MAX);
		InputNext();
	}

private:
	void InputNext() {
		istream& is = cin;
		if (turn >= T) {
			newPlayers.clear();
			return;
		}

		int n;
		int S;
		is >> n;
		newPlayers.resize(n);
		REP(i, n) {
			is >> S;

			auto& player = players.emplace_back_ref();
			player.skill = S;
			player.startTurn = turn;

			newPlayers[i] = (int)players.size() - 1;
		}
	}

public:


	void TurnOutput(const arr<pint>& joinPlayers) {
		ostream& os = cout;
		os << joinPlayers.size() << endl;
		REP(i, joinPlayers.size()) {
			const auto& j = joinPlayers[i];
			os << j.a + 1 << " " << j.b + 1 << endl;
		}

		++turn;

		InputNext();

	}


	int CalcScore() const {
		return 0;
	}

};

IOServer server;



constexpr double SkillSpawnRate[101] = {
0.000886591	,
0.00100397	,
0.001133689	,
0.001277618	,
0.001434525	,
0.00160503	,
0.001795888	,
0.002001511	,
0.00222116	,
0.002468785	,
0.0027315	,
0.003015067	,
0.003319959	,
0.003645566	,
0.003992201	,
0.004363595	,
0.004758201	,
0.005177994	,
0.005611699	,
0.006068417	,
0.006552535	,
0.007050818	,
0.007574194	,
0.008116218	,
0.008667253	,
0.009239319	,
0.009819463	,
0.010409084	,
0.01102259	,
0.011625182	,
0.012244323	,
0.012851716	,
0.013460935	,
0.014057413	,
0.014651523	,
0.015233315	,
0.015801684	,
0.016338302	,
0.016855305	,
0.017346859	,
0.01781184	,
0.018233642	,
0.018635775	,
0.018968129	,
0.019287902	,
0.019553354	,
0.019790864	,
0.019950125	,
0.020078118	,
0.02015592	,
0.020183211	,
0.020152242	,
0.020079253	,
0.019953895	,
0.019775677	,
0.019562781	,
0.019289282	,
0.018976212	,
0.018634235	,
0.018226315	,
0.017805866	,
0.017336229	,
0.016854305	,
0.016339981	,
0.015797902	,
0.01523896	,
0.014654296	,
0.014062827	,
0.013465667	,
0.012854553	,
0.012237758	,
0.011632685	,
0.011023942	,
0.010418014	,
0.009827223	,
0.009239522	,
0.008669362	,
0.008111972	,
0.007575837	,
0.007053683	,
0.00654921	,
0.006070975	,
0.005610849	,
0.005174682	,
0.004759192	,
0.00436347	,
0.003991778	,
0.003646986	,
0.003321075	,
0.00301742	,
0.002731122	,
0.002468613	,
0.002225941	,
0.00200128	,
0.001796238	,
0.001606176	,
0.001433477	,
0.001276184	,
0.001133847	,
0.001003772	,
0.00088736	,
};

#define JOIN_ON_GROUP_TEST 1
#define CLIP_SCORE_ZERO 0			

#define VALIDATE_SCORE 0
#define VALIDATE_PHASE_ESTIMATE 0
#define GROUP_SCORE_CHECK 0


struct Group {
	CapacityArray<int, R_MAX> players;		
	int minSkill;
	int maxSkill;
	int matchingTurnSum;		
	int startTurnSum;


	bool IsEmpty() const {
		return players.empty();
	}
	bool IsFull() const {
		return players.size() == R_MAX;
	}

	int CenterDist() const {
		if (S_CENTER >= minSkill && S_CENTER <= maxSkill) {
			return 0;
		}
		return min(abs(minSkill - S_CENTER), abs(maxSkill - S_CENTER));
	}
	int CenterDistMax() const {
		if (S_CENTER >= minSkill && S_CENTER <= maxSkill) {
			return 0;
		}
		return max(abs(minSkill - S_CENTER), abs(maxSkill - S_CENTER));
	}




	int GetSkillRangeSize() const {
		return maxSkill - minSkill + 1;
	}

	int CalcScore() const {
		int ps = matchingTurnSum - (players.size() - 1) * startTurnSum;

		int ce = 0;
		if (players.size() == 2) { ce = 1; }
		else if (players.size() == 3) { ce = 3; }
		else if (players.size() == 4) { ce = 6; }
		int score = max(ce * (200 - square(maxSkill - minSkill)) - ps, 0);
		return score;
	}

	int CalcScoreIfAddPlayer(int skill, int nowTurn, int startTurn) const {
		int newMatchingTurnSum = matchingTurnSum + 2 * players.size() * nowTurn;
		int newStartTurnSum = startTurnSum + startTurn;

		int newPlayerCount = players.size() + 1;
		int newMinSkill = min(minSkill, skill);
		int newMaxSkill = max(maxSkill, skill);

		int ps = newMatchingTurnSum - (newPlayerCount - 1) * newStartTurnSum;

		int ce = 0;
		if (newPlayerCount == 2) { ce = 1; }
		else if (newPlayerCount == 3) { ce = 3; }
		else if (newPlayerCount == 4) { ce = 6; }
		int score = max(ce * (200 - square(newMaxSkill - newMinSkill)) - ps, 0);
		return score;
	}

	void Clear() {
		players.Clear();
	}

	void InitGroup(int pi, int skill, int startTurn) {
		matchingTurnSum = 0;
		startTurnSum = startTurn;

		players.PushBack(pi);
		minSkill = maxSkill = skill;
	}

	void AddPlayer(int pi, int skill, int nowTurn, int startTurn) {
		matchingTurnSum += 2 * players.size() * nowTurn;
		startTurnSum += startTurn;

		players.PushBack(pi);
		if (skill < minSkill) {
			minSkill = skill;
		}
		else if (skill > maxSkill) {
			maxSkill = skill;
		}
	}

	void JoinGroup(Group& group, int nowTurn) {
		matchingTurnSum += group.matchingTurnSum;
		matchingTurnSum += 2 * players.size() * group.players.size() * nowTurn;
		startTurnSum += group.startTurnSum;

		if (players[0] < group.players[0]) {
			for (int pi : group.players) {
				players.PushBack(pi);
			}
		}
		else {
			for (int pi : players) {
				group.players.PushBack(pi);
			}
			players = group.players;
		}
		if (group.minSkill < minSkill) {
			minSkill = group.minSkill;
		}
		if (group.maxSkill > maxSkill) {
			maxSkill = group.maxSkill;
		}

		group.Clear();
	}
};

struct PhaseEstimater {
	struct Param {
		int moveWidth = 0;

		double B = 0;
		double C = 0;
		double F = 0;
		double G = 0;
		double H = 0;
		int sampleCount = 0;

		int moveTotal_ = 0;
		int moveCount_ = 0;

		void SetMoveWidth(int mw) {
			moveWidth = mw;

		}

		double CalcE(double np) const {

			return B / 2.0 * sin(2 * np) - C / 2.0 * cos(2 * np) - 2 * F * cos(np) - 2 * G * sin(np) + H + (sampleCount) / 2.0;
		}

		double CalcDiff(double np) const {
			return B * cos(2 * np) + C * sin(2 * np) + 2 * F * sin(np) - 2 * G * cos(np);
		}

		double CalcDiff2(double np) const {
			return -B * sin(2 * np) + C * cos(2 * np) + 2 * F * cos(np) + 2 * G * sin(np);
		}

		void Add(int turn, int spawnCount, const arr<int>& spawnCountsRecord) {
			moveTotal_ += spawnCount;
			++moveCount_;
			if (moveCount_ > moveWidth) {
				--moveCount_;
				int index = spawnCountsRecord.sz() - moveWidth - 1;
				moveTotal_ -= spawnCountsRecord[index];
			}


			double avgSpawnCpunt = moveTotal_ / (double)moveCount_;

			double y = avgSpawnCpunt - 1.5;
			double x = (turn - (moveWidth - 1) / 2.0) * 2 * M_PI / (double)T_MAX;	
			B += sin(2 * x);
			C += cos(2 * x);
			F += y * sin(x);
			G += y * cos(x);
			H += y * y;
			++sampleCount;
		}
	};

	arr<Param> params_;

	double phase = 0;

	arr<int> spawnCounts_;
	int spawnTotal_ = 0;

	PhaseEstimater() {
		spawnCounts_.reserve(T_MAX);
		arr<int> WS = { HYPER_PARAM.EstimateMoveWidth };
		params_.resize(WS.size());
		REP(i, WS.size()) {
			params_[i].SetMoveWidth(WS[i]);
		}
	}

	void Add(int turn, int spawnCount) {

		spawnCounts_.emplace_back(spawnCount);
		spawnTotal_ += spawnCount;

		for (auto& param : params_) {
			param.Add(turn, spawnCount, spawnCounts_);
		}

		const auto& paramW1 = params_[0];

		double minNp = 0;
		double minError = INT_MAX;
		int usedWidth = -1;

		for (auto& param : params_) {
			constexpr int TryCount = 4;
			REP(i, TryCount) {
				double np = phase * 2 * M_PI / (double)T_MAX + (i * 2 * M_PI / (double)TryCount);
				REP(step, HYPER_PARAM.ESTIMATE_STEP_COUNT) {
					double dE = param.CalcDiff(np);
					double d2E = param.CalcDiff2(np);
					np = np - dE / d2E;
				}

				double baseError = paramW1.CalcE(np);
				{
					double flipError = paramW1.CalcE(np + M_PI);
					if (baseError > flipError) {
						np += M_PI;
						baseError = flipError;
					}
				}

				if (baseError < minError) {
					minNp = np;
					minError = baseError;
					usedWidth = param.moveWidth;
				}
			}
		}

		double np = minNp;

		phase = np * T_MAX / (2 * M_PI);
		while (phase >= T_MAX) {
			phase -= T_MAX;
		}
		while (phase < 0) {
			phase += T_MAX;
		}

	}

	double CalcTurnSpawnCount(int turn) const {
		double turnSpwanCount = 1.5;
		if (server.turn > 0 && server.turn < HYPER_PARAM.EstimatePhaseTurn) {
			turnSpwanCount = (spawnTotal_ + 1.5 * HYPER_PARAM.EstimatePhaseGeta) / (double)(server.turn + HYPER_PARAM.EstimatePhaseGeta);
			chmin(turnSpwanCount, 2.5);
			chmax(turnSpwanCount, 0.5);
		}
		else {
			constexpr double DIV = 1.0 / (double)T_MAX * 2.0 * M_PI;
			turnSpwanCount = 1.5 + sin((turn + phase) * DIV);
		}
		return turnSpwanCount;
	}

	double CalcAverageSpawnCount() const {
		return spawnTotal_ / (double)spawnCounts_.size();
	}

	double CalcMoveAverageSpawnCount() const {
		const auto& param = params_.back();
		return param.moveTotal_ / (double)param.moveCount_;
	}


	double CalcError() const {
		constexpr double DIV = 1.0 / (double)T_MAX * 2.0 * M_PI;

		double totalError = 0;
		REP(turn, spawnCounts_.size()) {
			double turnSpwanCount = 1.5 + sin((turn + phase) * DIV);
			double err = square(spawnCounts_[turn] - turnSpwanCount);
			totalError += err;
		}
		totalError /= (double)spawnCounts_.sz();
		totalError = sqrt(totalError);
		return totalError;
	}

};

double ParamValue(double x, double a, double e) {
	return a * pow(x, e);
}

struct IntPow {
	arr<double> tbl_;

	IntPow(int maxValue, double a, double e) {
		tbl_.resize(maxValue + 1);
		REP(x, maxValue + 1) {
			tbl_[x] = ParamValue(x, a, e);
		}
	}
	double operator ()(int x) const {
		VASSERT(x < tbl_.sz());
		return tbl_[x];
	}
};

using PlayerQueue = array<deque<int>, S_MAX + 1>;
using Groups = array<Group, S_MAX + 1>;

struct State {
	Groups groups_;
	int score_;


	void FinishGroup(int gi) {
		Group& group = groups_[gi];
		int score = group.CalcScore();
		score_ += score;

		group.Clear();
	}
};

struct Solver {
	PlayerQueue playerQueue_;		
	State state_ = {};
	PhaseEstimater phaseEstimater_;

	mutable array<double, S_MAX + 1> groupScores_ = {};
	mutable array<pint, S_MAX + 1> groupRanges_ = {};

	void Run() {

		arr<pint> joinPlayers;
		REP(t, server.T) {
			for (int pi : server.newPlayers) {
				playerQueue_[server.players[pi].skill].emplace_back(pi);
			}
			phaseEstimater_.Add(t, server.newPlayers.sz());


			joinPlayers.clear();

			RemoveScoreDownGroup(state_);

			JoinOnGroup(playerQueue_, state_, joinPlayers);

			AssignNewGroup(playerQueue_, state_, joinPlayers);
			JoinGroup6(state_, joinPlayers);


			server.TurnOutput(joinPlayers);

#if _DEBUG
#else
			if (timer.IsOver()) {
				break;
			}
#endif
		}

	}

	void JoinGroup6(State& state, arr<pint>& joinPlayers) const {
		arr<int> baseGroupOrder;
		CreateGroupOrder(state, baseGroupOrder);

		vector<vector<ScoreRange>> baseScoreTable;
		CreateScoreTable(state, baseGroupOrder, baseScoreTable);


		arr<s8> maxJoinStack;
		double maxScore = CalcSplit(state, baseGroupOrder, baseScoreTable, maxJoinStack);

		array<int, 5> checkTurnTable = {
			9999,
			HYPER_PARAM.FinishGroupCheckTurn1,
			HYPER_PARAM.FinishGroupCheckTurn2,
			HYPER_PARAM.FinishGroupCheckTurn3,
			9999,
		};

		while (true) {
			int maxRemoveOi = -1;

			REP(oi, baseGroupOrder.size()) {
				int gi = baseGroupOrder[oi];
				const auto& group = state.groups_[gi];
				VASSERT(!group.IsEmpty());
				int groupStartTurn = server.players[group.players[0]].startTurn;
				if (server.turn - groupStartTurn < checkTurnTable[group.players.size()]) {
					continue;
				}

				arr<int> groupOrder;
				vector<vector<ScoreRange>> scoreTable;
				RemoveOi(state, baseGroupOrder, baseScoreTable, oi, groupOrder, scoreTable);

				arr<s8> joinStack;
				double tmpScore = CalcSplit(state, groupOrder, scoreTable, joinStack);

				tmpScore += group.CalcScore();

				if (tmpScore > maxScore) {
					maxScore = tmpScore;
					maxJoinStack = move(joinStack);
					maxRemoveOi = oi;
				}
			}

			if (maxRemoveOi >= 0) {
				state.FinishGroup(baseGroupOrder[maxRemoveOi]);

				arr<int> groupOrder;
				vector<vector<ScoreRange>> scoreTable;
				RemoveOi(state, baseGroupOrder, baseScoreTable, maxRemoveOi, groupOrder, scoreTable);

				baseScoreTable = move(scoreTable);
				baseGroupOrder = move(groupOrder);
			}
			else {
				break;
			}
		}

		SplitGroups(state, baseGroupOrder, maxJoinStack, joinPlayers);
	}

	struct ScoreRange {
		double score;
		pint range;
	};

	void CreateGroupOrder(const State& state, arr<int>& groupOrder) const {
		groupOrder.clear();
		REP(gi, S_MAX + 1) {
			auto& group = state.groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}
			groupOrder.emplace_back(gi);
		}
	}

	double CalcGroupEvalScore(const Group& group, const pint& limitRange, pint& maxRange) const {
		maxRange = { -1, -1 };
		double score = CalcMaxValueRange(group, maxRange, limitRange);
		VASSERT(maxRange.a >= 0 && maxRange.b >= 0);


		static IntPow centerDistValue(S_MAX, HYPER_PARAM.GroupEvalCenterA, HYPER_PARAM.GroupEvalCenterE);
		static IntPow centerDistMaxValue(S_MAX, HYPER_PARAM.GroupEvalCenterMaxA, HYPER_PARAM.GroupEvalCenterMaxE);
		score -= centerDistValue(group.CenterDist());
		score -= centerDistMaxValue(group.CenterDistMax());

		static IntPow playerValue(R_MAX, HYPER_PARAM.GroupEvalPlayerCountA, HYPER_PARAM.GroupEvalPlayerCountE);
		score += playerValue(group.players.size());

		static IntPow rangeValue(S_MAX, HYPER_PARAM.GroupEvalRangeA, HYPER_PARAM.GroupEvalRangeE);
		score -= rangeValue(maxRange.b - maxRange.a);


		score *= group.players.size();

		return score;
	}

	void CreateScoreTable(const State& state, const arr<int>& groupOrder, vector<vector<ScoreRange>>& scoreTable) const {

		auto SetTable = [&](const Group& group, const pint& limitRange, int startOi, int curOi) {
			pint maxRange = { -1, -1 };
			double score = CalcGroupEvalScore(group, limitRange, maxRange);
			scoreTable[startOi][curOi].score = score;
			scoreTable[startOi][curOi].range = maxRange;
		};

		scoreTable.resize(groupOrder.size());
		REP(oi, groupOrder.size()) {
			scoreTable[oi].assign(groupOrder.size(), ScoreRange{ -1, pint{-1, -1} });
		}

		const auto& groups = state.groups_;

		REP(startOi, groupOrder.size()) {
			int startGi = groupOrder[startOi];
			Group group = groups[startGi];
			pint limitRange;
			if (startOi > 0) {
				limitRange.a = groups[groupOrder[startOi - 1]].maxSkill + 1;
			}
			else {
				limitRange.a = 0;
			}
			if (startOi + 1 < groupOrder.sz()) {
				limitRange.b = groups[groupOrder[startOi + 1]].minSkill - 1;
			}
			else {
				limitRange.b = S_MAX;
			}

			SetTable(group, limitRange, startOi, startOi);

			FOR(curOi, startOi + 1, groupOrder.size()) {
				int curGi = groupOrder[curOi];
				if (group.players.size() + groups[curGi].players.size() > R_MAX) {
					break;
				}

				Group tmp = groups[curGi];
				group.JoinGroup(tmp, server.turn);

				if (curOi + 1 < groupOrder.sz()) {
					limitRange.b = groups[groupOrder[curOi + 1]].minSkill - 1;
				}
				else {
					limitRange.b = S_MAX;
				}

				SetTable(group, limitRange, startOi, curOi);
			}
		}
	}

	void RemoveOi(const State& state, const arr<int>& srcGroupOrder, const vector<vector<ScoreRange>>& srcScoreTable, int removeOi, arr<int>& groupOrder, vector<vector<ScoreRange>>& scoreTable) const {
		groupOrder = srcGroupOrder;
		groupOrder.erase(groupOrder.begin() + removeOi);

		auto SetTable = [&](const Group& group, const pint& limitRange, int startOi, int curOi) {
			if ((startOi <= removeOi && removeOi <= curOi) ||
				(startOi == removeOi) ||
				(curOi + 1 == removeOi)) {
				pint maxRange = { -1, -1 };
				double score = CalcGroupEvalScore(group, limitRange, maxRange);
				scoreTable[startOi][curOi].score = score;
				scoreTable[startOi][curOi].range = maxRange;

			}
			else {
				int srcStart = startOi;
				int srcEnd = curOi;
				if (srcStart >= removeOi) {
					srcStart++;
				}
				if (srcEnd >= removeOi) {
					srcEnd++;
				}
				scoreTable[startOi][curOi] = srcScoreTable[srcStart][srcEnd];
			}
		};

		scoreTable.resize(groupOrder.size());
		REP(oi, groupOrder.size()) {
			scoreTable[oi].assign(groupOrder.size(), ScoreRange{ -1, pint{-1, -1} });
		}

		const auto& groups = state.groups_;

		REP(startOi, groupOrder.size()) {
			int startGi = groupOrder[startOi];
			Group group = groups[startGi];
			pint limitRange;
			if (startOi > 0) {
				limitRange.a = groups[groupOrder[startOi - 1]].maxSkill + 1;
			}
			else {
				limitRange.a = 0;
			}
			if (startOi + 1 < groupOrder.sz()) {
				limitRange.b = groups[groupOrder[startOi + 1]].minSkill - 1;
			}
			else {
				limitRange.b = S_MAX;
			}

			SetTable(group, limitRange, startOi, startOi);

			FOR(curOi, startOi + 1, groupOrder.size()) {
				int curGi = groupOrder[curOi];
				if (group.players.size() + groups[curGi].players.size() > R_MAX) {
					break;
				}

				Group tmp = groups[curGi];
				group.JoinGroup(tmp, server.turn);

				if (curOi + 1 < groupOrder.sz()) {
					limitRange.b = groups[groupOrder[curOi + 1]].minSkill - 1;
				}
				else {
					limitRange.b = S_MAX;
				}

				SetTable(group, limitRange, startOi, curOi);
			}
		}
	}

	double CalcSplit(const State& state, const arr<int>& groupOrder, const vector<vector<ScoreRange>>& scoreTable, arr<s8>& maxJoinStack) const {

		double maxScore = INT_MIN;
		maxJoinStack.clear();
		{
			arr<s8> joinStack;
			auto DFS = [&](auto&& dfs, const pint& prevRange, s8 startOi, s8 oi, double totalScore) {
				if (oi >= groupOrder.sz()) {
					if (totalScore > maxScore) {
						maxScore = totalScore;
						maxJoinStack = joinStack;
					}
					return;
				}

				if (scoreTable[startOi][oi].range.a < 0) {
					return;
				}

				double score = scoreTable[startOi][oi].score;

				{
					double rangeScore = 0;
					const pint& range = scoreTable[startOi][oi].range;
					if (range.a <= prevRange.b) {
						int crossCount = prevRange.b - range.a + 1;
						static IntPow rangeValue(S_MAX, HYPER_PARAM.GroupRelationCrossA, HYPER_PARAM.GroupRelationCrossE);
						rangeScore -= rangeValue(crossCount);
					}

					joinStack.emplace_back(oi);
					dfs(dfs, range, oi + 1, oi + 1, totalScore + score + rangeScore);
					joinStack.pop_back();
				}

				if (oi + 1 == groupOrder.sz()) {
					return;
				}

					dfs(dfs, prevRange, startOi, oi + 1, totalScore);
			};
			DFS(DFS, pint{ -1, -1 }, 0, 0, 0);
		}

		VASSERT(maxScore != INT_MIN);

		double resultScore = state.score_ + maxScore * HYPER_PARAM.FutureScoreRate;
		return resultScore;
	}

	void SplitGroups(State& state, const arr<int>& groupOrder, const arr<s8>& maxJoinStack, arr<pint>& joinPlayers) const {
		s8 startOi = 0;
		for (int oi : maxJoinStack) {
			if (startOi != oi) {
				int gi1 = groupOrder[startOi];
				auto& group1 = state.groups_[gi1];
				FOR(oi2, startOi + 1, oi + 1) {
					int gi2 = groupOrder[oi2];
					auto& group2 = state.groups_[gi2];
					VASSERT(group1.players.size() + group2.players.size() <= R_MAX);

					joinPlayers.emplace_back(pint{ group1.players[0], group2.players[0] });
					group1.JoinGroup(group2, server.turn);

					if (group1.IsFull()) {
						state.FinishGroup(gi1);
					}
				}
			}
			startOi = oi + 1;
		}
	}


	double CalcJoinGroupScore(const State& state) const {
		arr<int> baseGroupOrder;
		CreateGroupOrder(state, baseGroupOrder);

		vector<vector<ScoreRange>> baseScoreTable;
		CreateScoreTable(state, baseGroupOrder, baseScoreTable);

		arr<s8> maxJoinStack;
		double maxScore = CalcSplit(state, baseGroupOrder, baseScoreTable, maxJoinStack);

		return maxScore;
	}

	double CalcMaxValue(const Group& group, int siL, int siR) const {
		double maxScore = INT_MIN;

		auto CheckMaxScore = [&](const Group& tmpGroup, int turn) {
			double score = tmpGroup.CalcScore();

			{
				static IntPow playerValue(4, HYPER_PARAM.ExpectValuePlayerCountA, HYPER_PARAM.ExpectValuePlayerCountE);
				score += playerValue(tmpGroup.players.size());

				static IntPow turnValue(T_MAX, HYPER_PARAM.ExpectValueTurnA, HYPER_PARAM.ExpectValueTurnE);
				score -= turnValue(turn - server.turn);

				static IntPow rangeValue(S_MAX, HYPER_PARAM.ExpectValueRangeA, HYPER_PARAM.ExpectValueRangeE);
				score -= rangeValue(tmpGroup.maxSkill - tmpGroup.minSkill);

			}

			if (server.turn < T_MAX - 1) {
				score /= tmpGroup.players.size();
			}

			if (score > maxScore) {
				maxScore = score;
			}
			return score;
		};

		CheckMaxScore(group, server.turn);

		if (!group.IsFull()) {
			auto tmpGroup = group;
			tmpGroup.minSkill = siL;
			tmpGroup.maxSkill = siR;

			double spawnRate = 0;
			FOR(si, siL, siR + 1) {
				spawnRate += SkillSpawnRate[si];
			}

			spawnRate *= HYPER_PARAM.AreaSpawnBaseRate;
			spawnRate *= pow(HYPER_PARAM.AreaSpawnCenterB, tmpGroup.CenterDist() / 50.0);
			spawnRate *= pow(HYPER_PARAM.AreaSpawnCenterC, tmpGroup.CenterDistMax() / 50.0);


			double power = 0;
			FOR(turn, server.turn + 1, server.T) {
				double turnSpwanCount = phaseEstimater_.CalcTurnSpawnCount(turn);
				power += turnSpwanCount * spawnRate;
				if (power >= 1.0) {
					power -= 1.0;
					tmpGroup.AddPlayer(-1, siL, turn, turn);

					CheckMaxScore(tmpGroup, turn);		


					if (tmpGroup.IsFull()) {
						break;
					}
				}
			}
		}

		VASSERT(maxScore != INT_MIN);

		return maxScore;
	}


	double CalcMaxValueRange(const Group& group, pint& maxRange, const pint& limitRange) const {
		int siL = group.minSkill;
		int siR = group.maxSkill;

		int maxSiL = -1;
		int maxSiR = -1;
		double maxScore = INT_MIN;

		while (true) {
			double score = CalcMaxValue(group, siL, siR);
			if (score > maxScore) {
				maxScore = score;
				maxSiL = siL;
				maxSiR = siR;
			}

			if (siR - siL >= 10) {
				break;
			}

			CapacityArray<int, 2> candidates;
			if (siL - 1 >= 0 && siL - 1 >= limitRange.a) {
				candidates.PushBack(siL - 1);
			}
			if (siR + 1 <= S_MAX && siR + 1 <= limitRange.b) {
				candidates.PushBack(siR + 1);
			}

			if (candidates.GetCount() == 0) {
				break;
			}

			int newSi = -1;
			if (candidates.GetCount() == 2) {
				if (SkillSpawnRate[candidates[0]] >= SkillSpawnRate[candidates[1]]) {
					newSi = candidates[0];
				}
				else {
					newSi = candidates[1];
				}
			}
			else {
				newSi = candidates[0];
			}

			if (newSi == siL - 1) {
				--siL;
			}
			else {
				++siR;
			}
		}

		maxRange.a = maxSiL;
		maxRange.b = maxSiR;

		VASSERT(maxScore != INT_MIN);

		return maxScore;
	}

	void RemoveScoreDownGroup(State& state) const {
		REP(gi, S_MAX + 1) {
			auto& group = state.groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}

			double curScore = group.CalcScore();

			double newScore = group.CalcScoreIfAddPlayer(group.minSkill, server.turn, server.turn);

			curScore /= group.players.size();
			newScore /= group.players.size() + 1;

			if (newScore <= curScore) {
				state.FinishGroup(gi);
			}
		}
	}


	void JoinOnGroup(PlayerQueue& playerQueue, State& state, arr<pint>& joinPlayers) const {
		arr<int> groupOrder;
		arr<arr<arr<s8>>> groupCandidates;
		REP(gi, S_MAX + 1) {
			auto& group = state.groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}

			int waitPlayerCount = 0;
			FOR(si, group.minSkill, group.maxSkill + 1) {
				waitPlayerCount += (int)playerQueue[si].size();
			}
			if (waitPlayerCount == 0) {
				continue;
			}

			groupOrder.emplace_back(gi);

			arr<arr<s8>> candidates;
			auto DFS = [&](auto&& dfs, int si, int left, arr<s8>& useStack) -> void {
				if (si > group.maxSkill) {
					if (left == 0) {
						candidates.emplace_back(useStack);
					}
					return;
				}
				dfs(dfs, si + 1, left, useStack);

				FOR(useCount, 1, min((int)playerQueue[si].size(), left) + 1) {
					REP(i, useCount) {
						useStack.emplace_back(si);
					}
					dfs(dfs, si + 1, left - useCount, useStack);
					REP(i, useCount) {
						useStack.pop_back();
					}
				}
			};

			int left = min(R_MAX - (int)group.players.size(), waitPlayerCount);
			if (left > 0) {
				arr<s8> useStack;
				DFS(DFS, group.minSkill, left, useStack);
			}

			groupCandidates.emplace_back(move(candidates));
		}

		if (groupCandidates.size() == 0) {
			return;
		}

#define DISP_CANDIDATE 0

		double maxEvalScore = INT_MIN;
		arr<s8> maxSkills;

		auto DFS = [&](auto&& dfs, int oi, State& srcState, arr<s8>& selectStack, array<int, S_MAX + 1>& skipCounts) -> void {
			if (oi >= groupOrder.sz()) {
				arr<pint> dummyJoinPlayers;
				AssignNewGroupWithSkip(playerQueue, skipCounts, srcState, dummyJoinPlayers);

				double evalScore = CalcJoinGroupScore(srcState);
				if (evalScore > maxEvalScore) {
					maxEvalScore = evalScore;
					maxSkills = selectStack;
				}

				return;
			}
			const int gi = groupOrder[oi];

			const auto& candidates = groupCandidates[oi];


			REP(ci, candidates.size()) {
				const auto& candidate = candidates[ci];

				selectStack.insert(selectStack.end(), candidate.begin(), candidate.end());
				for (int si : candidate) {
					++skipCounts[si];
				}

				bool pass = (ci == candidate.size() - 1);

				if (pass) {
					for (int si : candidate) {
						auto& group = srcState.groups_[gi];
						group.AddPlayer(-1, si, server.turn, server.turn);
						if (group.IsFull()) {
							srcState.FinishGroup(gi);
						}
					}
					dfs(dfs, oi + 1, srcState, selectStack, skipCounts);
				}
				else {
					State tmpState = srcState;
					for (int si : candidate) {
						auto& group = tmpState.groups_[gi];
						group.AddPlayer(-1, si, server.turn, server.turn);
						if (group.IsFull()) {
							tmpState.FinishGroup(gi);
						}
					}
					dfs(dfs, oi + 1, tmpState, selectStack, skipCounts);
				}

				for (int si : candidate) {
					--skipCounts[si];
				}
				selectStack.erase(selectStack.end() - candidate.size(), selectStack.end());
			}
		};

		State tmpState = state;
		arr<s8> selectStack;
		array<int, S_MAX + 1> skipCounts = {};
		DFS(DFS, 0, tmpState, selectStack, skipCounts);

		VASSERT(maxEvalScore != INT_MIN);

		for (int si : maxSkills) {
			bool hit = false;
			RREP(gi, si + 1) {
				Group& group = state.groups_[gi];
				if (group.IsEmpty()) {
					continue;
				}
				VASSERT(si >= group.minSkill && si <= group.maxSkill);

				hit = true;

				int pi = playerQueue[si].front();
				playerQueue[si].pop_front();
				joinPlayers.emplace_back(pint{ group.players[0], pi });
				group.AddPlayer(pi, server.players[pi].skill, server.turn, server.players[pi].startTurn);
				if (group.IsFull()) {
					state.FinishGroup(gi);
					break;
				}
				break;
			}
			VASSERT(hit);
		}

	}

	void AssignNewGroup(PlayerQueue& playerQueue, State& state, arr<pint>& joinPlayers) const {
		REP(si, S_MAX + 1) {
			auto& queue = playerQueue[si];
			while (!queue.empty()) {
				int pi = queue.front();
				queue.pop_front();

				auto& group = state.groups_[si];
				VASSERT(group.IsEmpty());

				group.InitGroup(pi, server.players[pi].skill, server.players[pi].startTurn);

				REP(loop, R_MAX - 1) {
					if (queue.empty()) {
						break;
					}
					int pi = queue.front();
					queue.pop_front();
					joinPlayers.emplace_back(pint{ group.players[0], pi });
					group.AddPlayer(pi, server.players[pi].skill, server.turn, server.players[pi].startTurn);
					VASSERT(server.turn == server.players[pi].startTurn);
				}
				if (group.IsFull()) {
					state.FinishGroup(si);

				}
			}
		}
	}

	void AssignNewGroupWithSkip(const PlayerQueue& playerQueue, const array<int, S_MAX + 1>& skipCounts, State& state, arr<pint>& joinPlayers) const {
		REP(si, S_MAX + 1) {
			int index = skipCounts[si];
			auto& queue = playerQueue[si];
			while (index < queue.size()) {
				int pi = queue[index++];

				auto& group = state.groups_[si];

				VASSERT(server.turn == server.players[pi].startTurn);

				if (group.IsEmpty()) {
					group.InitGroup(pi, server.players[pi].skill, server.players[pi].startTurn);
				}
				else {
					joinPlayers.emplace_back(pint{ group.players[0], pi });
					group.AddPlayer(pi, server.players[pi].skill, server.turn, server.players[pi].startTurn);

					if (group.IsFull()) {
						state.FinishGroup(si);

					}
				}
			}
		}
	}
};

struct Main {
	void Run(int argc, const char* argv[]) {
		server.Init();
		timer.StartMs(TIME_LIMIT);

		Solver* solver = new Solver;
		solver->Run();

	}

};
yukicoder

結果

テストケース

ソースコード
