Submission #42715311

---

Source Code Expand

#define CODETEST 0
#define OPTUNE 0
#define PERFORMANCE 0
#define EVAL 0
#define UNIT_TEST 0

#define TIME_LIMIT (1970)

#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



#define TIME_LIMIT_US (TIME_LIMIT * 1000)

#ifdef __clang_version__
#pragma clang diagnostic ignored "-Wunknown-pragmas"
#pragma clang diagnostic ignored "-Wunknown-warning-option"
#pragma clang diagnostic ignored "-Wmissing-braces"
#endif


#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"
#pragma GCC diagnostic ignored "-Wunused-function"
#pragma GCC diagnostic ignored "-Wunused-but-set-variable"
#endif

#define _USE_MATH_DEFINES
#ifdef __clang_version__

#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <cfenv>
#include <cinttypes>
#include <cstdint>
#include <cwchar>
#include <cwctype>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

#else
#include <bits/stdc++.h>
#endif

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()

template <class T, class U> inline void chmin(T& a, U&& b) { if (b < a) { a = b; } }
template <class T, class U> inline void chmax(T& a, U&& b) { if (a < b) { a = b; } }
template <class T, class U, class V> inline void clip(T& v, U&& lower, V&& upper) {
	if (v < lower) { v = lower; }
	else if (v > upper) { v = upper; }
}
template <class T> inline constexpr T square(T v) { return v * v; }

template <class T, int SIZE>
constexpr int len(const T(&)[SIZE]) { return SIZE; }

#define cauto const auto

#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();
		endTime_ = startTime_;
	}

	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();
	}

	void SetElapseTimeMs(int ms) {
		auto now = chrono::high_resolution_clock::now();
		auto limit = endTime_ - startTime_;
		startTime_ = now - chrono::milliseconds(ms);
		endTime_ = startTime_ + limit;
	}

	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 StartTime() const {
		return startTime_;
	}
	inline TimePoint EndTime() const {
		return endTime_;
	}

	TimePoint GetLimitTimePointUs(int limit) const {
		return startTime_ + chrono::microseconds(limit);
	}
};

TimePoint Now() {
	return chrono::high_resolution_clock::now();
}


template <class T>
void InstanceRun(int argc, const char* argv[]) {
	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 MemoryException {};


#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 x;
		A first;
	};
	union {
		B b;
		B y;
		B second;
	};

	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_trivially_copyable<pint>::value, "not trivially_copyable");

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; };

inline pdouble ToDouble(const pint& p) {
	return pdouble{ double(p.x), double(p.y) };
}
inline pint round(const pdouble& d) {
	return pint{ (int)round(d.x), (int)round(d.y) };
}
inline double norm(const pdouble& d) {
	return sqrt((d.x * d.x) + (d.y * d.y));
}
inline double norm(const pint& d) {
	return norm(ToDouble(d));
}
inline int norm2(const pint& d) {
	return square(d.x) + square(d.y);
}
inline pdouble normalized(const pdouble& d) {
	return d / norm(d);
}
inline double dot(const pdouble& a, const pdouble& b) {
	return a.x * b.x + a.y * b.y;
}
inline double cross(const pdouble& a, const pdouble& b) {
	return a.x * b.y - a.y * b.x;
}



template <class T, int CAP>
class CapArr {
private:
	friend class CapArr;

	static_assert(is_trivially_copyable<T>::value);

	T array_[CAP];
	int size_;

public:
	CapArr() {
		size_ = 0;
	}

	explicit CapArr(int count) {
		resize(count);
	}

	bool operator == (const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		REP(i, size_) {
			if (!(array_[i] == r.array_[i])) {
				return false;
			}
		}
		return true;
	}
	template <class U, int U_CAP>
	bool operator != (const CapArr<U, U_CAP>& r) const {
		return !(*this == r);
	}

	bool MemEqual(const CapArr<T, CAP>& r) const {
		if (size_ != r.size_) {
			return false;
		}
		return memcmp(data(), r.data(), sizeof(T) * size_) == 0;
	}

	constexpr int capacity() const {
		return CAP;
	}

	int size() const {
		return size_;
	}
	bool empty() const {
		return size_ == 0;
	}

	void clear() {
		size_ = 0;
	}

	void resize(int size) {
		size_ = size;
	}

	void assign(int size, const T& e) {
		size_ = size;
		if constexpr (sizeof(T) == 1) {
			memset(data(), e, size);
		}
		else {
			for (int i = 0; i < size; ++i) {
				array_[i] = e;
			}
		}
	}

	void MemAssign(int size, int byte) {
		size_ = size;
		memset(data(), byte, sizeof(T) * size);
	}

	void MemCopy(const CapArr<T, CAP>& from) {
		size_ = from.size_;
		memcpy(data(), from.data(), sizeof(T) * from.size_);
	}

	const T* data() const {
		return &array_[0];
	}
	T* data() {
		return &array_[0];
	}

	T& front() {
		return array_[0];
	}
	const T& front() const {
		return array_[0];
	}

	T& back() {
		return array_[size_ - 1];
	}
	const T& back() const {
		return array_[size_ - 1];
	}

	T& operator[](int index) {
		return array_[index];
	}

	const T& operator[](int index) const {
		return array_[index];
	}

	T* begin() {
		return &array_[0];
	}
	T* end() {
		return &array_[size_];
	}
	const T* begin() const {
		return &array_[0];
	}
	const T* end() const {
		return &array_[size_];
	}

	[[nodiscard]] T& push() {
		auto& ref = array_[size_];
		++size_;
		return ref;
	}
	void push(const T& e) {
		array_[size_] = e;
		++size_;
	}

	void pop() {
		--size_;
	}

	int find(const T& value) const {

		REP(i, size_) {
			if (array_[i] == value) {
				return i;
			}
		}
		return -1;
	}
	bool contains(const T& value) const {
		for (const auto& v : *this) {
			if (v == value) {
				return true;
			}
		}
		return false;
	}

	void insert(int index, const T& value) {
		insert(index, &value, 1);
	}

	void insert(int index, const T* mem, int size) {
		if (index == size_) {
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
		else {
			memmove(data() + index + size, data() + index, sizeof(T) * (size_ - index));
			memcpy(data() + index, mem, sizeof(T) * size);
			size_ += size;
		}
	}

	template <int RCAP>
	void append(const CapArr<T, RCAP>& r) {
		insert(size(), r.data(), r.size());
	}

	void remove(int index) {
		remove(index, index + 1);
	}

	void remove(int start, int end) {
		int size = end - start;
		memmove(data() + start, data() + end, sizeof(T) * (size_ - end));
		size_ -= size;
	}

	void RemoveSwap(int index) {
		array_[index] = array_[size_ - 1];
		--size_;
	}

	void RemoveInsert(int start, int end, const T* p, int size) {
		int newEnd = start + size;
		if (size_ - end > 0 && newEnd != end) {
			memmove(data() + newEnd, data() + end, sizeof(T) * (size_ - end));
		}

		memcpy(data() + start, p, sizeof(T) * size);

		size_ -= end - start;
		size_ += size;
	}

};




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;
		++end_;
	}

	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_;
	}
	int direct_start() const {
		return start_;
	}
	int direct_end() const {
		return end_;
	}

	inline auto begin() -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}
	inline auto begin() const -> decltype(ar_.begin()) {
		return ar_.begin() + start_;
	}
	inline auto end() const -> decltype(ar_.begin()) {
		return ar_.begin() + end_;
	}

	const T& front() const {
		return ar_[start_];
	}
	const T& back() const {
		return ar_[end_ - 1];
	}


};

