#include #include #include #include #include #include #include #include #include using namespace std; using ull = unsigned long long; using ll = long long; using vll = vector; inline double get_time() { using namespace std::chrono; return duration_cast(system_clock::now().time_since_epoch()).count(); } double start_time = get_time(); struct IO{ int n; vll a,b; IO(){} void input(){ cin >> n; a.resize(n); b.resize(n); for(int i=0;i> a[i] >> b[i]; } } }; //操作を表す構造体 struct Operation{ size_t x,y; }; //操作を元に戻すための情報を表す構造体 struct RollbackOperation{ size_t x,y; pair x_val; pair y_val; }; struct State{ IO *io; vll a,b; //初期状態の生成 State(IO &_io) : io(&_io){ a = io->a; b = io->b; }; //スコア計算 ull score(){ ll diff_a = a[0] - 500000000000000000ll; ll diff_b = b[0] - 500000000000000000ll; return max(abs(diff_a),abs(diff_b)); }; //ハッシュ値計算 ull hash(){ ull h = 0; for(int i=0;in;i++){ h ^= a[i]; h ^= b[i]; } return h; }; //状態を更新せずスコアとハッシュのみを計算 pair try_apply(Operation op, ull score, ull hash){ if(op.x==0 || op.y==0){ ll a_ave = (a[op.x] + a[op.y])/2; ll b_ave = (b[op.x] + b[op.y])/2; ll a_diff = abs(a_ave-500000000000000000ll); ll b_diff = abs(b_ave-500000000000000000ll); score = max(a_diff,b_diff); } hash ^= a[op.x]; hash ^= b[op.x]; hash ^= a[op.y]; hash ^= b[op.y]; return {score,hash}; }; //状態を更新する //元の状態に戻すための情報を返す RollbackOperation apply(Operation op){ ll a_ave = (a[op.x] + a[op.y])/2; ll b_ave = (b[op.x] + b[op.y])/2; RollbackOperation rop = {op.x,op.y,{a[op.x],b[op.x]},{a[op.y],b[op.y]}}; a[op.x] = a_ave; b[op.x] = b_ave; a[op.y] = a_ave; b[op.y] = b_ave; return rop; } //applyから返された情報を元に状態を戻す void rollback(RollbackOperation op){ a[op.x] = op.x_val.first; b[op.x] = op.x_val.second; a[op.y] = op.y_val.first; b[op.y] = op.y_val.second; } }; struct Node; struct Cand{ Operation op; shared_ptr parent; ull score; ull hash; ull p; //優先度 }; using Parent = optional>>; using Children = vector>>; struct Node{ Parent parent; Children child; ull score; ull hash; Node(Parent parent, Children child, ull score, ull hash): parent(parent),child(child),score(score),hash(hash){} }; // 多スタート用に構造体にまとめておくと楽 struct Tree{ State state; shared_ptr node; ull rank; // 注意: depthは深くなっていくごとに-1されていく void dfs(vector& next_states,bool one,ull& p,ull depth){ if(depth==0){ ull score=node->score; ull hash=node->hash; // 検算 // assert(score==state.score()); // assert(hash==state.hash()); vector ops; //次の操作を列挙 for(int i=0;in;i++){ for(int j=i+1;jn;j++){ if(i==j) continue; ops.emplace_back(i,j); } } //次の操作を全部試す for(auto const& op:ops){ auto [next_score,next_hash]=state.try_apply(op,score,hash); next_states.emplace_back(Cand{op,node,next_score,next_hash,p}); p+=1; } } else{ auto node_backup=node; auto child=&node_backup->child; // 有効な子だけにする child->erase(remove_if(child->begin(),child->end(),[](pair>& x){return x.second.expired();}),child->end()); bool next_one=one&child->size()==1; // 定数調整の必要あり if(depth==5){ p=0; } ++rank; for(const auto& [op,ptr]:*child){ node=ptr.lock(); RollbackOperation backup=state.apply(op); dfs(next_states,next_one,p,depth-1); if(!next_one){ state.rollback(backup); } } if(!next_one){ node=node_backup; --rank; } } } }; vector beam(IO &io){ constexpr ull turn = 50; constexpr ull beam_width = 2000; State state(io); ull score = state.score(); ull hash = state.hash(); // 検算 /* assert(score==state.score()); assert(hash==state.hash()); */ Tree tree{move(state), shared_ptr(new Node(Parent(),Children(),score,hash)),0}; vector> cur{tree.node}; vector next_states; unordered_set hash_set; for(ull i=0;i beam_width){ nth_element(next_states.begin(),next_states.begin()+beam_width,next_states.end(), [](Cand& a, Cand& b){ if(a.score == b.score){ return a.p > b.p; } else return a.score < b.score; }); next_states.erase(next_states.begin()+beam_width,next_states.end()); } cur.clear(); hash_set.clear(); for(const auto&[op,parent,next_score,next_hash,p]:next_states){ //重複除去 if(hash_set.count(next_hash)==0){ hash_set.insert(next_hash); auto child_ptr=shared_ptr(new Node(Parent({op,parent}),Children(),score,hash)); parent->child.emplace_back(op,weak_ptr(child_ptr)); cur.emplace_back(child_ptr); } } } } //最良の状態を選択 ull arg_min = -1; ull min = 1ull<<60; for(ull i=0;i ret{op}; // 操作の復元 while(ptr->parent.has_value()){ auto [op,parent]=ptr->parent.value(); ret.emplace_back(op); ptr=parent; } reverse(ret.begin(),ret.end()); return ret; } int main(){ IO io; io.input(); auto ops = beam(io); cout << ops.size() << endl; for(auto [x,y]:ops){ cout << x+1 << " " << y+1 << endl; } cerr << "time : " << get_time()-start_time << "ms" << endl; }