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

提出ソース
結果

問題	No.5004 Room Assignment
ユーザー	bowwowforeach
提出日時	2021-12-07 06:16:44
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	816 ms / 5,000 ms
コード長	39,888 bytes
コンパイル時間	4,011 ms
実行使用メモリ	22,368 KB
スコア	140,412,709
平均クエリ数	7638.20
最終ジャッジ日時	2021-12-07 06:18:07
合計ジャッジ時間	81,799 ms
ジャッジサーバーID （参考情報）	judge15 / judge14
	純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	667 ms 21,948 KB
testcase_01	AC	676 ms 21,912 KB
testcase_02	AC	710 ms 21,924 KB
testcase_03	AC	677 ms 21,792 KB
testcase_04	AC	711 ms 21,888 KB
testcase_05	AC	768 ms 21,936 KB
testcase_06	AC	691 ms 21,948 KB
testcase_07	AC	729 ms 22,032 KB
testcase_08	AC	710 ms 22,140 KB
testcase_09	AC	733 ms 22,020 KB
testcase_10	AC	686 ms 21,948 KB
testcase_11	AC	699 ms 22,104 KB
testcase_12	AC	657 ms 21,900 KB
testcase_13	AC	727 ms 22,152 KB
testcase_14	AC	767 ms 21,912 KB
testcase_15	AC	664 ms 21,948 KB
testcase_16	AC	709 ms 21,912 KB
testcase_17	AC	666 ms 22,368 KB
testcase_18	AC	670 ms 21,792 KB
testcase_19	AC	671 ms 22,188 KB
testcase_20	AC	631 ms 21,960 KB
testcase_21	AC	676 ms 21,996 KB
testcase_22	AC	679 ms 22,032 KB
testcase_23	AC	706 ms 21,936 KB
testcase_24	AC	677 ms 21,960 KB
testcase_25	AC	693 ms 21,792 KB
testcase_26	AC	687 ms 21,932 KB
testcase_27	AC	674 ms 22,140 KB
testcase_28	AC	686 ms 21,804 KB
testcase_29	AC	666 ms 21,924 KB
testcase_30	AC	666 ms 21,804 KB
testcase_31	AC	787 ms 22,176 KB
testcase_32	AC	714 ms 22,104 KB
testcase_33	AC	701 ms 21,996 KB
testcase_34	AC	737 ms 21,900 KB
testcase_35	AC	756 ms 22,068 KB
testcase_36	AC	693 ms 21,996 KB
testcase_37	AC	761 ms 21,936 KB
testcase_38	AC	737 ms 21,948 KB
testcase_39	AC	758 ms 21,912 KB
testcase_40	AC	785 ms 21,924 KB
testcase_41	AC	706 ms 21,996 KB
testcase_42	AC	713 ms 22,140 KB
testcase_43	AC	668 ms 22,152 KB
testcase_44	AC	654 ms 22,140 KB
testcase_45	AC	708 ms 22,140 KB
testcase_46	AC	674 ms 21,936 KB
testcase_47	AC	757 ms 21,792 KB
testcase_48	AC	645 ms 21,912 KB
testcase_49	AC	714 ms 21,948 KB
testcase_50	AC	745 ms 21,936 KB
testcase_51	AC	778 ms 21,996 KB
testcase_52	AC	760 ms 21,972 KB
testcase_53	AC	666 ms 21,900 KB
testcase_54	AC	712 ms 21,960 KB
testcase_55	AC	654 ms 22,140 KB
testcase_56	AC	816 ms 21,792 KB
testcase_57	AC	763 ms 22,020 KB
testcase_58	AC	731 ms 21,956 KB
testcase_59	AC	679 ms 21,936 KB
testcase_60	AC	725 ms 21,912 KB
testcase_61	AC	697 ms 21,804 KB
testcase_62	AC	693 ms 21,804 KB
testcase_63	AC	716 ms 21,960 KB
testcase_64	AC	787 ms 22,004 KB
testcase_65	AC	714 ms 21,948 KB
testcase_66	AC	649 ms 22,092 KB
testcase_67	AC	677 ms 21,912 KB
testcase_68	AC	704 ms 21,924 KB
testcase_69	AC	751 ms 21,720 KB
testcase_70	AC	715 ms 21,960 KB
testcase_71	AC	668 ms 22,152 KB
testcase_72	AC	725 ms 22,080 KB
testcase_73	AC	677 ms 21,720 KB
testcase_74	AC	796 ms 22,056 KB
testcase_75	AC	748 ms 21,924 KB
testcase_76	AC	780 ms 22,008 KB
testcase_77	AC	697 ms 21,780 KB
testcase_78	AC	718 ms 21,996 KB
testcase_79	AC	687 ms 22,152 KB
testcase_80	AC	640 ms 22,224 KB
testcase_81	AC	715 ms 21,948 KB
testcase_82	AC	778 ms 21,980 KB
testcase_83	AC	654 ms 21,924 KB
testcase_84	AC	691 ms 21,912 KB
testcase_85	AC	755 ms 22,068 KB
testcase_86	AC	699 ms 22,092 KB
testcase_87	AC	711 ms 21,804 KB
testcase_88	AC	761 ms 21,780 KB
testcase_89	AC	690 ms 22,080 KB
testcase_90	AC	717 ms 21,972 KB
testcase_91	AC	618 ms 22,140 KB
testcase_92	AC	703 ms 21,948 KB
testcase_93	AC	700 ms 21,900 KB
testcase_94	AC	725 ms 21,924 KB
testcase_95	AC	704 ms 22,044 KB
testcase_96	AC	794 ms 21,780 KB
testcase_97	AC	744 ms 21,912 KB
testcase_98	AC	744 ms 21,924 KB
testcase_99	AC	653 ms 21,936 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
#define _CRT_SECURE_NO_WARNINGS