template <class T, int CAPACITY>
using CapQue = CapacityQueue<T, CAPACITY>;






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];
    }
    T& operator[](int i) {
        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;
    }
};

template <class T, int CAP>
struct CapacitySet {
private:
	CapArr<T, CAP> elemens;
	CheckMapDataS<T, CAP> indexTable;

public:
	CapacitySet() {
	}

	constexpr int capacity() {
		return CAP;
	}

	void Fill() {
		indexTable.Clear();
		elemens.resize(CAP);
		iota(ALL(elemens), 0);
		REP(i, CAP) {
			indexTable.Set(i, i);
		}
	}

	void Clear() {
		elemens.clear();
		indexTable.Clear();
	}

	void Add(T ai) {
		indexTable.Set(ai, elemens.size());
		elemens.push(ai);
	}

	void ForceAdd(T ai) {
		if (indexTable.IsChecked(ai)) {
			return;
		}
		indexTable.Set(ai, elemens.size());
		elemens.push(ai);
	}

	void Remove(int ai) {
		T removeIndex = indexTable[ai];
		T lastIndex = elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.pop();
		indexTable.Reset(ai);
	}

	void ForceRemove(T ai) {
		if (!indexTable.IsChecked(ai)) {
			return;
		}
		T removeIndex = indexTable[ai];
		T lastIndex = elemens.size() - 1;

		if (removeIndex != lastIndex) {
			elemens[removeIndex] = elemens[lastIndex];
			indexTable.Set(elemens[lastIndex], removeIndex);
		}
		elemens.pop();
		indexTable.Reset(ai);
	}

	bool IsContain(T ai) const {
		return indexTable.IsChecked(ai);
	}

	int size() const {
		return elemens.size();
	}
	bool empty() const {
		return elemens.empty();
	}

	T At(int index) const {
		return elemens[index];
	}

	T operator[](int index) const {
		return elemens[index];
	}

	auto begin() -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() -> decltype(elemens.begin()) {
		return elemens.end();
	}
	auto begin() const -> decltype(elemens.begin()) {
		return elemens.begin();
	}
	auto end() const -> decltype(elemens.begin()) {
		return elemens.end();
	}
};
template <class T, int CAP>
using CapSet = CapacitySet<T, CAP>;



template<class T, class COMPARERE = less<T>>
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();
	}
};


#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;
	}
	inline bool GetProb(double E) {
		return GetDouble() <= E;
	}
};



#define PARAM_CATEGORY(NAME, VALUE, ...) int NAME = VALUE;
#define PARAM_INT(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) int NAME = VALUE;
#define PARAM_DOUBLE(NAME, VALUE, LOWER_VALUE, UPPER_VALUE) double NAME = VALUE;


#define PARAM_LOWER(v)
#define PARAM_UPPER(v)
#define START_TUNING
#define END_TUNING

#define PARAM_GROUP(NAME)
#define PARAM_GROUP_END




constexpr
struct {





	PARAM_INT(InitialRandLevelCount, 41, 8, 36);PARAM_LOWER(0);
	PARAM_INT(InitialGreedyLevelCount, 0, 0, 8);PARAM_LOWER(0);
	PARAM_INT(InitialMaxLevelCount, 5, 0, 8);PARAM_LOWER(0);

	PARAM_DOUBLE(StartTemp, 13852.554230322956, 13000.0, 15000.0);PARAM_LOWER(0.0);
	PARAM_DOUBLE(EndTemp, 568.340811127415, 500.0, 600.0);PARAM_LOWER(0.0);
	PARAM_INT(RollbackCount, 784, 600, 900);PARAM_LOWER(10);
	PARAM_DOUBLE(RollbackNextMulti, 1.0376129373220926, 1.0, 1.05);PARAM_LOWER(1.0);

	START_TUNING;
	PARAM_INT(TransitionUp, 15, 20, 30);PARAM_LOWER(0);
	END_TUNING;

	PARAM_INT(TransitionUpMulti, 0, 0, 10);PARAM_LOWER(0);
	PARAM_INT(TransitionDownMulti, 0, 0, 10);PARAM_LOWER(0);

	PARAM_INT(TransitionDown, 30, 8, 18);PARAM_LOWER(0);
} HP;

constexpr int N = 100;			
constexpr int M_Max = 300;		
constexpr int K_Max = 5000;		

int M = 0;
int K = 0;

template <class T>
using NArr = CapArr<T, N>;

template <class T>
using MArr = CapArr<T, M_Max>;

template <class T>
using KArr = CapArr<T, K_Max>;




struct Result {
	NArr<int> powers;	
	MArr<bool> ons;		
};

struct Edge {
	array<int, 2> uv;
	int w;			
};

struct Around {
	int vi;
	int ei;
	int w;
};

struct IOServer {
	NArr<pint> srcs_;
	MArr<Edge> edges_;
	KArr<pint> dsts_;
	NArr<CapArr<Around, 32>> arounds_;		

	void InitInput(ChronoTimer& timer) {
		istream& is = cin;
		int dummy;
		is >> dummy;	
		timer.Init();		

		is >> M >> K;

		srcs_.resize(N);
		REP(i, N) {
			is >> srcs_[i].x >> srcs_[i].y;
		}

		edges_.resize(M);
		arounds_.resize(N);
		REP(i, M) {
			auto& e = edges_[i];
			is >> e.uv[0] >> e.uv[1] >> e.w;
			--e.uv[0];
			--e.uv[1];

			{
				auto& a = arounds_[e.uv[0]].push();
				a.ei = i;
				a.vi = e.uv[1];
				a.w = e.w;
			}
			{
				auto& a = arounds_[e.uv[1]].push();
				a.ei = i;
				a.vi = e.uv[0];
				a.w = e.w;
			}
		}

		dsts_.resize(K);
		REP(i, K) {
			is >> dsts_[i].x >> dsts_[i].y;
		}
	}

	void Output(const Result& result) {
		ostream& os = cout;
		REP(i, N) {
			os << result.powers[i] << " ";
		}
		os << endl;
		REP(i, M) {
			os << (result.ons[i] ? 1 : 0) << " ";
		}
		os << endl;

	}

