#940194 (C++17) No.2596 Christmas Eve (Heuristic ver.)

提出ソース

結果

問題	No.2596 Christmas Eve (Heuristic ver.)
ユーザー	bin101
提出日時	2023-12-24 20:12:19
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,204 ms / 1,224 ms
コード長	24,333 bytes
コンパイル時間	4,747 ms
コンパイル使用メモリ	264,964 KB
実行使用メモリ	6,676 KB
スコア	4,998,543
最終ジャッジ日時	2023-12-24 20:15:08
合計ジャッジ時間	168,105 ms
ジャッジサーバーID （参考情報）	judge14 / judge13
	純コード判定しない問題か言語

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,203 ms 6,676 KB
testcase_01	AC	1,203 ms 6,676 KB
testcase_02	AC	1,202 ms 6,676 KB
testcase_03	AC	1,203 ms 6,676 KB
testcase_04	AC	1,203 ms 6,676 KB
testcase_05	AC	1,202 ms 6,676 KB
testcase_06	AC	1,202 ms 6,676 KB
testcase_07	AC	1,203 ms 6,676 KB
testcase_08	AC	1,203 ms 6,676 KB
testcase_09	AC	1,203 ms 6,676 KB
testcase_10	AC	1,203 ms 6,676 KB
testcase_11	AC	1,203 ms 6,676 KB
testcase_12	AC	1,202 ms 6,676 KB
testcase_13	AC	1,203 ms 6,676 KB
testcase_14	AC	1,202 ms 6,676 KB
testcase_15	AC	1,203 ms 6,676 KB
testcase_16	AC	1,202 ms 6,676 KB
testcase_17	AC	1,202 ms 6,676 KB
testcase_18	AC	1,203 ms 6,676 KB
testcase_19	AC	1,203 ms 6,676 KB
testcase_20	AC	1,202 ms 6,676 KB
testcase_21	AC	1,203 ms 6,676 KB
testcase_22	AC	1,203 ms 6,676 KB
testcase_23	AC	1,203 ms 6,676 KB
testcase_24	AC	1,203 ms 6,676 KB
testcase_25	AC	1,203 ms 6,676 KB
testcase_26	AC	1,203 ms 6,676 KB
testcase_27	AC	1,203 ms 6,676 KB
testcase_28	AC	1,203 ms 6,676 KB
testcase_29	AC	1,202 ms 6,676 KB
testcase_30	AC	1,202 ms 6,676 KB
testcase_31	AC	1,203 ms 6,676 KB
testcase_32	AC	1,202 ms 6,676 KB
testcase_33	AC	1,203 ms 6,676 KB
testcase_34	AC	1,202 ms 6,676 KB
testcase_35	AC	1,203 ms 6,676 KB
testcase_36	AC	1,203 ms 6,676 KB
testcase_37	AC	1,202 ms 6,676 KB
testcase_38	AC	1,203 ms 6,676 KB
testcase_39	AC	1,203 ms 6,676 KB
testcase_40	AC	1,202 ms 6,676 KB
testcase_41	AC	1,202 ms 6,676 KB
testcase_42	AC	1,202 ms 6,676 KB
testcase_43	AC	1,202 ms 6,676 KB
testcase_44	AC	1,203 ms 6,676 KB
testcase_45	AC	1,202 ms 6,676 KB
testcase_46	AC	1,203 ms 6,676 KB
testcase_47	AC	1,202 ms 6,676 KB
testcase_48	AC	1,203 ms 6,676 KB
testcase_49	AC	1,203 ms 6,676 KB
testcase_50	AC	1,203 ms 6,676 KB
testcase_51	AC	1,202 ms 6,676 KB
testcase_52	AC	1,202 ms 6,676 KB
testcase_53	AC	1,203 ms 6,676 KB
testcase_54	AC	1,203 ms 6,676 KB
testcase_55	AC	1,203 ms 6,676 KB
testcase_56	AC	1,202 ms 6,676 KB
testcase_57	AC	1,204 ms 6,676 KB
testcase_58	AC	1,203 ms 6,676 KB
testcase_59	AC	1,203 ms 6,676 KB
testcase_60	AC	1,203 ms 6,676 KB
testcase_61	AC	1,203 ms 6,676 KB
testcase_62	AC	1,203 ms 6,676 KB
testcase_63	AC	1,203 ms 6,676 KB
testcase_64	AC	1,202 ms 6,676 KB
testcase_65	AC	1,203 ms 6,676 KB
testcase_66	AC	1,202 ms 6,676 KB
testcase_67	AC	1,203 ms 6,676 KB
testcase_68	AC	1,203 ms 6,676 KB
testcase_69	AC	1,202 ms 6,676 KB
testcase_70	AC	1,203 ms 6,676 KB
testcase_71	AC	1,202 ms 6,676 KB
testcase_72	AC	1,203 ms 6,676 KB
testcase_73	AC	1,203 ms 6,676 KB
testcase_74	AC	1,202 ms 6,676 KB
testcase_75	AC	1,203 ms 6,676 KB
testcase_76	AC	1,202 ms 6,676 KB
testcase_77	AC	1,203 ms 6,676 KB
testcase_78	AC	1,201 ms 6,676 KB
testcase_79	AC	1,203 ms 6,676 KB
testcase_80	AC	1,203 ms 6,676 KB
testcase_81	AC	1,203 ms 6,676 KB
testcase_82	AC	1,203 ms 6,676 KB
testcase_83	AC	1,203 ms 6,676 KB
testcase_84	AC	1,203 ms 6,676 KB
testcase_85	AC	1,203 ms 6,676 KB
testcase_86	AC	1,203 ms 6,676 KB
testcase_87	AC	1,202 ms 6,676 KB
testcase_88	AC	1,203 ms 6,676 KB
testcase_89	AC	1,203 ms 6,676 KB
testcase_90	AC	1,203 ms 6,676 KB
testcase_91	AC	1,203 ms 6,676 KB
testcase_92	AC	1,202 ms 6,676 KB
testcase_93	AC	1,202 ms 6,676 KB
testcase_94	AC	1,203 ms 6,676 KB
testcase_95	AC	1,202 ms 6,676 KB
testcase_96	AC	1,202 ms 6,676 KB
testcase_97	AC	1,203 ms 6,676 KB
testcase_98	AC	1,203 ms 6,676 KB
testcase_99	AC	1,202 ms 6,676 KB
testcase_100	AC	1,203 ms 6,676 KB
testcase_101	AC	1,203 ms 6,676 KB
testcase_102	AC	1,203 ms 6,676 KB
testcase_103	AC	1,203 ms 6,676 KB
testcase_104	AC	1,202 ms 6,676 KB
testcase_105	AC	1,203 ms 6,676 KB
testcase_106	AC	1,203 ms 6,676 KB
testcase_107	AC	1,203 ms 6,676 KB
testcase_108	AC	1,202 ms 6,676 KB
testcase_109	AC	1,203 ms 6,676 KB
testcase_110	AC	1,203 ms 6,676 KB
testcase_111	AC	1,202 ms 6,676 KB
testcase_112	AC	1,203 ms 6,676 KB
testcase_113	AC	1,201 ms 6,676 KB
testcase_114	AC	1,202 ms 6,676 KB
testcase_115	AC	1,203 ms 6,676 KB
testcase_116	AC	1,202 ms 6,676 KB
testcase_117	AC	1,203 ms 6,676 KB
testcase_118	AC	1,203 ms 6,676 KB
testcase_119	AC	1,203 ms 6,676 KB
testcase_120	AC	1,203 ms 6,676 KB
testcase_121	AC	1,203 ms 6,676 KB
testcase_122	AC	1,201 ms 6,676 KB
testcase_123	AC	1,203 ms 6,676 KB
testcase_124	AC	1,203 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

