結果
| 問題 |
No.5004 Room Assignment
|
| コンテスト | |
| ユーザー |
 bowwowforeach
|
| 提出日時 | 2021-12-07 06:16:44 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.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 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 100 |
ソースコード
#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();
}
};