	void Finalize() {
	}
};
IOServer server;

#define USE_SA_POINT_FILTER 1
#define USE_SA_ROLLBACK 1

#define DOUBLE_PHASE 0
#define GREADY_UPDATE 0
#define USE_LEVEL_CHANGE_COST 0



struct RandomTable {
	vector<int> table_;

	void push(int value, int count) {
		table_.reserve(table_.size() + count);
		REP(i, count) {
			table_.emplace_back(value);
		}
	}

	template <class ENGINE>
	int operator()(ENGINE& engine) {
		return table_[engine() % table_.size()];
	}
};

#define USE_ACCEPT_SCORE 0



struct SAChecker {
	Xor64* rand_ = nullptr;
	double* totalMaxScore_ = nullptr;

	double temp = 0;		
	double divTemp = 0;

	double currentScore = 0;
	double maxScore = 0;

	int noMaxUpdateCount = 0;				
	int nextRollbackCheckCount = INT_MAX;	

	inline bool operator()(double newScore) {
		++noMaxUpdateCount;

		if (newScore > currentScore) {
			currentScore = newScore;
			if (newScore > maxScore) {
				maxScore = newScore;
				noMaxUpdateCount = 0;

				if (newScore > *totalMaxScore_) {
					*totalMaxScore_ = newScore;
				}
			}

			return true;
		}

		else if (newScore == currentScore) {
			return true;
		}

		else {
			if (exp((newScore - currentScore) * divTemp) * UINT32_MAX > (*rand_)(UINT32_MAX)) {
				currentScore = newScore;
				return true;
			}
			else {
				return false;
			}
		}
	}

};

template <class F>
struct SATransition {
	const char* name;
	F func;
	int weight;
};
template <class F>
auto MakeTransition(const char* name, F&& func, int weight) {
	return SATransition<F>{ name, func, weight };
}
#define MAKE_TRANS(func, weight) MakeTransition(#func, [&](SAChecker& sac, State& state) { func(sa, sac, state); }, weight)

struct SimulatedAnnealing {
	vector<SAChecker> checkers;

	double totalMaxScore = 0;				
	double timeRate = 0;				
	double temp = 0;					
	double divTemp = 0;					


	Xor64 rand_;

	double startTemp_ = 200;					
	double endTemp_ = 1;						
	int stepLoopCount = 1000;					

	double rollbackStartRate_ = 999.0;			
	int rollbackCount_ = INT_MAX;				
	double rollbackNextMulti_ = 1.1;			


public:
	template <class STATE, class... TRANSITION>
	void Run2(ChronoTimer& timer, vector<STATE>& states, tuple<SATransition<TRANSITION>...>& transitions) {

		vector<STATE> maxStates = states;
		checkers.resize(states.size());
		totalMaxScore = states[0].EvalScore();
		REP(pi, checkers.size()) {
			auto& checker = checkers[pi];
			checker.rand_ = &rand_;
			checker.totalMaxScore_ = &totalMaxScore;

			checker.temp = 0;
			checker.divTemp = 0;
			checker.currentScore = states[pi].EvalScore();
			checker.maxScore = checker.currentScore;
			checker.noMaxUpdateCount = 0;
			checker.nextRollbackCheckCount = rollbackCount_;

			chmax(totalMaxScore, checker.maxScore);
		}

		RandomTable randTable;
		TupleLoop(transitions, [&](auto&& e, size_t i) {
			randTable.push((int)i, e.weight);
		});

		const auto startTime = timer.Now();
		const auto endTime = timer.EndTime();
		const double subTimeCountDiv = 1.0 / (double)(endTime - startTime).count();

		vector<int> pis(states.size());
		iota(ALL(pis), 0);

		bool forceEnd = false;
		while (!timer.IsOver()) {
			timeRate = (timer.Now() - startTime).count() * subTimeCountDiv;
			temp = startTemp_ * std::pow(endTemp_ / startTemp_, timeRate);		
			divTemp = 1.0 / temp;
			for (auto& checker : checkers) {
				checker.temp = temp;
				checker.divTemp = divTemp;
			}


			for (int rp = 0; rp < stepLoopCount; ++rp) {
				int ti = (int)randTable(rand_);

				auto exec = [&](auto&& e, size_t i) {
					for (int pi : pis) {
						auto& checker = checkers[pi];
						e.func(checker, states[pi]);

						if (states[pi].RawScore() > maxStates[pi].RawScore()) {
							maxStates[pi] = states[pi];
						}
						else {
							if (timeRate >= rollbackStartRate_) {
								if (checker.noMaxUpdateCount >= checker.nextRollbackCheckCount) {
									states[pi] = maxStates[pi];
									checker.noMaxUpdateCount = 0;
									checker.nextRollbackCheckCount = (int)round(checker.nextRollbackCheckCount * rollbackNextMulti_);
								}
							}
						}
					}
				};

				TupleAccess(transitions, ti, exec);
			}
			if (forceEnd) {
				break;
			}

			{
				constexpr double start = 0.2;
				constexpr double end = 1.0;
				int targetPointCount = (int)states.size();
				if (timeRate >= end) {
					targetPointCount = 1;
				}
				else if (timeRate >= start) {
					double r = 1.0 - (timeRate - start) / (end - start);		
					targetPointCount = 1 + (int)floor(states.size() * r);
				}
				if ((int)pis.size() > targetPointCount) {
					sort(ALL(pis), [&](int a, int b) {
						return checkers[a].maxScore > checkers[b].maxScore;
					});
					pis.resize(targetPointCount);
				}
			}
		}

	}

	void ForceUpdate() {
	}

private:
	template <class Tuple, class Func>
	void TupleLoop(Tuple & t, Func && f) {
		TupleLoop2(t, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
	}
	template <class Tuple, class Func, size_t... Indics>
	void TupleLoop2(Tuple & t, Func && f, index_sequence<Indics...>) {
		using swallow = int[];
		(void)swallow {
			(TupleLoop3<Tuple, Func, Indics>(t, f), 0)...
		};
	}
	template <class Tuple, class Func, size_t Index>
	void TupleLoop3(Tuple & t, Func & f) {
		f(get<Index>(t), Index);
	}

	template <class Tuple, class Func>
	void TupleAccess(Tuple & t, int i, Func && f) {
		TupleAccess2(t, i, forward<Func>(f), make_index_sequence<tuple_size<Tuple>::value>{});
	}
	template <class Tuple, class Func, size_t... Indics>
	void TupleAccess2(Tuple & t, int i, Func && f, index_sequence<Indics...>) {
		using swallow = int[];
		(void)swallow {
			(TupleAccess3<Tuple, Func, Indics>(t, i, f), 0)...
		};
	}
	template <class Tuple, class Func, size_t Index>
	void TupleAccess3(Tuple & t, int i, Func & f) {
		if (i == Index) {
			f(get<Index>(t), Index);
		}
	}

};

using VPath = NArr<int>;		
using EPath = NArr<int>;		

struct PathFinder {
	NArr<NArr<int>> costs_;
	NArr<NArr<int>> froms_;
	NArr<NArr<int>> edges_;		