/*
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=[](pii a,pii b){
        return min(a,b);
    };
    auto f_max=[](pii a,pii b){
        return max(a,b);
    };
    SegmentTree<pii,decltype(f_min)> seg_min(num_tree,f_min,pii(MAX,-1));
    SegmentTree<pii,decltype(f_max)> seg_max(num_tree,f_max,pii(-1,-1));

    for(int i=0;i<num_tree;i++){
        seg_min.set(i,pii(ans[i].height(),i));
        seg_max.set(i,pii(ans[i].height(),i));
    }
    seg_min.build();
    seg_max.build();

    SimulatedAnnealing SA(50,0,TIME.span(),1200,false,true,0,1000);
    int pre_score=evaluate(ans);
    int best_score=pre_score;
    vector<Ans> best_ans=ans;

    while(TIME.span()<1200){
        int id0=Rand32(num_tree);
        bool minimum=false;
        if(Rand32(2)){
            id0=seg_min.query(0,num_tree).second;
            minimum=true;
        }else{
            id0=seg_max.query(0,num_tree).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();
        seg_max.update(id0,pii(h0,id0));
        seg_min.update(id0,pii(h0,id0));

        if(id1<num_tree){
            int h1=ans[id1].height();
            seg_max.update(id1,pii(h1,id1));
            seg_min.update(id1,pii(h1,id1));
        }

        int now_score=seg_max.query(0,num_tree).first-seg_min.query(0,num_tree).first;
        if(SA(now_score-pre_score)){
            pre_score=now_score;
            if(best_score>now_score){
                best_score=now_score;
                best_ans=ans;
            }
        }else{
            swap(ans[id0][type],ans[id1][type]);
            int h0=ans[id0].height();
            seg_max.update(id0,pii(h0,id0));
            seg_min.update(id0,pii(h0,id0));

            if(id1<num_tree){
                int h1=ans[id1].height();
                seg_max.update(id1,pii(h1,id1));
                seg_min.update(id1,pii(h1,id1));
            }
        }
    }
    output(best_ans);
    cerr<<seg_max.query(0,num_tree).first-seg_min.query(0,num_tree).first<<endl;
    
#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();
}

yukicoder

結果

テストケース

ソースコード