結果
| 問題 |
No.2596 Christmas Eve (Heuristic ver.)
|
| コンテスト | |
| ユーザー |
 bin101
|
| 提出日時 | 2023-12-24 20:51:36 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 1,203 ms / 1,224 ms |
| コード長 | 25,766 bytes |
| コンパイル時間 | 5,151 ms |
| コンパイル使用メモリ | 270,028 KB |
| 実行使用メモリ | 6,548 KB |
| スコア | 4,998,674 |
| 最終ジャッジ日時 | 2023-12-24 20:54:24 |
| 合計ジャッジ時間 | 167,183 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge12 |
| 純コード判定しない問題か言語 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 125 |
ソースコード
/*
TODO:
*/
//#define NDEBUG
//#define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
//#define OPTUNA
#endif
#ifdef ONLINE_JUDGE
#define NDEBUG
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif
#include<bits/stdc++.h>
using namespace std;
using ll=long long int;
//using Int=__int128;
#define mask(x) ((1LL<<x)-1)
#define ALL(A) A.begin(),A.end()
template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}
template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}
template<typename T> int bitUP(T x,int a){return (x>>a)&1;}
enum Dir{
Right,
Down,
Left,
Up
};
//→ ↓ ← ↑
int dh[4]={0,1,0,-1}, dw[4]={1,0,-1,0};
//上から時計回り
//int dx[8]={0,1,1,1,0,-1,-1,-1}, dy[8]={1,1,0,-1,-1,-1,0,1};
long double EPS = 1e-6;
const ll INF=(1LL<<62);
const int MAX=(1<<30);
using pii=pair<int,int>;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using psi=pair<string,int>;
using pis=pair<int,string>;
using psl=pair<string,ll>;
using pls=pair<ll,string>;
using pss=pair<string,string>;
template<class T>
using minimum_queue=priority_queue<T,vector<T>,greater<T>>;
using Graph=vector<vector<int>>;
using i8=int8_t;
using i16=int16_t;
using i32=int32_t;
using i64=int64_t;
using u8=uint8_t;
using u16=uint16_t;
using u32=uint32_t;
using u64=uint64_t;
void FastIO(){
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(20);
}
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<T> &v) {
for(size_t i=0;i<v.size();i++) is>>v[i];
return is;
}
//0-indexed vector cin
template<typename T>
inline istream &operator>>(istream &is,vector<vector<T>> &v) {
for(size_t i=0;i<v.size();i++){
is>>v[i];
}
return is;
}
struct Xor32{
using u32=uint32_t;
u32 x=1234567;
inline u32 rnd_make(){
x^=(x<<13);
x^=(x>>17);
x^=(x<<5);
return x;
}
inline u32 operator()(){
return rnd_make();
}
//[a,b)
inline int operator()(int a,int b){
int dis=b-a;
int add=rnd_make()%dis;
return a+add;
}
//[0,b)
inline int operator()(int b){
return rnd_make()%b;
}
//http://web.archive.org/web/20200105011004/https://topcoder.g.hatena.ne.jp/tomerun/20171216/
//[0,b)の中から異なる2つを選ぶ [0]の値<[1]の値
inline array<int,2> two(int b){
assert(b>=2);
int v1=rnd_make()%b;
int v2=rnd_make()%(b-1);
if (v2>=v1) return {v1,v2+1};
else return {v2,v1};
}
inline float random01(){
return float(rnd_make())/mask(32);
}
inline double random_double(double a,double b){
double sa=b-a;
a+=random01()*sa;
return a;
}
//確率pでtrueを返す
inline bool gen_bool(float p){
return p>random01();
}
};
struct Xor64{
u64 x=1234567;
inline u64 rnd_make(){
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
return x;
}
inline u64 operator()(){
return rnd_make();
}
};
struct Timer{
chrono::high_resolution_clock::time_point st;
float local;
Timer(){
#ifndef ONLINE_JUDGE
local=1.0;
#endif
start();
}
void start(){
st=chrono::high_resolution_clock::now();
}
int span()const{
auto now=chrono::high_resolution_clock::now();
return chrono::duration_cast<chrono::milliseconds>(now-st).count();
}
};
struct TestTimer{
chrono::high_resolution_clock::time_point st;
unordered_map<string,ll> sum_time;
unordered_map<string,chrono::high_resolution_clock::time_point> start_time;
TestTimer(){}
void start(const string &s){
#ifndef ONLINE_JUDGE
start_time[s]=chrono::high_resolution_clock::now();
#endif
}
void end(const string &s){
#ifndef ONLINE_JUDGE
auto now=chrono::high_resolution_clock::now();
sum_time[s]+=chrono::duration_cast<chrono::nanoseconds>(now-start_time[s]).count();
#endif
}
void output()const{
#ifndef ONLINE_JUDGE
for(auto m:sum_time){
cerr<<m.first<<": "<<m.second/1e6<<"ms"<<endl;
}
#endif
}
};
struct TestCounter{
unordered_map<string,ll> cnt;
TestCounter(){}
void count(const string &s){
#ifndef ONLINE_JUDGE
cnt[s]++;
#endif
}
void output()const{
#ifndef ONLINE_JUDGE
for(auto m:cnt){
cerr<<m.first<<": "<<m.second<<endl;
}
#endif
}
};
Timer TIME;
Xor32 Rand32;
Xor64 Rand64;
TestTimer testTimer;
TestCounter testCounter;
//https://atcoder.jp/contests/asprocon9/submissions/34659956
template<class T,int CAPACITY>
class DynamicArray{
public:
array<T,CAPACITY> array_={};
int size_=0;
DynamicArray(){}
DynamicArray(int n){
resize(n);
}
void push_back(const T &e){
array_[size_++]=e;
}
//ソートされた状態を保つように挿入
void insert(const T &e){
int ng=-1,ok=size_;
while(ok-ng!=1){
int mid=(ok+ng)/2;
if(array_[mid]>e) ok=mid;
else ng=mid;
}
for(int i=size_;i>ok;i--){
array_[i]=array_[i-1];
}
array_[ok]=e;
size_++;
}
//eをこえる一番左の添字
int find_binary_search(const T &e)const{
int ng=-1,ok=size_;
while(ok-ng!=1){
int mid=(ok+ng)/2;
if(array_[mid]>=e) ok=mid;
else ng=mid;
}
return ok;
}
void pop_back(){
size_--;
}
inline T& operator[](int index){
return array_[index];
}
inline const T& operator[](int index) const {
return array_[index];
}
inline int size()const{
return size_;
}
inline T& back(){
return array_[size_-1];
}
const inline T& back()const{
return array_[size_-1];
}
inline auto begin() -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() -> decltype(array_.begin()) {
return array_.begin() + size_;
}
inline auto begin() const -> decltype(array_.begin()) {
return array_.begin();
}
inline auto end() const -> decltype(array_.begin()) {
return array_.begin() + size_;
}
inline void resize(int new_size){
size_=new_size;
}
void operator=(const DynamicArray &e){
for(int i=0;i<e.size_;i++){
array_[i]=e[i];
}
size_=e.size_;
}
bool operator==(const DynamicArray &v){
if(size_!=v.size_) return false;
for(int i=0;i<size_;i++){
if(array_[i]!=v[i]){
return false;
}
}
return true;
}
bool operator==(const vector<T> &v){
if(size_!=v.size()) return false;
for(int i=0;i<size_;i++){
if(array_[i]!=v[i]){
return false;
}
}
return true;
}
void clear(){
size_=0;
}
//O(1)
//末尾と入れ替える。順序が保持されないが高速
void swap_remove(int idx){
array_[idx]=array_[size_-1];
size_--;
}
//最初から見ていき、一致したものを削除(remove)
bool erase(T value){
for(int i=0;i<size_;i++){
if(array_[i]==value){
remove(i);
return true;
}
}
return false;
}
void reverse(){
for(int i=0;i<size_/2;i++){
swap(array_[i],array_[size_-1-i]);
}
}
//O(size)
//順序を気にしない場合、swap_removeの方がいい
void remove(int idx){
for(int i=idx;i<size_-1;i++){
array_[i]=array_[i+1];
}
size_--;
}
void fill(T x){
for(int i=0;i<size_;i++){
array_[i]=x;
}
}
};
//ソート
template<typename T>
inline void vsort(vector<T> &v){
sort(v.begin(),v.end());
}
//逆順ソート
template<typename T>
inline void rvsort(vector<T> &v){
sort(v.rbegin(),v.rend());
}
//1ビットの数を返す
inline int popcount(int x){
return __builtin_popcount(x);
}
//1ビットの数を返す
inline int popcount(ll x){
return __builtin_popcountll(x);
}
template<typename T>
inline void Compress(vector<T> &C){
sort(C.begin(),C.end());
C.erase(unique(C.begin(),C.end()),C.end());
}
//要素数n 初期値x
template<typename T>
inline vector<T> vmake(size_t n,T x){
return vector<T>(n,x);
}
//a,b,c,x data[a][b][c] 初期値x
template<typename... Args>
auto vmake(size_t n,Args... args){
auto v=vmake(args...);
return vector<decltype(v)>(n,move(v));
}
//vは昇順
bool is_in(const vector<int> &v,int x){
int n=v.size();
if(n==0) return false;
int ng=-1,ok=n-1;
while(ok-ng!=1){
int mid=(ok+ng)/2;
if(v[mid]<x) ng=mid;
else ok=mid;
}
if(v[ok]==x) return true;
return false;
}
template<typename T >
struct edge {
int to;
T cost;
int id;
edge()=default;
edge(int to, T cost,int id) : to(to), cost(cost), id(id) {}
};
template<class T >
struct Edge {
int from, to,id;
T cost;
Edge(int from,int to,T cost,int id):from(from),to(to),cost(cost),id(id){}
Edge()=default;
bool operator<(const Edge<T> &e){
return cost<e.cost;
}
bool operator<=(const Edge<T> &e){
return cost<=e.cost;
}
};
template<typename T>
using WeightGraph=vector<vector<edge<T>>>;
//vector cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<T> &v) {
bool sp=true;
if(string(typeid(T).name())=="c") sp=false;
for(size_t i=0;i<v.size();i++){
if(i and sp) os<<" ";
os<<v[i];
}
return os;
}
//vector<vector> cout
template<typename T>
inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {
for(size_t i=0;i<v.size();i++){
os<<v[i];
if(i+1!=v.size()) os<<"\n";
}
return os;
}
//pair cout
template<typename T, typename U>
inline ostream &operator<<(ostream &os,const pair<T,U> &p) {
os<<p.first<<" "<<p.second;
return os;
}
//map cout
template<typename F, typename S>
inline ostream &operator<<(ostream &os,const map<F,S> &M) {
bool first=false;
for(auto x:M){
if(first) os<<endl;
first=true;
os<<x;
}
return os;
}
//set cout
template<typename T>
inline ostream &operator<<(ostream &os,const set<T> &S) {
bool first=false;
for(auto x:S){
if(first) os<<endl;
first=true;
os<<x;
}
return os;
}
//pair cin
template<typename T, typename U>
inline istream &operator>>(istream &is,pair<T,U> &p) {
is>>p.first>>p.second;
return is;
}
template<typename T>
void append(vector<T> &v,const vector<T> &vp){
for(auto p:vp){
v.push_back(p);
}
}
//Fisher–Yatesアルゴリズム
template<typename T>
void shuffle(vector<T> &v){
int sz=v.size();
for(int i=sz-1;i>0;i--){
swap(v[Rand32()%(i+1)],v[i]);
}
}
template<class T,class U>
T linear_function(U x,U start_x,U end_x,T start_value,T end_value){
if(x>=end_x) return end_value;
if(x<=start_x) return start_value;
return start_value+(end_value-start_value)*(x-start_x)/(end_x-start_x);
}
//http://gasin.hatenadiary.jp/entry/2019/09/03/162613
struct SimulatedAnnealing{
float temp_start; //差の最大値(あくまでも参考)
float temp_end; //差の最小値(あくまでも参考)
float time_start;
float time_end;
bool is_hill;
bool minimum;
int interval=1; //intervalごとに温度の再計算
float temp_now;
int cnt_calc_temp;
/*
0:線形
1:pow pow
2:指数
*/
int temp_type;
//SimulatedAnnealing(){}
SimulatedAnnealing(float temp_start,float temp_end,float time_start,float time_end,bool is_hill,bool minimum,int temp_type=0,int interval=1):
temp_start(temp_start),temp_end(temp_end),time_start(time_start),time_end(time_end),
is_hill(is_hill),minimum(minimum),temp_type(temp_type),interval(interval),temp_now(temp_start),cnt_calc_temp(0){
}
float calc_temp(){
if(cnt_calc_temp%interval==0){
float progress=float(TIME.span()-time_start)/(time_end-time_start);
if(progress>1.0) progress=1.0;
if(temp_type==0){//線形
temp_now=temp_start*(1.0-progress)+temp_end*progress;
}else if(temp_type==1){ //https://atcoder.jp/contests/ahc014/submissions/35326979
temp_now = pow(temp_start,1.0-progress)*pow(temp_end,progress);
}else{ //https://ozy4dm.hateblo.jp/entry/2022/12/22/162046#68-%E3%83%97%E3%83%AB%E3%83%BC%E3%83%8B%E3%83%B3%E3%82%B0%E6%97%A9%E6%9C%9F%E7%B5%82%E4%BA%86%E5%8D%98%E7%B4%94%E5%8C%96%E3%81%95%E3%82%8C%E3%81%9F%E8%A8%88%E7%AE%97%E3%82%92%E4%BD%BF%E7%94%A8%E3%81%99%E3%82%8B
temp_now = temp_start*pow(temp_end/temp_start,progress);
}
}
cnt_calc_temp++;
return temp_now;
}
//diff: スコアの変化量
//確率を計算
float calc_prob(float diff){
if(minimum) diff*=-1;
if(diff>0) return 1;
float temp=calc_temp();
return exp(diff/temp);
}
inline bool operator()(float diff){
testCounter.count("try_cnt");
if(minimum) diff*=-1;
if(diff>=0){
if(diff==0) testCounter.count("zero_change");
else testCounter.count("plus_change");
return true;
}
if(is_hill) return false;
float prob = exp(diff/calc_temp());
if(Rand32.gen_bool(prob)){
testCounter.count("minus_change");
return true;
}
else return false;
}
//最大化の場合,返り値<変化量なら遷移してもよい
float calc_tolerance(float prob){
float tolerance=log(prob)*calc_temp();
if(minimum) tolerance*=-1;
return tolerance;
}
//log(prob)*temp prob:[0,1]の乱数
float calc_tolerance(){
float prob=Rand32.random01();
return calc_tolerance(prob);
}
};
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
//https://atcoder.jp/contests/asprocon9/submissions/34659956
#ifndef OPTUNA
#define REGIST_PARAM(name, type, defaultValue) constexpr type name = defaultValue
#else
#define REGIST_PARAM(name, type, defaultValue) type name = defaultValue
#endif
namespace OP{
REGIST_PARAM(yama,bool,false);
REGIST_PARAM(startTemp,double,500000);
REGIST_PARAM(endTemp,float,0);
REGIST_PARAM(TIME_END,int,1900);
};
constexpr int num_parts=500;
int num_tree;
struct Parts{
int width;
int height;
int id;
bool used=false;
};
vector<Parts> bases_input(num_parts*2);
vector<Parts> middles_input(num_parts);
vector<Parts> tops_input(num_parts);
void input(){
int dummy;
cin>>dummy;
cin>>num_tree;
for(int i=0;i<num_parts;i++){
cin>>middles_input[i].width;
middles_input[i].id=i;
}
for(int i=0;i<num_parts;i++){
cin>>middles_input[i].height;
}
for(int i=0;i<num_parts*2;i++){
cin>>bases_input[i].width;
bases_input[i].id=i;
}
for(int i=0;i<num_parts*2;i++){
cin>>bases_input[i].height;
}
for(int i=0;i<num_parts;i++){
cin>>tops_input[i].width;
tops_input[i].id=i;
}
for(int i=0;i<num_parts;i++){
cin>>tops_input[i].height;
}
}
struct Ans{
array<Parts,2> bases;
Parts middle;
Parts top;
bool is_valid(){
if(min(bases[0].width,bases[1].width)<=middle.width) return false;
if(middle.width<=top.width) return false;
return true;
}
int height(){
int h=0;
h+=bases[0].height;
h+=bases[1].height;
h+=middle.height;
h+=top.height;
return h;
}
Parts& operator[](int type){
if(type<2){
return bases[type];
}
if(type==3) return middle;
else return top;
}
};
vector<Ans> ans;
vector<Parts> bases_res;
vector<Parts> middles_res;
vector<Parts> tops_res;
void make_valid_ans(){
auto bases=bases_input;
auto middles=middles_input;
auto tops=tops_input;
sort(bases.begin(),bases.end(),
[&](Parts a,Parts b){
return a.width>b.width;
});
sort(middles.begin(),middles.end(),
[&](Parts a,Parts b){
return a.width>b.width;
});
sort(tops.begin(),tops.end(),
[&](Parts a,Parts b){
return a.width>b.width;
});
vector<int> now(3,0);
while(ans.size()!=num_tree){
Ans a;
a.bases[0]=bases[now[0]];
a.bases[1]=bases[now[0]+1];
now[0]+=2;
int w=a.bases[1].width;
for(int i=now[1];;i++){
if(w>middles[i].width){
now[1]=i+1;
a.middle=middles[i];
w=middles[i].width;
break;
}
middles_res.push_back(middles[i]);
}
for(int i=now[2];;i++){
if(w>tops[i].width){
now[2]=i+1;
a.top=tops[i];
break;
}
tops_res.push_back(tops[i]);
}
ans.push_back(a);
}
for(int i=now[0];i<num_parts*2;i++){
bases_res.push_back(bases[i]);
}
for(int i=now[1];i<num_parts;i++){
middles_res.push_back(middles[i]);
}
for(int i=now[2];i<num_parts;i++){
tops_res.push_back(tops[i]);
}
while(bases_res.size()){
Ans a;
a.bases[0]=bases_res.back();
bases_res.pop_back();
a.bases[1]=bases_res.back();
bases_res.pop_back();
a.middle=middles_res.back();
middles_res.pop_back();
a.top=tops_res.back();
tops_res.pop_back();
ans.push_back(a);
}
assert(ans.size()==num_parts);
}
ll evaluate(vector<Ans> &ans){
int min_h=MAX;
int max_h=-1;
ll error_value=0;
for(int i=0;i<num_tree;i++){
auto a=ans[i];
chmin(min_h,a.height());
chmax(max_h,a.height());
if(a.is_valid()==false) error_value+=1e5;
}
return error_value+(max_h-min_h);
}
void output(vector<Ans> ans){
for(int i=0;i<num_tree;i++){
auto a=ans[i];
assert(a.is_valid());
cout<<a.middle.id+1<<" "<<a.bases[0].id+1<<" "<<a.bases[1].id+1<<" "<<a.top.id+1<<endl;
//cerr<<middles_input[a.middle.id].width<<" "<<bases_input[a.bases[0].id].width<<" "<<bases_input[a.bases[1].id].width<<" "<<tops_input[a.top.id].width<<endl;
}
}
/*
1. validな解を作る
焼きなましにする
最小と最大を常に保持
どうやろう
素直なのはセグ木
近傍: 最小(最大)の木となにかを適当に交換
validな解でなければダメ
*/
template<class T,class F>
struct SegmentTree{
const F f;
int size;
int N;
vector<T> seg;
const T unit;
SegmentTree(int N,const F _f,const T &_unit) :N(N),f(_f),unit(_unit){
size=1;
while(size<N) size<<=1;
seg.assign(2*size,unit);
build();
}
void set(int k,const T &x){
seg[k+size]=x;
}
void build(){
for(int k=size-1;k>0;k--){
seg[k]=f(seg[2*k],seg[2*k+1]);
}
}
void update(int k,const T &x){
k+=size;
seg[k]=x;
while(k>>=1){
seg[k]=f(seg[2*k],seg[2*k+1]);
}
}
//[a:b)
//[0:N)に自動で抑える
T query(int a,int b){
if(a<0) a=0;
if(b>N) b=N;
T L=unit,R=unit;
for(a+=size,b+=size;a<b;a>>=1,b>>=1){
if(a&1) L=f(L,seg[a++]);
if(b&1) R=f(seg[--b],R);
}
return f(L,R);
}
//左側を固定する二分探索
//参考:https://qiita.com/ningenMe/items/bf66de877e3b97d35862
//https://rsk0315.hatenablog.com/entry/2020/11/25/193834
//falseが出たなら上がるor右に行く
//p(a[l,r])=trueとなる最小のr
//↑を満たすrがなければr=Nとする
//verify:https://atcoder.jp/contests/iroha2019-day1/submissions/20250286
template<class G>
int left_binary_search(int l,G g){
T x=unit;
int idx;
for(idx=l+size;idx<2*size;){
if(not g(f(x,seg[idx]))){
x=f(x,seg[idx]);
idx++;
if(__builtin_popcount(idx)==1) return N;
if(not (idx&1)) idx>>=1; //右の子だったら
}else{
idx<<=1;
}
}
return (idx>>1)-size;
}
//右側を固定する二分探索
//p(a[l,r])=trueとなる最大のl
//↑を満たすrがなければl=-1とする
//veirfy:https://atcoder.jp/contests/past202012-open/submissions/20483948
template<class G>
int right_binary_search(int r,G g){
T x=unit;
int idx;
for(idx=r+size;idx<2*size;){
if(not g(f(seg[idx],x))){ //falseならまだ伸ばす
x=f(seg[idx],x);
if(__builtin_popcount(idx)==1) return -1;
idx--;
if((idx&1)) idx>>=1; //左の子だったら
}else{
idx<<=1; //左の子に移動
idx++; //右に移動
}
}
return (idx>>1)-size;
}
T operator[](const int &k) const{
return seg[k+size];
}
};
void solve(){
input();
make_valid_ans();
auto is_valid=[&](int i){
return ans[i].is_valid();
};
cerr<<evaluate(ans)<<endl;
auto f_min=[](array<pii,3> &a,array<pii,3> &b){
array<pii,3> ret;
int i0=0,i1=0;
for(int i=0;i<3;i++){
if(a[i0]<b[i1]){
ret[i]=a[i0];
i0++;
}else{
ret[i]=b[i1];
i1++;
}
}
return ret;
};
auto f_max=[](array<pii,3> a,array<pii,3> b){
array<pii,3> ret;
int i0=0,i1=0;
for(int i=0;i<3;i++){
if(a[i0]>b[i1]){
ret[i]=a[i0];
i0++;
}else{
ret[i]=b[i1];
i1++;
}
}
return ret;
};
array<pii,3> unit_min;
for(int i=0;i<3;i++){
unit_min[i].first=MAX;
}
SegmentTree<array<pii,3>,decltype(f_min)> seg_min(num_tree,f_min,unit_min);
array<pii,3> unit_max;
for(int i=0;i<3;i++){
unit_max[i].first=-1;
}
SegmentTree<array<pii,3>,decltype(f_max)> seg_max(num_tree,f_max,unit_max);
for(int i=0;i<num_tree;i++){
unit_min[0]=pii(ans[i].height(),i);
unit_max[0]=pii(ans[i].height(),i);
seg_min.set(i,unit_min);
seg_max.set(i,unit_max);
}
seg_min.build();
seg_max.build();
SimulatedAnnealing SA(8,0,TIME.span(),1200,false,true,0,1000);
int pre_score=evaluate(ans);
int best_score=pre_score;
vector<Ans> best_ans=ans;
auto max3=seg_max.query(0,num_tree);
auto min3=seg_min.query(0,num_tree);
while(TIME.span()<1200){
int id0=Rand32(num_tree);
bool minimum=false;
if(Rand32(2)){
id0=min3[0].second;
minimum=true;
}else{
id0=max3[0].second;
}
if(Rand32(2)){
swap(ans[id0][0],ans[id0][1]);
}
int id1=Rand32(0,num_parts);
int type=Rand32(0,4);
if(minimum and ans[id0][type].height>ans[id1][type].height) continue;
if(minimum==false and ans[id0][type].height<ans[id1][type].height) continue;
swap(ans[id0][type],ans[id1][type]);
//not validならダメ
if(is_valid(id0)==false or (id1<num_tree and is_valid(id1)==false)){
swap(ans[id0][type],ans[id1][type]);
continue;
}
int h0=ans[id0].height();
int h1=ans[id1].height();
if(id1>=num_tree) h1=-1;
int max_h=0;
for(int i=0;i<3;i++){
if(max3[i].second==id0 or max3[i].second==id1){
continue;
}
if(max3[i].first>=max(h0,h1)){
max_h=max3[i].first;
}else{
max_h=max(h0,h1);
}
}
if(id1>=num_tree) h1=MAX;
int min_h=0;
for(int i=0;i<3;i++){
if(min3[i].second==id0 or min3[i].second==id1){
continue;
}
if(min3[i].first<=min(h0,h1)){
min_h=min3[i].first;
}else{
min_h=min(h0,h1);
}
}
int now_score=max_h-min_h;
//cerr<<now_score<<endl;
if(SA(now_score-pre_score)){
pre_score=now_score;
if(best_score>now_score){
best_score=now_score;
best_ans=ans;
}
unit_min[0]=pii(ans[id0].height(),id0);
unit_max[0]=pii(ans[id0].height(),id0);
seg_min.update(id0,unit_min);
seg_max.update(id0,unit_max);
if(id1<num_tree){
unit_min[0]=pii(ans[id1].height(),id1);
unit_max[0]=pii(ans[id1].height(),id1);
seg_min.update(id1,unit_min);
seg_max.update(id1,unit_max);
}
min3=seg_min.query(0,num_tree);
max3=seg_max.query(0,num_tree);
}else{
swap(ans[id0][type],ans[id1][type]);
}
}
output(best_ans);
#ifndef ONLINE_JUDGE
testTimer.output();
testCounter.output();
cerr<<TIME.span()<<"ms"<<endl;
cerr<<"score: "<<evaluate(best_ans)<<endl;
#endif
}
int main(const int argc,const char** argv){
#ifndef OPTUNA
if(argc!=1){
}
#endif
FastIO();
int T=1;
//cin>>T;
while(T--) solve();
}