	void Init() {
		struct Node {
			int point;
			int totalCost;
			bool operator < (Node const& n) const {
				return totalCost > n.totalCost;
			}
		};

		PriorityQueue<Node> que;

		costs_.resize(N);
		froms_.resize(N);
		edges_.resize(N);

		REP(start, N) {
			auto& costs = costs_[start];
			auto& froms = froms_[start];
			auto& edges = edges_[start];
			costs.assign(N, INT_MAX);
			froms.assign(N, -1);
			edges.assign(N, -1);

			costs[start] = 0;
			que.push(Node{ start, 0 });

			while (!que.empty()) {
				Node node = que.top();
				que.pop();

				if (costs[node.point] != node.totalCost) {
					continue;
				}

				for (cauto& a : server.arounds_[node.point]) {
					int next = a.vi;
					int cost = a.w;

					VASSERT((s64)node.totalCost + (s64)cost <= INT_MAX);
					int nextCost = node.totalCost + cost;
					if (nextCost < costs[next]) {
						costs[next] = nextCost;
						froms[next] = node.point;
						edges[next] = a.ei;
						que.push(Node{ next, nextCost });
					}
				}
			}
		}
	}

	int Cost(int a, int b) const {
		return costs_[a][b];
	}



	void GetPath(int from, int to, VPath& vis, VPath& eis) const {
		vis.clear();
		eis.clear();

		cauto& froms = froms_[to];
		cauto& edges = edges_[to];
		int cur = from;
		while (cur >= 0) {
			vis.push(cur);
			if (edges[cur] >= 0) {
				eis.push(edges[cur]);
			}
			cur = froms[cur];
		}
	}
	void GetPathNoFrom(int from, int to, VPath& vis, VPath& eis) const {
		vis.clear();
		eis.clear();

		cauto& froms = froms_[to];
		cauto& edges = edges_[to];
		int cur = from;
		while (cur >= 0) {
			if (cur != from) {
				vis.push(cur);
			}
			if (edges[cur] >= 0) {
				eis.push(edges[cur]);
			}
			cur = froms[cur];
		}
	}
};
#define USE_COMPETITORS 1



struct Level2 {
	pint range;	
	int power;
	int powerCost;
};
struct Caster {
	KArr<int> kis;				
	KArr<int> ki2li;			
	KArr<Level2> levels;		
};

struct Area {
	KArr<NArr<pint>> nearLevels_;		
	NArr<Caster> casters_;

	NArr<NArr<int>> competitors_;		


	void Init() {
		array<int, 5001> powerCosts;
		REP(power, 5001) {
			powerCosts[power] = square(power);
		}

		KArr<int> dists;
		nearLevels_.resize(K);
		casters_.resize(N);

		REP(start, N) {
			auto& caster = casters_[start];
			caster.kis.clear();
			caster.levels.clear();

			dists.assign(K, -1);
			cauto& src = server.srcs_[start];
			REP(k, K) {
				cauto& dst = server.dsts_[k];
				s64 d2 = square(src.x - dst.x) + square(src.y - dst.y);
				if (d2 > square(5000)) {
					continue;
				}
				s64 lower = (s64)sqrt(d2);
				FOR(d, lower, 5001) {
					if (d2 <= square(d)) {
						caster.kis.push(k);
						dists[k] = d;
						break;
					}
				}
			}

			sort(ALL(caster.kis), [&](int a, int b) {
				return dists[a] < dists[b];
				});



			caster.ki2li.assign(K, -1);

			int prevD = -1;
			{
				auto& level = caster.levels.push();
				level.power = 0;
				level.powerCost = 0;
				level.range.a = 0;
				level.range.b = 0;
			}
			REP(i, caster.kis.size()) {
				int ki = caster.kis[i];
				int d = dists[ki];
				if (d != prevD) {
					if (prevD >= 0) {
						caster.levels.back().range.b = i;
					}
					auto& level = caster.levels.push();
					level.power = d;
					level.powerCost = square(d);
					level.range.a = i;
					level.range.b = -1;
				}
				nearLevels_[ki].push(pint{ caster.levels.size() - 1, start });
				caster.ki2li[ki] = caster.levels.size() - 1;
				prevD = d;
			}
			if (prevD >= 0) {
				caster.levels.back().range.b = caster.kis.size();
			}
		}

		REP(ki, K) {
			sort(ALL(nearLevels_[ki]), [&](const pint& a, const pint& b) {
				return casters_[a.second].levels[a.first].power < casters_[b.second].levels[b.first].power;
				});
		}


		array<bitset<N>, N> competitorsBit;
		REP(ki, K) {
			cauto& n = nearLevels_[ki];
			REP(i, n.size()) {
				int vi = n[i].second;
				FOR(j, i + 1, n.size()) {
					int vj = n[j].second;
					competitorsBit[vi].set(vj);
					competitorsBit[vj].set(vi);
				}
			}
		}
		competitors_.resize(N);
		REP(vi, N) {
			cauto& bit = competitorsBit[vi];
			REP(vj, N) {
				if (bit.test(vj)) {
					competitors_[vi].push(vj);
				}
			}
		}
	}


	int GetPower(int vi, int li) const {
		return casters_[vi].levels[li].power;
	}
	int GetPowerCost(int vi, int li) const {
		return casters_[vi].levels[li].powerCost;
	}

};


struct ChoiceTable {
private:
	vector<int> table_;
	int m_ = 0;

public:
	void Init(int n) {
		table_.resize(n);
		iota(table_.begin(), table_.end(), 0);
		m_ = 0;
	}
	void Choice(int m, Xor64& rand) {
		VASSERT(m <= (int)table_.size());
		REP(i, m) {
			swap(table_[i], table_[i + rand(table_.size() - i)]);
		}
		m_ = m;
	}

	using iterator = vector<int>::iterator;
	using const_iterator = vector<int>::const_iterator;

	inline const_iterator begin() const {
		return table_.begin();
	}
	inline const_iterator end() const {
		return table_.begin() + m_;
	}
	inline iterator begin() {
		return table_.begin();
	}
	inline iterator end() {
		return table_.begin() + m_;
	}
	inline int operator [](int index) const {
		return table_[index];
	}
};

template <int CAP>
struct ChoiceTableS {
private:
	CapArr<int, CAP> table_;
	int m_ = 0;

public:
	void Init(int n) {
		table_.resize(n);
		iota(table_.begin(), table_.end(), 0);
		m_ = 0;
	}
	void Choice(int m, Xor64& rand) {
		VASSERT(m <= (int)table_.size());
		REP(i, m) {
			swap(table_[i], table_[i + (int)rand(table_.size() - i)]);
		}
		m_ = m;
	}