#define SUBMIT 1
#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 1

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


constexpr
struct {
	double CENTER_RATE = 0.0001;

	double AREA_SPAWN_RATE = 1.5610493972303132;
	double PLAYER_COUNT_RATE = 3.556789586654154;
	double RANGE_CROSS_RATE = 13.779839605289654;
	double VALUE_TURN_RATE = 0.5376029821892172;

	int ESTIMATE_STEP_COUNT = 29;
	int USE_ESTIMATE_PHASE_TURN = 18;

} 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 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 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 {
	double B = 0;
	double C = 0;
	double F = 0;
	double G = 0;

	double phase = 0;

	void Add(int turn, int spawnCount) {
		double y = spawnCount - 1.5;
		double x = turn * 2 * M_PI / (double)T_MAX;
		B += sin(2 * x);
		C += cos(2 * x);
		F += y * sin(x);
		G += y * cos(x);

		auto CalcE = [&](double np) {
			return B / 2.0 * sin(2 * np) - C / 2.0 * cos(2 * np) - 2 * F * cos(np) - 2 * G * sin(np);

		};
		auto CalcDiff = [&](double np) {
			return B * cos(2 * np) + C * sin(2 * np) + 2 * F * sin(np) - 2 * G * cos(np);
		};
		auto CalcDiff2 = [&](double np) {
			return -B * sin(2 * np) + C * cos(2 * np) + 2 * F * cos(np) + 2 * G * sin(np);
		};

		double np = phase * 2 * M_PI / (double)T_MAX;
		REP(step, HYPER_PARAM.ESTIMATE_STEP_COUNT) {
			double dE = CalcDiff(np);
			double d2E = CalcDiff2(np);
			np = np - dE / d2E;
		}
		if (CalcE(np) > CalcE(np + M_PI)) {
			np += M_PI;
		}

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

};

struct Solver {
	array<queue<int>, S_MAX + 1> playerQueue_;		
	array<Group, S_MAX + 1> groups_;
	PhaseEstimater phaseEstimater_;



	void FinishGroup(Group& group) {
		group.Clear();
	}


	void Run() {


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


			joinPlayers.clear();

			RemoveScoreDownGroup();

			JoinOnGroup(joinPlayers);

			AssignNewGroup(joinPlayers);

			JoinGroup5(joinPlayers);


			server.TurnOutput(joinPlayers);
		}


	}

	void JoinGroup5(arr<pint>& joinPlayers) {

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

		vector<vector<double>> scoreTable(groupOrder.sz(), vector<double>(groupOrder.sz(), -1));
		vector<vector<pint>> rangeTable(groupOrder.sz(), vector<pint>(groupOrder.sz(), pint{ -1, -1 }));

		auto SetTable = [&](const Group& group, const pint& limitRange, int startOi, int curOi) {
			pint maxRange = { -1, -1 };
			double score = CalcMaxValueRange(group, maxRange, limitRange);
			VASSERT(maxRange.a >= 0 && maxRange.b >= 0);

			score += group.players.size() * HYPER_PARAM.PLAYER_COUNT_RATE;
			score -= group.CenterDist() * HYPER_PARAM.CENTER_RATE;

			score *= group.players.size();

			scoreTable[startOi][curOi] = score;
			rangeTable[startOi][curOi] = maxRange;

		};

#define ENABLE_HALF_LIMIT 0

		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 maxScore = -1;
		arr<s8> maxJoinStack;
		{
			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;
				}

				double score = scoreTable[startOi][oi];
				if (score < 0) {
					return;
				}

				{
					double rangeScore = 0;
					const pint& range = rangeTable[startOi][oi];
					if (range.a <= prevRange.b) {
						int crossCount = prevRange.b - range.a + 1;
						rangeScore = -crossCount * HYPER_PARAM.RANGE_CROSS_RATE;
					}

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

				if (score > 0) {
					dfs(dfs, prevRange, startOi, oi + 1, totalScore);
				}

			};
			DFS(DFS, pint{ -1, -1 }, 0, 0, 0);
		}

		s8 startOi = 0;
		for (int oi : maxJoinStack) {
			if (startOi != oi) {
				auto& group1 = groups_[groupOrder[startOi]];
				FOR(oi2, startOi + 1, oi + 1) {
					auto& group2 = groups_[groupOrder[oi2]];
					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()) {
					FinishGroup(group1);
				}
			}


			startOi = oi + 1;
		}
	}

	void JoinGroup3(arr<pint>& joinPlayers) {
		arr<int> groupOrder;
		array<int, S_MAX + 1> prevs;
		array<int, S_MAX + 1> nexts;
		prevs.fill(-1);
		nexts.fill(-1);
		int prev = -1;
		REP(gi, S_MAX + 1) {
			auto& group = groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}
			groupOrder.emplace_back(gi);
			prevs[gi] = prev;
			if (prev >= 0) {
				nexts[prev] = gi;
			}
			prev = gi;
		}

		auto RemoveLink = [&](int gi) {
			if (prevs[gi] >= 0) {
				nexts[prevs[gi]] = nexts[gi];
			}
			if (nexts[gi] >= 0) {
				prevs[nexts[gi]] = prevs[gi];
			}
			prevs[gi] = -1;
			nexts[gi] = -1;
		};



		array<int, S_MAX + 1> assignedGroups;
		assignedGroups.fill(-1);
		REP(oi, groupOrder.size()) {
			int gi = groupOrder[oi];
			auto& group = groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}
			FOR(si, group.minSkill, group.maxSkill + 1) {
				VASSERT(assignedGroups[si] == -1);		
				assignedGroups[si] = gi;
			}
		}

		while (true) {
			array<double, S_MAX + 1> singleScores;
			singleScores.fill(-1);
			for (int gi : groupOrder) {
				auto& group = groups_[gi];
				if (group.IsEmpty()) {
					continue;
				}

				int rangeLower = -1;
				int rangeUpper = -1;
				double score = CalcMaxValueRange(group, rangeLower, rangeUpper, assignedGroups);
				VASSERT(rangeLower >= 0);
				singleScores[gi] = score;
			}

			int giA = -1;
			int giB = -1;
			double maxUpScore = 0;

			REP(oi, groupOrder.size()) {
				int gi = groupOrder[oi];
				auto& group = groups_[gi];
				if (group.IsEmpty()) {
					continue;
				}

				CapacityArray<int, 2> side;
				if (prevs[gi] >= 0) {
					side.PushBack(prevs[gi]);
				}
				if (nexts[gi] >= 0) {
					side.PushBack(nexts[gi]);
				}
				for (int gi2 : side) {
					auto& group2 = groups_[gi2];
					if (group2.IsEmpty()) {
						continue;
					}
					if (group.players.size() + group2.players.size() > R_MAX) {
						continue;
					}

					auto joinedGroup1 = group;
					auto joinedGroup2 = group2;
					joinedGroup1.JoinGroup(joinedGroup2, server.turn);
					int rangeLower = -1;
					int rangeUpper = -1;
					double joinedScore = CalcMaxValueRange(joinedGroup1, rangeLower, rangeUpper, assignedGroups);
					joinedScore *= joinedGroup1.players.size();
					double baseScore = singleScores[gi] * group.players.size() + singleScores[gi2] * group2.players.size();
					double upScore = joinedScore - baseScore;

					if (upScore > maxUpScore) {
						giA = gi;
						giB = gi2;
						maxUpScore = upScore;
					}
				}
			}
			if (giA < 0) {
				break;
			}
			else {
				auto& group = groups_[giA];
				auto& group2 = groups_[giB];
				joinPlayers.emplace_back(pint{ group.players[0], group2.players[0] });
				group.JoinGroup(group2, server.turn);
				RemoveLink(giB);

				FOR(si, group.minSkill, group.maxSkill + 1) {
					if (assignedGroups[si] != giA && assignedGroups[si] != giB && assignedGroups[si] != -1) {
						VABORT();
					}
					assignedGroups[si] = giA;
				}

				if (group.IsFull()) {
					FOR(si, group.minSkill, group.maxSkill + 1) {
						if (assignedGroups[si] != giA) {
							VABORT();
						}
						assignedGroups[si] = -1;
					}
					FinishGroup(group);
					RemoveLink(giA);

				}
			}
		}
	}

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

		auto CheckMaxScore = [&](const Group& tmpGroup, int turn) {
			double score = tmpGroup.CalcScore();
			score -= (turn - server.turn) * HYPER_PARAM.VALUE_TURN_RATE;
			score /= tmpGroup.players.size();		
			if (score > maxScore) {
				maxScore = score;
			}
			return score;
		};

		double beforeScore = CheckMaxScore(group, server.turn);

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

		spawnRate *= HYPER_PARAM.AREA_SPAWN_RATE;

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

			double power = 0;
			FOR(turn, server.turn + 1, server.T) {
				double turnSpwanCount = 1.5;
				if (server.turn >= HYPER_PARAM.USE_ESTIMATE_PHASE_TURN) {
					turnSpwanCount = 1.5 + sin((turn + phaseEstimater_.phase) / (double)T_MAX * 2.0 * M_PI);
				}

				power += turnSpwanCount * spawnRate;
				if (power >= 1.0) {
					power -= 1.0;
					tmpGroup.AddPlayer(-1, siL, turn, turn);

					double score = CheckMaxScore(tmpGroup, turn);		


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

		return maxScore;
	}

	double CalcMaxValueSim(const Group& group, int siL, int siR) const {
		auto CalcNormalizeScore = [&](const Group& tmpGroup) {
			double score = tmpGroup.CalcScore();
			score /= tmpGroup.players.size();		
			return score;
		};

		if (group.IsFull()) {
			return CalcNormalizeScore(group);
		}


		double totalScore[5] = {};
		int count[5] = {};

		double spawnRate = 0;
		FOR(si, siL, siR + 1) {
			spawnRate += SkillSpawnRate[si];
		}
		BiasDistribution bd;
		bd.set(&SkillSpawnRate[siL], &SkillSpawnRate[siR + 1]);

		REP(step, 10) {
			auto tmpGroup = group;

			double power = 0;
			FOR(turn, server.turn + 1, server.T) {
				double turnSpwanCount = 1.5;
				if (server.turn >= HYPER_PARAM.USE_ESTIMATE_PHASE_TURN) {
					turnSpwanCount = 1.5 + sin((turn + phaseEstimater_.phase) / (double)T_MAX * 2.0 * M_PI);
				}

				power += turnSpwanCount * spawnRate;
				if (power >= 1.0) {
					power -= 1.0;

					int skill = siL + bd(Random::Instnce());

					tmpGroup.AddPlayer(-1, skill, turn, turn);
					double score = CalcNormalizeScore(tmpGroup);

					totalScore[tmpGroup.players.size()] += score;
					count[tmpGroup.players.size()] += 1;

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

		double maxScore = 0;
		FOR(i, 1, 5) {
			if (count[i] == 0) {
				continue;
			}
			double avg = totalScore[i] / (double)count[i];
			if (avg > maxScore) {
				maxScore = avg;
			}
		}

		return maxScore;
	}

	double CalcMaxValueRange(const Group& group, int& rangeLower, int& rangeUpper, const array<int, S_MAX + 1>& assignedGroups) const {
		int siL = group.minSkill;
		int siR = group.maxSkill;

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

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

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

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

			CapacityArray<int, 2> candidates;
			if (siL - 1 >= 0 && assignedGroups[siL - 1] == -1) {
				candidates.PushBack(siL - 1);
			}
			if (siR + 1 <= S_MAX && assignedGroups[siR + 1] == -1) {
				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;
			}
		}

		rangeLower = maxSiL;
		rangeUpper = maxSiR;

		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 = -1;

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

			if (siR - siL >= 14) {
				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;

		return maxScore;
	}

	void RemoveScoreDownGroup() {
		REP(gi, S_MAX + 1) {
			auto& group = 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) {
				FinishGroup(group);
			}
		}
	}


	void JoinOnGroup(arr<pint>& joinPlayers) {
		REP(gi, S_MAX + 1) {
			auto& group = groups_[gi];
			if (group.IsEmpty()) {
				continue;
			}

			while (true) {
				int outerSi = -1;
				int outerDist = -1;
				FOR(si, group.minSkill, group.maxSkill + 1) {
					if (playerQueue_[si].empty()) {
						continue;
					}
					int dist = abs(si - S_CENTER);
					if (dist > outerDist) {
						outerDist = dist;
						outerSi = si;
					}
				}
				if (outerSi < 0) {
					break;
				}

				int pi = playerQueue_[outerSi].front();
				playerQueue_[outerSi].pop();
				joinPlayers.emplace_back(pint{ group.players[0], pi });
				group.AddPlayer(pi, server.players[pi].skill, server.turn, server.players[pi].startTurn);
				if (group.IsFull()) {
					FinishGroup(group);
					break;
				}
			}
		}
	}

	void AssignNewGroup(arr<pint>& joinPlayers) {
		REP(si, S_MAX + 1) {
			auto& queue = playerQueue_[si];
			while (!queue.empty()) {
				int pi = queue.front();
				queue.pop();

				auto& group = groups_[si];
				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();
					joinPlayers.emplace_back(pint{ group.players[0], pi });
					group.AddPlayer(pi, server.players[pi].skill, server.turn, server.players[pi].startTurn);
				}
				if (group.IsFull()) {
					FinishGroup(group);

				}
			}
		}
	}

};

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

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

	}

};
yukicoder

結果

テストケース

ソースコード
