結果

問題 No.5004 Room Assignment
ユーザー bowwowforeach
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0