	using iterator = vector<int>::iterator;
	using const_iterator = vector<int>::const_iterator;

	inline const_iterator begin() const {
		return table_.begin();
	}
	inline const_iterator end() const {
		return table_.begin() + m_;
	}
	inline iterator begin() {
		return table_.begin();
	}
	inline iterator end() {
		return table_.begin() + m_;
	}
	inline int operator [](int index) const {
		return table_[index];
	}
};

struct State {
	NArr<int> levels;	
	KArr<s8> refCounts;		
	s64 edgeCost;
	s64 powerCost;
	NArr<s8> useVis;		

	s64 rawScore;
	double score;

	void Init() {
		levels.assign(N, 0);
		refCounts.assign(K, 0);
		edgeCost = 0;
		powerCost = 0;
		useVis.clear();

		rawScore = 0;
		score = 0;
	}
	double EvalScore() const {
		return score;
	}
	double RawScore() const {
		return score;
	}
};
static constexpr int StateSize = sizeof(State);

struct Solver {
	Xor64 rand_;

	PathFinder pathFinder_;
	Area area_;

	NArr<int> easyCost_;		

	State bestState_;

	void CheckMaxScore(const State& state) {
		if (state.rawScore > bestState_.rawScore) {
			bestState_ = state;
		}
	}

	void Run(ChronoTimer& timer) {
		{

			pathFinder_.Init();
			area_.Init();
			MakeAllTree(easyCost_);


		}

		vector<State> states;
		InitState(states);
		bestState_ = states.front();

		timer.Start(TIME_LIMIT);

		SimulatedAnnealing sa;
		{
			sa.startTemp_ = HP.StartTemp;
			sa.endTemp_ = HP.EndTemp;
			sa.stepLoopCount = 100;

			sa.rollbackStartRate_ = 0.0;
			sa.rollbackCount_ = HP.RollbackCount;
			sa.rollbackNextMulti_ = HP.RollbackNextMulti;

			auto transitions = make_tuple(
				MAKE_TRANS(Transition_DownPower, HP.TransitionDown)
				, MAKE_TRANS(Transition_UpPower, HP.TransitionUp)
			);
			sa.Run2(timer, states, transitions);
		}

		s64 bestEdgeCost = INT64_MAX;
		MArr<bool> bestOns;
		MArr<bool> ons;
		REP(vi, N) {
			if (bestState_.levels[vi] > 0) {
				s64 edgeCost = MakeTreeWithStart(bestState_.levels, ons, vi);
				if (edgeCost < bestEdgeCost) {
					bestEdgeCost = edgeCost;
					bestOns = ons;
				}
			}
		}

		Result result;
		result.powers.resize(N);
		REP(i, N) {
			result.powers[i] = area_.GetPower(i, bestState_.levels[i]);
		}
		result.ons = bestOns;

		server.Output(result);
	}

	void InitState(vector<State>& states) {
		int StateCount = HP.InitialGreedyLevelCount + HP.InitialMaxLevelCount + HP.InitialRandLevelCount;
		states.resize(StateCount);

		int si = 0;
		REP(i, HP.InitialGreedyLevelCount) {
			State& state = states[si];
			state.Init();
			InitLevelGreedy(state.levels);
			InitOther(state);
			++si;
		}

		if (HP.InitialMaxLevelCount > 0) {
			State& baseState = states[si];
			{
				baseState.Init();
				InitLevelMax(baseState.levels);
				InitOther(baseState);
				++si;
			}

			REP(i, HP.InitialMaxLevelCount - 1) {
				states[si] = baseState;
				++si;
			}
		}

		REP(i, HP.InitialRandLevelCount) {
			State& state = states[si];
			state.Init();
			InitLevelRand(state.levels);
			InitOther(state);
			++si;
		}

		VASSERT(si == StateCount);
	}

	s64 MakeTree(const NArr<int>& levels) {
		struct Node {
			int to;
			int cost;

			bool operator < (const Node& r) const {
				return cost > r.cost;
			}
		};

		static NArr<s8> terminals;
		static NArr<int> costs;		
		static NArr<int> froms;
		costs.assign(N, INT_MAX);
		froms.assign(N, -1);

		s64 totalCost = 0;
		int nextVi = 0;
		terminals.clear();
		terminals.push(0);
		FOR(ni, 1, N) {
			if (levels[ni] > 0) {
				terminals.push(ni);
			}
		}
		int nextTi = (int)rand_(terminals.size());

		while (nextTi >= 0) {
			static VPath vis;
			const int nextVi = terminals[nextTi];
			int from = froms[nextVi];
			if (from < 0) {
				vis.clear();
				vis.push(nextVi);
				terminals.RemoveSwap(nextTi);
			}
			else {
				vis.clear();
				cauto& froms = pathFinder_.froms_[from];
				cauto& edges = pathFinder_.edges_[from];
				int cur = nextVi;
				while (cur != from) {
					vis.push(cur);

					int ei = edges[cur];
					VASSERT(ei >= 0);
					totalCost += server.edges_[ei].w;

					cur = froms[cur];
				}
				terminals.RemoveSwap(nextTi);
			}

			int bestCost = INT_MAX;
			nextTi = -1;
			REP(ti, terminals.size()) {
				int ni = terminals[ti];
				int minCost = costs[ni];
				int minCi = -1;
				for (int ci : vis) {
					VASSERT(levels[ni] >= 0);

					int cost = pathFinder_.Cost(ci, ni);
					if (cost < minCost) {
						minCost = cost;
						minCi = ci;
					}
				}
				if (minCi >= 0) {
					costs[ni] = minCost;
					froms[ni] = minCi;
				}
				if (minCost < bestCost) {
					bestCost = minCost;
					nextTi = ti;
				}
			}
			VASSERT(terminals.empty() || nextTi >= 0);
		}

		return totalCost;
	}

