/* 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 using namespace std; using ll=long long int; //using Int=__int128; #define mask(x) ((1LL< bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;} template bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;} template 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; using pil=pair; using pli=pair; using pll=pair; using psi=pair; using pis=pair; using psl=pair; using pls=pair; using pss=pair; template using minimum_queue=priority_queue,greater>; using Graph=vector>; 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 inline istream &operator>>(istream &is,vector &v) { for(size_t i=0;i>v[i]; return is; } //0-indexed vector cin template inline istream &operator>>(istream &is,vector> &v) { for(size_t i=0;i>v[i]; } return is; } struct Xor32{ using u32=uint32_t; u32 x=1234567; inline u32 rnd_make(){ x^=(x<<13); x=x^(x>>17); return x=x^(x<<5); } 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つを選ぶ first 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}; } }; 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(now-st).count(); } }; struct TestTimer{ chrono::high_resolution_clock::time_point st; unordered_map sum_time; unordered_map 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(now-start_time[s]).count(); #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:sum_time){ cerr< cnt; TestCounter(){} void count(const string &s){ #ifndef ONLINE_JUDGE cnt[s]++; #endif } void output()const{ #ifndef ONLINE_JUDGE for(auto m:cnt){ cerr< class DynamicArray{ public: array 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 &v){ if(size_!=v.size()) return false; for(int i=0;i inline void vsort(vector &v){ sort(v.begin(),v.end()); } //逆順ソート template inline void rvsort(vector &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 inline void Compress(vector &C){ sort(C.begin(),C.end()); C.erase(unique(C.begin(),C.end()),C.end()); } //要素数n 初期値x template inline vector vmake(size_t n,T x){ return vector(n,x); } //a,b,c,x data[a][b][c] 初期値x template auto vmake(size_t n,Args... args){ auto v=vmake(args...); return vector(n,move(v)); } //vは昇順 bool is_in(const vector &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] struct edge { int to; T cost; int id; edge()=default; edge(int to, T cost,int id) : to(to), cost(cost), id(id) {} }; template 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 &e){ return cost &e){ return cost<=e.cost; } }; template using WeightGraph=vector>>; //vector cout template inline ostream &operator<<(ostream &os,const vector &v) { bool sp=true; if(string(typeid(T).name())=="c") sp=false; for(size_t i=0;i cout template inline ostream &operator<<(ostream &os,const vector> &v) { for(size_t i=0;i inline ostream &operator<<(ostream &os,const pair &p) { os< inline ostream &operator<<(ostream &os,const map &M) { bool first=false; for(auto x:M){ if(first) os< inline ostream &operator<<(ostream &os,const set &S) { bool first=false; for(auto x:S){ if(first) os< inline istream &operator>>(istream &is,pair &p) { is>>p.first>>p.second; return is; } template void append(vector &v,const vector &vp){ for(auto p:vp){ v.push_back(p); } } //Fisher–Yatesアルゴリズム template void shuffle(vector &v){ int sz=v.size(); for(int i=sz-1;i>0;i--){ swap(v[Rand32()%(i+1)],v[i]); } } template 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); } ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ///++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ //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 bases_input(num_parts*2); vector middles_input(num_parts); vector tops_input(num_parts); void input(){ int dummy; cin>>dummy; cin>>num_tree; for(int i=0;i>middles_input[i].width; middles_input[i].id=i; } for(int i=0;i>middles_input[i].height; } for(int i=0;i>bases_input[i].width; bases_input[i].id=i; } for(int i=0;i>bases_input[i].height; } for(int i=0;i>tops_input[i].width; tops_input[i].id=i; } for(int i=0;i>tops_input[i].height; } } struct Ans{ array 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; } }; vector ans; vector bases_res; vector middles_res; vector 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 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 &ans){ int min_h=MAX; int max_h=-1; ll error_value=0; for(auto a:ans){ 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){ for(auto a:ans){ assert(a.is_valid()); cout<pre_height; return ans[i].height()=ans[j].height(); }; auto is_down=[&](int i,int pre_height){ return ans[i].height()b.height(); }); } bool done=false; int pre_height=ans[0].height(); for(int i=num_tree-1;i>=1;i--){ swap(ans[0].bases,ans[i].bases); if(is_valid(0) and is_valid(i) and is_up(0,pre_height,minimum) and is_not_change(0,i,minimum)){ done=true; break; } swap(ans[0].bases,ans[i].bases); swap(ans[0].middle,ans[i].middle); if(is_valid(0) and is_valid(i) and is_up(0,pre_height,minimum) and is_not_change(0,i,minimum)){ done=true; break; } swap(ans[0].middle,ans[i].middle); swap(ans[0].top,ans[i].top); if(is_valid(0) and is_valid(i) and is_up(0,pre_height,minimum) and is_not_change(0,i,minimum)){ done=true; break; } swap(ans[0].top,ans[i].top); } if(done) continue; for(int j=0;j<2;j++){ for(auto &b:bases_res){ swap(ans[0].bases[j],b); if(is_valid(0) and is_up(0,pre_height,minimum) and is_not_change(0,num_tree-1,minimum)){ done=true; break; } swap(ans[0].bases[j],b); } if(done) break; } if(done) continue; for(auto &m:middles_res){ swap(ans[0].middle,m); if(is_valid(0) and is_up(0,pre_height,minimum) and is_not_change(0,num_tree-1,minimum)){ done=true; break; } swap(ans[0].middle,m); } if(done) continue; for(auto &t:tops_res){ swap(ans[0].top,t); if(is_valid(0) and is_up(0,pre_height,minimum) and is_not_change(0,num_tree-1,minimum)){ done=true; break; } swap(ans[0].top,t); } } output(ans); cerr<>T; while(T--) solve(); }