結果
問題 | No.5004 Room Assignment |
ユーザー |
![]() |
提出日時 | 2021-12-12 23:17:25 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#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 {returnx >= 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 {returnx < 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;constexprstruct {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 0struct 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#elseif (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 0double 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();}};