	s64 MakeTreeWithStart(const NArr<int>& levels, MArr<bool>& ons, int start) {
		ons.assign(M, false);

		struct Node {
			int to;
			int cost;

			bool operator < (const Node& r) const {
				return cost > r.cost;
			}
		};

		static CapSet<s8, N> lefts;
		static NArr<int> costs;		
		static NArr<int> froms;
		costs.assign(N, INT_MAX);
		froms.assign(N, -1);

		s64 totalCost = 0;
		int nextVi = 0;
		lefts.Clear();
		lefts.Add(0);
		FOR(ni, 1, N) {
			if (levels[ni] > 0) {
				lefts.Add(ni);
			}
		}
		nextVi = start;

		while (!lefts.empty()) {
			static VPath vis;
			int from = froms[nextVi];
			if (from < 0) {
				vis.clear();
				vis.push(nextVi);
				lefts.Remove(nextVi);
			}
			else {
				vis.clear();
				cauto& froms = pathFinder_.froms_[from];
				cauto& edges = pathFinder_.edges_[from];
				int cur = nextVi;
				while (cur != from) {
					vis.push(cur);
					lefts.ForceRemove(cur);

					int ei = edges[cur];
					VASSERT(ei >= 0);
					ons[ei] = true;
					totalCost += server.edges_[ei].w;

					cur = froms[cur];
				}
			}

			int bestCost = INT_MAX;
			nextVi = -1;
			for (int ni : lefts) {
				int minCost = costs[ni];
				int minCi = -1;
				for (int ci : vis) {
					VASSERT(levels[ni] >= 0);

					int cost = pathFinder_.Cost(ci, ni);
					if (cost < minCost) {
						minCost = cost;
						minCi = ci;
					}
				}
				if (minCi >= 0) {
					costs[ni] = minCost;
					froms[ni] = minCi;
				}
				if (minCost < bestCost) {
					bestCost = minCost;
					nextVi = ni;
				}
			}
			VASSERT(lefts.empty() || nextVi >= 0);
		}

		return totalCost;
	}


	void MakeAllTree(NArr<int>& fromCosts) {
		struct Node {
			int to;
			int cost;

			bool operator < (const Node& r) const {
				return cost > r.cost;
			}
		};

		static PriorityQueue<Node> que;
		que.Clear();
		que.push({ 0, 0 });

		NArr<int>& costs = fromCosts;		
		static NArr<int> froms;
		static NArr<bool> used;
		costs.assign(N, INT_MAX);
		froms.assign(N, -1);
		used.assign(N, false);

		while (!que.empty()) {
			Node node = que.top();
			que.pop();

			if (used[node.to]) {
				continue;
			}
			used[node.to] = true;

			fromCosts[node.to] = node.cost;

			int ci = node.to;
			for (cauto& ar : server.arounds_[node.to]) {
				int ni = ar.vi;
				if (!used[ni]) {
					int cost = pathFinder_.Cost(ci, ni);
					if (cost < costs[ni]) {
						costs[ni] = cost;
						que.push(Node{ ni, cost });
					}
				}
			}
		}
	}

	s64 EasyEdgeCost(const NArr<int>& levels) {
		s64 cost = 0;
		REP(i, N) {
			if (levels[i] > 0) {
				cost += easyCost_[i];
			}
		}
		return cost;
	}

	void InitLevelGreedy(NArr<int>& levels) {
		static KArr<int> kis;
		if (kis.empty()) {
			kis.resize(K);
			iota(ALL(kis), 0);
		}
		shuffle(ALL(kis), rand_);

		for (int ki : kis) {
			cauto& srcs = area_.nearLevels_[ki];
			int bestVi = -1;
			int bestLevel = 0;
			int bestAppendCost = INT_MAX;
			for (auto [level, vi] : srcs) {
				int nowPowerCost = area_.GetPowerCost(vi, levels[vi]);
				int newPowerCost = area_.GetPowerCost(vi, level);
				int appendCost = newPowerCost - nowPowerCost;
				if (appendCost < bestAppendCost) {
					bestAppendCost = appendCost;
					bestLevel = level;
					bestVi = vi;
				}
			}
			VASSERT(bestVi >= 0);
			chmax(levels[bestVi], bestLevel);
		}
	}

	void InitLevelMax(NArr<int>& levels) {
		REP(vi, N) {
			cauto& caster = area_.casters_[vi];
			levels[vi] = caster.levels.size() - 1;
		}
	}

	void InitLevelRand(NArr<int>& levels) {
		static KArr<bool> used;
		used.assign(K, false);
		REP(vi, N) {
			cauto& caster = area_.casters_[vi];
			levels[vi] = (int)rand_(caster.levels.size());
			REP(i, caster.levels[levels[vi]].range.b) {
				int ki = caster.kis[i];
				used[ki] = true;
			}
		}


		static KArr<int> kis;
		if (kis.empty()) {
			kis.resize(K);
			iota(ALL(kis), 0);
		}
		shuffle(ALL(kis), rand_);

		for (int ki : kis) {
			if (used[ki]) {
				continue;
			}
			cauto& srcs = area_.nearLevels_[ki];
			int bestVi = -1;
			int bestLevel = 0;
			int bestAppendCost = INT_MAX;
			for (auto [level, vi] : srcs) {
				int nowPowerCost = area_.GetPowerCost(vi, levels[vi]);
				int newPowerCost = area_.GetPowerCost(vi, level);
				int appendCost = newPowerCost - nowPowerCost;
				if (appendCost < bestAppendCost) {
					bestAppendCost = appendCost;
					bestLevel = level;
					bestVi = vi;
				}
			}
			VASSERT(bestVi >= 0);
			chmax(levels[bestVi], bestLevel);
		}
	}

	void InitOther(State& state) {
		state.powerCost = 0;
		state.refCounts.assign(K, 0);
		state.useVis.clear();
		REP(vi, N) {
			state.powerCost += area_.GetPowerCost(vi, state.levels[vi]);

			if (state.levels[vi] > 0) {
				state.useVis.push(vi);
			}

			cauto& caster = area_.casters_[vi];
			REP(i, caster.levels[state.levels[vi]].range.b) {
				int ki = caster.kis[i];
				++state.refCounts[ki];
				VASSERT(state.refCounts[ki] >= 0);
			}
		}
		state.edgeCost = MakeTree(state.levels);
		state.score = CalcScore(state);
		state.rawScore = (s64)round(state.score);
	}

	double CalcScore(s64 totalCost) {
		return 1000000 * (1 + 100000000 / (double)(totalCost + 10000000));
	}
	double CalcScore(const State& state) {
		return CalcScore(state.powerCost + state.edgeCost);
	}

	double ScoreToCost(double score) {
		return 1e14 / (score - 1e6) - 1e7;
	}

	bool TryDown(State& state, int vi) {
		cauto& caster = area_.casters_[vi];
		auto& level = state.levels[vi];

		int startI = 0;
		int newLevel = level;
		{
			int i = caster.levels[level].range.b - 1;
			while (i >= 0) {
				int ki = caster.kis[i];
				VASSERT(state.refCounts[ki] > 0);
				if (state.refCounts[ki] == 1) {
					break;
				}
				--i;
			}
			if (i < 0) {
				startI = 0;
				newLevel = 0;
			}
			else {
				int ki = caster.kis[i];
				int li = caster.ki2li[ki];
				startI = caster.levels[li].range.b;
				newLevel = li;
			}
		}
		if (level == newLevel) {
			return false;
		}
		int endI = caster.levels[level].range.b;
		FOR(i, startI, endI) {
			int ki = caster.kis[i];
			--state.refCounts[ki];
		}
		level = newLevel;
		return true;
	}

	void DownPossible(State& state) {
		if (rand_(2) == 0) {
			REP(vi, N) {
				TryDown(state, vi);
			}
		}
		else {
			RREP(vi, N) {
				TryDown(state, vi);
			}
		}
	}

