結果
問題 | No.5007 Steiner Space Travel |
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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;constexprstruct {} 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;}};