結果

問題 No.5007 Steiner Space Travel
ユーザー bowwowforeach
提出日時 2022-07-30 15:15:59
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 1,000 ms
コード長 33,011 bytes
コンパイル時間 2,769 ms
実行使用メモリ 3,484 KB
スコア 6,203,930
最終ジャッジ日時 2022-07-30 15:16:04
合計ジャッジ時間 4,486 ms
ジャッジサーバーID
(参考情報)
judge11 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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

#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0
#define TIME_LIMIT (950)
#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 1
#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)
#define ALL(x) (x).begin(),(x).end()
#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)
#define all(x) (x).begin(),(x).end()
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; }
#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;
using TimePoint = chrono::high_resolution_clock::time_point;
struct ChronoTimer {
private:
TimePoint startTime_;
TimePoint endTime_;
public:
inline void Init() {
startTime_ = chrono::high_resolution_clock::now();
}
inline void Start(int limit) {
endTime_ = startTime_ + chrono::milliseconds(limit);
}
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::high_resolution_clock::now() >= endTime_;
}
inline int ElapseTimeMs() const {
return (int)chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - startTime_).count();
}
inline int ElapseTimeUs() const {
return (int)chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - startTime_).count();
}
inline int LeftToUS(const TimePoint& limit) const {
return (int)chrono::duration_cast<chrono::microseconds>(limit - chrono::high_resolution_clock::now()).count();
}
inline double NowRate() const {
return (chrono::high_resolution_clock::now() - startTime_).count() / (double)(endTime_ - startTime_).count();
}
inline TimePoint Now() const {
return chrono::high_resolution_clock::now();
}
inline TimePoint EndTime() const {
return endTime_;
}
TimePoint GetLimitTimePointUs(int limit) const {
return startTime_ + chrono::microseconds(limit);
}
};
ChronoTimer 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);
}
#define VALIDATE_ABORT()
#define VALIDATE_ASSERT(exp)
#define VABORT() VALIDATE_ABORT()
#define VASSERT(exp) VALIDATE_ASSERT(exp)
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;
}
bool operator > (pr const& r) const {
return r < (*this);
}
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;
}
template <class C, class D>
auto operator + (pr<C, D> const& v) const {
return pr<decltype(a + v.a), decltype(b + v.b)>{ a + v.a, b + v.b };
}
template <class C, class D>
auto operator - (pr<C, D> const& v) const {
return pr<decltype(a - v.a), decltype(b - v.b)>{ a - v.a, b - v.b };
}
template <class C, class D>
explicit 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;
}
pr operator -() const {
return pr{ -x, -y };
}
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;
}
template <size_t I>
auto get() const {
if constexpr (I == 0) {
return x;
}
else if constexpr (I == 1) {
return y;
}
}
};
using pint = pr<int, int>;
using pdouble = pr<double, double>;
static_assert(is_pod<pint>::value, "not pod");
template <class A, class B>
struct tuple_size<pr<A, B>> : integral_constant<size_t, 2> {};
template <class A, class B>
struct tuple_element<0, pr<A, B>> { using type = A; };
template <class A, class B>
struct tuple_element<1, pr<A, B>> { using type = B; };
template <class A, class B, class C>
struct tr {
union {
A a;
A first;
A x;
};
union {
B b;
B second;
B y;
};
union {
C c;
C third;
C z;
};
bool operator == (tr const& r) const { return a == r.a && b == r.b && c == r.c; }
bool operator != (tr const& r) const { return !((*this) == r); }
bool operator < (tr const& r) const {
if (a == r.a) {
if (b == r.b) {
return c < r.c;
}
return b < r.b;
}
return a < r.a;
}
tr operator + (tr v) const { return tr(x, y, z) += v; }
tr operator - (tr v) const { return tr(x, y, z) -= v; }
tr operator - () const { return tr{ -x, -y, -z }; }
tr& operator += (tr v) {
x += v.x;
y += v.y;
z += v.z;
return *this;
}
tr& operator -= (tr v) {
x -= v.x;
y -= v.y;
z -= v.z;
return *this;
}
friend istream& operator>>(istream& is, tr& p) {
is >> p.a >> p.b >> p.c;
return is;
}
friend ostream& operator<<(ostream& os, tr const& p) {
os << p.a << " " << p.b << " " << p.c;
return os;
}
};
using tint = tr<int, int, int>;
static_assert(is_pod<tint>::value, "not pod");
template <class T>
struct arr : public vector<T> {
static arr<arr<T>> D2(int y, int x, T value) {
return arr<arr<T>>(y, arr<T>(x, value));
}
static arr<arr<arr<T>>> D3(int z, int y, int x, T value) {
return arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value)));
}
static arr<arr<arr<arr<T>>>> D4(int w, int z, int y, int x, T value) {
return arr<arr<arr<arr<T>>>>(w, arr<arr<arr<T>>>(z, arr<arr<T>>(y, arr<T>(x, value))));
}
static arr<T> Iota(int N, int value = 0) {
auto r = arr<T>(N);
r.iota(value);
return r;
}
arr() {}
arr(initializer_list<T> il) : vector<T>(il) {}
explicit arr(int n) : vector<T>(n) {}
arr(int n, T v) : vector<T>(n, v) {}
arr(const arr& r) : vector<T>(r) {}
arr(arr&& r) : vector<T>(move(r)) {}
arr& operator = (const arr& r) {
vector<T>::operator = (r);
return *this;
}
arr& operator = (arr&& r) {
vector<T>::operator = (move(r));
return *this;
}
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 (int)(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(); }
void iota(T startValue = 0) { ::iota(this->begin(), this->end(), startValue); }
void fill(T v) { ::fill(this->begin(), this->end(), v); }
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 (int)(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()); }
void slide_remove(int i) {
(*this)[i] = (*this)[sz() - 1];
this->pop_back();
}
void remove_idx(int i) {
this->erase(this->begin() + i);
}
void insert_idx(int i, const T& v) {
this->insert(this->begin() + i, v);
}
int findGE(const T& v) {
return lower_bound(v);
}
int findG(const T& v) {
return upper_bound(v);
}
int findLE(const T& v) {
return upper_bound(v) - 1;
}
int findL(const T& v) {
return lower_bound(v) - 1;
}
friend ostream& operator<<(ostream& os, const arr<T>& p) {
if (p.empty()) {
return os;
}
os << p[0];
FOR(i, 1, p.size()) {
os << " " << p[i];
}
return os;
}
};
using ints = arr<int>;
template <class T, int CAPACITY>
struct CapacityQueue {
private:
array<T, CAPACITY> ar = {};
int start = 0;
int end = 0;
public:
inline void clear() {
start = 0;
end = 0;
}
inline void push(const T& v) {
ar[end++] = v;
}
inline T* push() {
T* ptr = &ar[end];
++end;
return ptr;
}
inline const T& get() const {
return ar[start];
}
inline T pop() {
return ar[start++];
}
inline bool empty() const {
return start == end;
}
inline bool exist() const {
return start != end;
}
inline int size() const {
return end - start;
}
inline int total_push_count() const {
return end;
}
const T& operator[](int i) const{
return ar[i];
}
int end_size() const {
return end;
}
};
template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;
template <class T, int CAPACITY>
class CapacityArray {
static_assert(is_trivially_copyable<T>::value);
private:
array<T, CAPACITY> array_ = {};
int count_ = 0;
public:
CapacityArray() {
}
explicit CapacityArray(int count) {
resize(count);
}
bool operator == (const CapacityArray<T, CAPACITY>& r) const {
return memcmp(array_.data(), r.array_.data(), sizeof(T) * count_) == 0;
}
inline void clear() {
count_ = 0;
}
inline void Clear() {
clear();
}
inline void resize(int count) {
count_ = count;
}
inline void Resize(int count) {
resize(count);
}
inline void assign(int count, const T& e) {
count_ = count;
for (int i = 0; i < count; ++i) {
array_[i] = e;
}
}
const T* data() const {
return array_.data();
}
inline T* PushBack() {
return &array_[count_++];
}
inline void push_back(const T& e) {
array_[count_++] = e;
}
inline void PushBack(const T& e) {
push_back(e);
}
inline void pop_back() {
--count_;
}
inline void PopBack() {
pop_back();
}
T& front() {
return array_[0];
}
const T& front() const {
return array_[0];
}
T& back() {
return array_[count_ - 1];
}
const T& back() const {
return array_[count_ - 1];
}
inline void RemoveSlide(int i) {
array_[i] = array_[count_ - 1];
--count_;
}
inline int GetCount() const {
return count_;
}
inline int size() const {
return count_;
}
inline int sz() 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 MemInsert(int index, const T* mem, int count) {
if (index == count_) {
memcpy(array_.data() + index, mem, sizeof(T) * count);
count_ += count;
}
else {
memmove(array_.data() + index + count, array_.data() + index, sizeof(T) * (count_ - index));
memcpy(array_.data() + index, mem, sizeof(T) * count);
count_ += count;
}
}
void insert(int index, const T& value) {
MemInsert(index, &value, 1);
}
inline void Insert(int start, int end, const T* p, int size) {
int newEnd = start + size;
if (count_ - end > 0 && newEnd != end) {
memmove(array_.data() + newEnd, array_.data() + end, sizeof(T) * (count_ - end));
}
memcpy(array_.data() + start, p, sizeof(T) * size);
count_ -= end - start;
count_ += size;
}
inline void Remove(int start, int end) {
int size = end - start;
memmove(array_.data() + start, array_.data() + end, sizeof(T) * (count_ - end));
count_ -= size;
}
};
template <class T, int CAPACITY>
using CapArr = CapacityArray<T, CAPACITY>;
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();
}
};
template<class T, class COMPARERE>
struct PriorityQueue : public priority_queue<T, vector<T>, COMPARERE> {
template <class D>
void Cut(int size, D&& deleter) {
if ((int)this->c.size() > size) {
int orgSize = (int)this->c.size();
for (int i = size; i < orgSize; ++i) {
deleter(this->c[i]);
}
this->c.resize(size);
}
}
vector<T>& Container() {
return this->c;
}
void Cut(int size) {
if ((int)this->c.size() > size) {
this->c.resize(size);
}
}
void Clear() {
this->c.clear();
}
};
template <int S>
struct CheckMapS {
private:
array<u32, S> checked_ = {};
u32 mark_ = 1;
public:
void Clear() {
++mark_;
if (mark_ == 0) {
checked_ = {};
++mark_;
}
}
bool IsChecked(int i) const {
return checked_[i] == mark_;
}
void Check(int i) {
checked_[i] = mark_;
}
void Reset(int i) {
checked_[i] = mark_ - 1;
}
bool operator[](int i) const {
return checked_[i] == mark_;
}
bool operator == (const CheckMapS<S>& r) const {
REP(i, S) {
if (this->IsChecked(i) != r.IsChecked(i)) {
return false;
}
}
return true;
}
};
template <class T, int S>
struct CheckMapDataS {
private:
array<T, S> data_;
array<u32, S> checked_ = {};
u32 mark_ = 1;
public:
void Clear() {
++mark_;
if (mark_ == 0) {
checked_ = {};
++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 {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T& Ref(int i) {
VASSERT(checked_[i] == mark_);
return data_[i];
}
const T& Ref(int i) const {
VASSERT(checked_[i] == mark_);
return data_[i];
}
const T& operator[](int i) const {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T GetIf(int i, const T& defaultValue) const {
if (checked_[i] == mark_) {
return data_[i];
}
return defaultValue;
}
};
struct CheckMapD {
private:
vector<u32> checked_;
u32 mark_ = 1;
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_;
}
void Reset(int i) {
checked_[i] = mark_ - 1;
}
};
template <class T>
struct CheckMapDataD {
private:
vector<T> data_;
vector<u32> checked_;
u32 mark_ = 1;
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 {
VASSERT(checked_[i] == mark_);
return data_[i];
}
T& Ref(int i) {
VASSERT(checked_[i] == mark_);
return data_[i];
}
};
enum class Dir : int8_t {
L = 0,
U,
R,
D,
N,
Invalid,
};
constexpr array<Dir, 4> Dir4 = {
Dir::L,
Dir::U,
Dir::R,
Dir::D,
};
constexpr array<pint, 4> Around4 = { pint{-1, 0}, pint{0, -1}, pint{1, 0}, pint{0, 1} };
inline Dir RotateRight(Dir d) {
return Dir(((int)d + 1) % 4);
}
inline Dir RotateLeft(Dir d) {
return Dir(((int)d + 3) % 4);
}
inline Dir Back(Dir d) {
return Dir(s8(d) ^ 2);
}
bool IsHorizontal(Dir dir) {
return dir == Dir::L || dir == Dir::R;
}
bool IsVertical(Dir dir) {
return dir == Dir::U || dir == Dir::D;
}
inline Dir CalcDir(const pint& from, const pint& to) {
if (from.x > to.x) {
return Dir::L;
}
else if (from.y > to.y) {
return Dir::U;
}
else if (from.x < to.x) {
return Dir::R;
}
else if (from.y < to.y) {
return Dir::D;
}
else {
return Dir::N;
}
}
inline const string& DirString(Dir dir) {
static const string strs[6] = {
"LEFT",
"UP",
"RIGHT",
"DOWN",
"WAIT",
"INVALID",
};
return strs[(int)dir];
}
inline char DirToChar(Dir dir) {
static const char chars[6] = {
'L',
'U',
'R',
'D',
'N',
'*',
};
return chars[(int)dir];
}
inline const Dir CharToDir(char c) {
if (c == 'L') {
return Dir::L;
}
else if (c == 'U') {
return Dir::U;
}
else if (c == 'R') {
return Dir::R;
}
else if (c == 'D') {
return Dir::D;
}
else if (c == 'N') {
return Dir::N;
}
VABORT();
return Dir::Invalid;
}
template <class T, int CAP>
struct CCA {
private:
T ar[CAP];
int s;
public:
inline constexpr void push(const T& v) {
ar[s++] = v;
}
inline constexpr const T* begin() const {
return &ar[0];
}
inline constexpr const T* end() const {
return &ar[s];
}
inline constexpr const T& operator ()(int i) const {
return ar[i];
}
inline constexpr const T& operator [](int i) const {
return ar[i];
}
int size() const {
return s;
}
};
template <int W, int H, int AROUND_COUNT>
struct AroundMapS {
using CA = CCA<int, AROUND_COUNT>;
CA table[W * H];
constexpr AroundMapS(const array<pint, AROUND_COUNT>& aroundDirs) : table{} {
REP(cellId, W * H) {
pint p = { cellId % W, cellId / W };
for (const pint& a : aroundDirs) {
int x = p.a + a.a;
int y = p.b + a.b;
if (x >= 0 && x < W &&
y >= 0 && y < H) {
table[cellId].push(x + y * W);
}
}
}
}
inline constexpr const CA& operator ()(int id) const {
return table[id];
}
inline constexpr const CA& operator [](int id) const {
return table[id];
}
};
template <int AROUND_COUNT>
struct AroundMapD {
using CA = CCA<int, AROUND_COUNT>;
vector<CA> table_;
int width_ = 1;
void Init(int width, int height, const array<pint, AROUND_COUNT>& aroundDirs) {
width_ = width;
int count = width * height;
table_.clear();
table_.resize(count);
REP(i, count) {
pint p = { i % width, i / width };
for (const pint& a : aroundDirs) {
pint n = p + a;
if (n.a >= 0 && n.a < width &&
n.b >= 0 && n.b < height) {
table_[i].push(n.a + n.b * width);
}
}
}
}
inline const CA& operator[](int i) const {
return table_[i];
}
inline const CA& operator[](const pint& p) const {
return table_[p.x + p.y * width_];
}
};
template <int W, int H, int AROUND_COUNT>
struct DirMapS {
using CA = CCA<int, AROUND_COUNT>;
CA table[W * H];
constexpr DirMapS(const array<pint, AROUND_COUNT>& aroundDirs) : table{} {
REP(cellId, W * H) {
pint p = { cellId % W, cellId / W };
for (const pint& a : aroundDirs) {
int x = p.a + a.a;
int y = p.b + a.b;
int n = -1;
if (x >= 0 && x < W &&
y >= 0 && y < H) {
n = x + y * W;
}
table[cellId].push(n);
}
}
}
inline constexpr const CA& operator ()(int id) const {
return table[id];
}
inline constexpr const CA& operator [](int id) const {
return table[id];
}
};
#include <cstdint>
struct Xor64 {
using result_type = uint64_t;
static constexpr result_type min() { return 0; }
static constexpr result_type max() { return UINT64_MAX; }
private:
Xor64(const Xor64& r) = delete;
Xor64& operator =(const Xor64& r) = delete;
public:
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;
}
inline double GetDouble() {
return (*this)() / (double)UINT64_MAX;
}
};
struct Random {
static inline Xor64& Instnce() {
static Xor64 x;
return x;
}
static inline uint64_t Get() {
return Instnce()();
}
static inline uint64_t Get(uint64_t l, uint64_t r) {
return Instnce()(l, r);
}
static inline uint64_t Get(uint64_t r) {
return Instnce()(r);
}
static inline void Get2(uint64_t N, uint64_t& a, uint64_t& b) {
VASSERT(N >= 2);
a = Get(N);
b = Get(N - 1);
if (b >= a) {
++b;
}
}
static inline double GetDouble() {
return Get() / (double)UINT64_MAX;
}
static inline double GetDouble(double l, double r) {
return l + GetDouble() * (r - l);
}
};
#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue;
constexpr
struct {
} HYPER_PARAM;
auto& HP = HYPER_PARAM;
double ParamValue(double x, double a, double e) {
return a * pow(x, e);
}
template <int W, int H>
struct GridSystemS {
inline constexpr int ToId(int x, int y) const {
return x + W * y;
}
inline constexpr int ToId(const pint& p) const {
return p.x + W * p.y;
}
inline constexpr pint ToPos(int id) const {
return pint{ id % W, id / W };
}
inline int CalcL1Dist(const pint& a, const pint& b) const {
return abs(a.x - b.x) + abs(a.y - b.y);
}
inline int CalcL1Dist(int a, int b) const {
return CalcL1Dist(ToPos(a), ToPos(b));
}
inline int CalcL2Dist2(const pint& a, const pint& b) const {
return square(a.x - b.x) + square(a.y - b.y);
}
inline int CalcL2Dist2(int a, int b) const {
return CalcL2Dist2(ToPos(a), ToPos(b));
}
inline double CalcL2Dist(const pint& a, const pint& b) const {
return sqrt(CalcL2Dist2(a, b));
}
inline double CalcL2Dist(int a, int b) const {
return CalcL2Dist(ToPos(a), ToPos(b));
}
inline bool IsOut(int x, int y) const {
if (x < 0 || x >= W ||
y < 0 || y >= H) {
return true;
}
return false;
}
inline bool IsOut(const pint& p) const {
return IsOut(p.x, p.y);
}
inline bool IsIn(const pint& p) const {
return !IsOut(p);
}
inline int RotateRight90(int id) const {
pint p = ToPos(id);
return ToId(W - 1 - p.y, p.x);
}
inline Dir CalcDir(int from, int to) const {
if (from - 1 == to) {
return Dir::L;
}
else if (from - W == to) {
return Dir::U;
}
else if (from + 1 == to) {
return Dir::R;
}
else if (from + W == to) {
return Dir::D;
}
else {
VABORT();
}
return Dir::Invalid;
}
};
struct Action {
CapArr<pint, 8> Qs;
CapArr<pint, 1000> route;
};
constexpr int N = 100;
constexpr int M = 8;
constexpr int alpha = 5;
CapArr<pint, 100> Ps;
struct IOServer {
void Input(int argc, const char* argv[]) {
auto& is = cin;
int dummy;
is >> dummy >> dummy;
Ps.resize(N);
REP(i, N) {
is >> Ps[i].x >> Ps[i].y;
}
}
void Output(const Action& action) {
ostream& os = cout;
REP(i, M) {
os << action.Qs[i].x << " " << action.Qs[i].y << endl;
}
os << action.route.size() << endl;
REP(i, action.route.size()) {
os << action.route[i].a << " " << action.route[i].b + 1 << endl;
}
}
};
IOServer server;
struct Mat {
array<int, N* N> m_;
const int& operator()(pint p) const {
return m_[p.x + p.y * N];
}
int& operator()(pint p) {
return m_[p.x + p.y * N];
}
const int& operator()(int x, int y) const {
return m_[x + y * N];
}
int& operator()(int x, int y) {
return m_[x + y * N];
}
};
bool WarshallFloyd(Mat& mat, int inf) {
REP(k, N) {
REP(i, N) {
REP(j, N) {
if (mat(i, k) == inf || mat(k, j) == inf) {
continue;
}
chmin(mat(i, j), mat(i, k) + mat(k, j));
}
}
}
REP(i, N) {
if (mat(i, i) < 0) {
return false;
}
}
return true;
}
bool WarshallFloyd2(Mat& mat, int inf, Mat& next) {
REP(k, N) {
REP(i, N) {
REP(j, N) {
if (mat(i, k) == inf || mat(k, j) == inf) {
continue;
}
if (mat(i, j) > mat(i, k) + mat(k, j)) {
mat(i, j) = mat(i, k) + mat(k, j);
next(i, j) = next(i, k);
}
}
}
}
REP(i, N) {
if (mat(i, i) < 0) {
return false;
}
}
return true;
}
struct Solver {
void Run() {
Mat mat;
mat.m_.fill(INT_MAX);
REP(i, N) {
FOR(j, i, N) {
if (i == j) {
mat(i, j) = 0;
mat(j, i) = 0;
}
else {
pint sub = Ps[i] - Ps[j];
int cost = (square(sub.x) + square(sub.y)) * square(alpha);
mat(i, j) = cost;
mat(j, i) = cost;
}
}
}
Mat next;
REP(i, N) {
REP(j, N) {
next(i, j) = j;
}
}
WarshallFloyd2(mat, INT_MAX, next);
int S = 0;
int S2 = 0;
Action action;
auto AddRoute = [&](int start, int goal) {
int now = start;
for (int cur = next(start, goal); cur != goal; cur = next(cur, goal)) {
action.route.push_back(pint{ 1, cur });
pint sub = Ps[now] - Ps[cur];
int cost = (square(sub.x) + square(sub.y)) * square(alpha);
S2 += cost;
now = cur;
}
action.route.push_back(pint{ 1, goal });
pint sub = Ps[now] - Ps[goal];
int cost = (square(sub.x) + square(sub.y)) * square(alpha);
S2 += cost;
};
action.Qs.resize(M);
REP(i, M) {
action.Qs[i] = pint{};
}
array<bool, N> used = {};
used[0] = true;
int now = 0;
action.route.push_back(pint{1, now});
REP(loop, N - 1) {
int bestI = -1;
int bestCost = INT_MAX;
REP(i, N) {
if (used[i]) {
continue;
}
int cost = mat(now, i);
if (cost < bestCost) {
bestCost = cost;
bestI = i;
}
}
AddRoute(now, bestI);
now = bestI;
used[bestI] = true;
S += bestCost;
}
AddRoute(now, 0);
int cost = mat(now, 0);
S += cost;
now = 0;
server.Output(action);
}
};
struct Main {
void Run(int argc, const char* argv[]) {
timer.StartMs(TIME_LIMIT);
server.Input(argc, argv);
Solver* solver = new Solver;
solver->Run();
cerr << "time " << timer.ElapseTimeMs() << endl;
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0