	void Transition_DownPower(SimulatedAnnealing& sa, SAChecker& checker, State& state) {
		int visI = (int)rand_(state.useVis.size());
		int svi = state.useVis[visI];

		auto oldLevels = state.levels;
		auto oldRefCounts = state.refCounts;

		int newLevel = (int)rand_(state.levels[svi]);

		VASSERT(newLevel != state.levels[svi]);
		state.levels[svi] = newLevel;

		bool levelUp = false;
		{
			cauto& caster = area_.casters_[svi];
			int startI = caster.levels[newLevel].range.b;
			int endI = caster.levels[oldLevels[svi]].range.b;
			FOR(i, startI, endI) {
				int ki = caster.kis[i];

				--state.refCounts[ki];

				if (state.refCounts[ki] == 0) {
					cauto& srcs = area_.nearLevels_[ki];

					int bestVi = -1;
					int bestLevel = 0;
					if (srcs.size() == 1) {
						bestLevel = srcs[0].first;
						bestVi = srcs[0].second;
					}
					else {
						int bestAppendCost = INT_MAX;
						for (auto&& [level, vi] : srcs) {
							if (vi == svi) {
								continue;
							}
							int nowPowerCost = area_.GetPowerCost(vi, state.levels[vi]);
							int newPowerCost = area_.GetPowerCost(vi, level);
							int appendCost = newPowerCost - nowPowerCost;
							if (nowPowerCost == 0) {
								appendCost += easyCost_[vi];
							}

							if (appendCost < bestAppendCost) {
								bestAppendCost = appendCost;
								bestLevel = level;
								bestVi = vi;

								if (bestAppendCost <= 0) {
									break;
								}
							}
						}
					}

					VASSERT(bestVi >= 0);
					if (bestLevel > state.levels[bestVi]) {
						cauto& caster = area_.casters_[bestVi];
						int startI = caster.levels[state.levels[bestVi]].range.b;
						int endI = caster.levels[bestLevel].range.b;
						FOR(i, startI, endI) {
							int ki = caster.kis[i];
							++state.refCounts[ki];
						}
						state.levels[bestVi] = bestLevel;
						levelUp = true;

					}
				}
			}
		}

		if (levelUp) {
			DownPossible(state);
		}

		bool requireUpdateEdge = false;
		REP(i, N) {
			if ((oldLevels[i] == 0 && state.levels[i] != 0) ||
				(oldLevels[i] != 0 && state.levels[i] == 0)) {
				requireUpdateEdge = true;
				break;
			}
		}

		s64 newPowerCost = 0;
		REP(i, N) {
			newPowerCost += area_.GetPowerCost(i, state.levels[i]);
		}

		s64 newEdgeCost = 0;
		if (requireUpdateEdge) {
			newEdgeCost = MakeTree(state.levels);
		}
		else {
			newEdgeCost = state.edgeCost;
		}

		double newScore = CalcScore(newPowerCost + newEdgeCost);

		if (checker(newScore)) {
			if (requireUpdateEdge) {
				state.edgeCost = newEdgeCost;
				state.useVis.clear();
				REP(i, N) {
					if (state.levels[i]) {
						state.useVis.push(i);
					}
				}
			}
			state.powerCost = newPowerCost;
			state.score = newScore;
			state.rawScore = (s64)round(state.score);

			CheckMaxScore(state);
		}
		else {
			state.levels = oldLevels;
			state.refCounts = oldRefCounts;
		}
	}

	void Transition_DownPowerMulti(SimulatedAnnealing& sa, SAChecker& checker, State& state) {
		CapArr<int, 8> targetVis;
		if (state.useVis.size() == 1) {
			targetVis.push(state.useVis[0]);
		}
		else {
			static ChoiceTable tbl;
			tbl.Init(state.useVis.size());
			int targetCount = 2 + (int)rand_(min(4, state.useVis.size()));
			tbl.Choice(targetCount, rand_);
			for (int i : tbl) {
				targetVis.push(state.useVis[i]);
			}
		}

		auto oldLevels = state.levels;
		auto oldRefCounts = state.refCounts;
		bool levelUp = false;

		REP(ti, targetVis.size()) {
			int svi = targetVis[ti];

			int newLevel = (int)rand_(state.levels[svi]);
			chmax(newLevel, 0);
			state.levels[svi] = newLevel;

			cauto& caster = area_.casters_[svi];
			int startI = caster.levels[newLevel].range.b;
			int endI = caster.levels[oldLevels[svi]].range.b;
			FOR(i, startI, endI) {
				int ki = caster.kis[i];

				--state.refCounts[ki];

				if (state.refCounts[ki] == 0) {
					cauto& srcs = area_.nearLevels_[ki];

					int bestVi = -1;
					int bestLevel = 0;

					int bestAppendCost = INT_MAX;
					for (auto&& [level, vi] : srcs) {
						if (targetVis.find(vi) >= 0) {
							continue;
						}
						int nowPowerCost = area_.GetPowerCost(vi, state.levels[vi]);
						int newPowerCost = area_.GetPowerCost(vi, level);
						int appendCost = newPowerCost - nowPowerCost;
						if (nowPowerCost == 0 && newPowerCost > 0) {
							appendCost += (int)easyCost_[vi];
						}
						if (appendCost < bestAppendCost) {
							bestAppendCost = appendCost;
							bestLevel = level;
							bestVi = vi;

							if (bestAppendCost <= 0) {
								break;
							}
						}
					}
					if (bestVi < 0) {
						for (auto&& [level, vi] : srcs) {
							int nowPowerCost = area_.GetPowerCost(vi, state.levels[vi]);
							int newPowerCost = area_.GetPowerCost(vi, level);
							int appendCost = newPowerCost - nowPowerCost;
							if (nowPowerCost == 0 && newPowerCost > 0) {
								appendCost += (int)easyCost_[vi];
							}
							if (appendCost < bestAppendCost) {
								bestAppendCost = appendCost;
								bestLevel = level;
								bestVi = vi;

								if (bestAppendCost <= 0) {
									break;
								}
							}
						}
					}

					VASSERT(bestVi >= 0);
					if (bestLevel > state.levels[bestVi]) {
						cauto& caster = area_.casters_[bestVi];
						int startI = caster.levels[state.levels[bestVi]].range.b;
						int endI = caster.levels[bestLevel].range.b;
						FOR(i, startI, endI) {
							int ki = caster.kis[i];
							++state.refCounts[ki];
						}
						state.levels[bestVi] = bestLevel;
						levelUp = true;
					}
				}
			}
		}

		if (levelUp) {
			DownPossible(state);
		}

		bool requireUpdateEdge = false;
		REP(i, N) {
			if ((oldLevels[i] == 0 && state.levels[i] != 0) ||
				(oldLevels[i] != 0 && state.levels[i] == 0)) {
				requireUpdateEdge = true;
				break;
			}
		}

		s64 newEdgeCost = 0;
		if (requireUpdateEdge) {
			newEdgeCost = MakeTree(state.levels);
		}
		else {
			newEdgeCost = state.edgeCost;
		}

		s64 newPowerCost = 0;
		REP(i, N) {
			newPowerCost += area_.GetPowerCost(i, state.levels[i]);
		}
		double newScore = CalcScore(newPowerCost + newEdgeCost);

		if (checker(newScore)) {
			if (requireUpdateEdge) {
				state.edgeCost = newEdgeCost;
				state.useVis.clear();
				REP(i, N) {
					if (state.levels[i]) {
						state.useVis.push(i);
					}
				}
			}
			state.powerCost = newPowerCost;
			state.score = newScore;
			state.rawScore = (s64)round(state.score);

			CheckMaxScore(state);
		}
		else {
			state.levels = oldLevels;
			state.refCounts = oldRefCounts;
		}
	}

	void Transition_UpPower(SimulatedAnnealing& sa, SAChecker& checker, State& state) {
		int visI = (int)rand_(state.useVis.size());
		int svi = state.useVis[visI];

		auto oldLevels = state.levels;
		auto oldRefCounts = state.refCounts;

		cauto& caster = area_.casters_[svi];
		int maxUp = caster.levels.size() - 1 - state.levels[svi];
		if (maxUp == 0) {
			return;
		}
		int newLevel = state.levels[svi] + 1 + (int)rand_(maxUp);
		VASSERT(newLevel != state.levels[svi]);

		int startI = caster.levels[state.levels[svi]].range.b;
		int endI = caster.levels[newLevel].range.b;
		FOR(i, startI, endI) {
			int ki = caster.kis[i];
			++state.refCounts[ki];
		}
		state.levels[svi] = newLevel;

		bool update = false;
		if (rand_(2) == 0) {
			for (int vi : area_.competitors_[svi]) {
				VASSERT(vi != svi);
				if (TryDown(state, vi)) {
					update = true;
				}
			}
		}
		else {
			cauto& competitors = area_.competitors_[svi];
			RREP(i, competitors.size()) {
				int vi = competitors[i];
				VASSERT(vi != svi);
				if (TryDown(state, vi)) {
					update = true;
				}
			}
		}
		if (!update) {
			return;
		}
		{
			TryDown(state, svi);
		}

		bool requireUpdateEdge = false;
		REP(i, N) {
			if ((oldLevels[i] == 0 && state.levels[i] != 0) ||
				(oldLevels[i] != 0 && state.levels[i] == 0)) {
				requireUpdateEdge = true;
				break;
			}
		}

		s64 newEdgeCost = 0;
		if (requireUpdateEdge) {
			newEdgeCost = MakeTree(state.levels);
		}
		else {
			newEdgeCost = state.edgeCost;
		}

		s64 newPowerCost = 0;
		REP(i, N) {
			newPowerCost += area_.GetPowerCost(i, state.levels[i]);
		}
		double newScore = CalcScore(newPowerCost + newEdgeCost);

		if (checker(newScore)) {
			if (requireUpdateEdge) {
				state.edgeCost = newEdgeCost;
				state.useVis.clear();
				REP(i, N) {
					if (state.levels[i]) {
						state.useVis.push(i);
					}
				}
			}
			state.powerCost = newPowerCost;
			state.score = newScore;
			state.rawScore = (s64)round(state.score);

			CheckMaxScore(state);
		}
		else {
			state.levels = oldLevels;
			state.refCounts = oldRefCounts;
		}
	}

	void Transition_UpPowerMulti(SimulatedAnnealing& sa, SAChecker& checker, State& state) {
		CapArr<int, 8> targetVis;
		if (state.useVis.size() == 1) {
			targetVis.push(state.useVis[0]);
		}
		else {
			static ChoiceTable tbl;
			tbl.Init(state.useVis.size());
			int targetCount = 2 + (int)rand_(min(4, state.useVis.size()));
			tbl.Choice(targetCount, rand_);
			for (int i : tbl) {
				targetVis.push(state.useVis[i]);
			}
		}

		auto oldLevels = state.levels;
		auto oldRefCounts = state.refCounts;
		for (int svi : targetVis) {
			cauto& caster = area_.casters_[svi];
			int maxUp = caster.levels.size() - 1 - state.levels[svi];
			if (maxUp == 0) {
				return;
			}
			int newLevel = state.levels[svi] + 1 + (int)rand_(maxUp);
			VASSERT(newLevel != state.levels[svi]);

			int startI = caster.levels[state.levels[svi]].range.b;
			int endI = caster.levels[newLevel].range.b;
			FOR(i, startI, endI) {
				int ki = caster.kis[i];
				++state.refCounts[ki];
			}
			state.levels[svi] = newLevel;
		}

		bool update = false;
		if (rand_(2) == 0) {
			REP(vi, N) {
				if (targetVis.find(vi) >= 0) {
					continue;
				}
				if (TryDown(state, vi)) {
					update = true;
				}
			}
		}
		else {
			RREP(vi, N) {
				if (targetVis.find(vi) >= 0) {
					continue;
				}
				if (TryDown(state, vi)) {
					update = true;
				}
			}
		}
		if (!update) {
			return;
		}
		for (int vi : targetVis) {
			TryDown(state, vi);
		}

		bool requireUpdateEdge = false;
		REP(i, N) {
			if ((oldLevels[i] == 0 && state.levels[i] != 0) ||
				(oldLevels[i] != 0 && state.levels[i] == 0)) {
				requireUpdateEdge = true;
				break;
			}
		}

		s64 newEdgeCost = 0;
		if (requireUpdateEdge) {
			newEdgeCost = MakeTree(state.levels);
		}
		else {
			newEdgeCost = state.edgeCost;
		}

		s64 newPowerCost = 0;
		REP(i, N) {
			newPowerCost += area_.GetPowerCost(i, state.levels[i]);
		}
		double newScore = CalcScore(newPowerCost + newEdgeCost);

		if (checker(newScore)) {
			if (requireUpdateEdge) {
				state.edgeCost = newEdgeCost;
				state.useVis.clear();
				REP(i, N) {
					if (state.levels[i]) {
						state.useVis.push(i);
					}
				}
			}
			state.powerCost = newPowerCost;
			state.score = newScore;
			state.rawScore = (s64)round(state.score);

			CheckMaxScore(state);
		}
		else {
			state.levels = oldLevels;
			state.refCounts = oldRefCounts;
		}
	}

};















struct Main {
    void Run(int argc, const char* argv[]) {
        ChronoTimer timer;
        server.InitInput(timer);

        static Solver solver;
        timer.StartMs(TIME_LIMIT);

        solver.Run(timer);

        server.Finalize();
    }
};

Submission Info

Judge Result