#pragma GCC target("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #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 HalfPow{ double a[100]; constexpr HalfPow(){ a[0] = 1.0; for(int i=1;i<100;i++){ a[i] = a[i-1] * 0.5; } return; } }; constexpr auto p = HalfPow(); struct IndexSet { vector que; vector pos; IndexSet() {} IndexSet(int n) : pos(n), que(n) { iota(pos.begin(),pos.end(),0); iota(que.begin(),que.end(),0); } void add(int v) { pos[v] = que.size(); que.push_back(v); } void remove(int v) { int p = pos[v]; int b = que.back(); que[p] = b; que.pop_back(); pos[b] = p; pos[v] = -1; } bool contains(int v) const { return pos[v] != -1; } int size() const { return que.size(); } }; 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]; a[i] -= 500000000000000000ll; b[i] -= 500000000000000000ll; } } }; //操作を表す構造体 struct Operation{ size_t i; }; //操作を元に戻すための情報を表す構造体 struct RollbackOperation{ size_t i; double mul; }; struct State{ IO *io; double a,b; IndexSet unused; int cnt; //初期状態の生成 State(IO &_io) : io(&_io){ a = 0, b = 0; unused = IndexSet(io->n); cnt = 1; }; //スコア計算 ull score(){ return max(abs(a),abs(b)); }; //ハッシュ値計算 ull hash(){ ull h = ull(a)^ull(b); return h; }; //状態を更新せずスコアとハッシュのみを計算 pair try_apply(Operation op, ull score, ull hash){ double ave_a = a + p.a[cnt] * (double)io->a[op.i]; double ave_b = b + p.a[cnt] * (double)io->b[op.i]; hash = ull(ave_a) ^ ull(ave_b); score = max(abs(ave_a),abs(ave_b)); if(score == 0){ cerr << "a : " << a << endl; cerr << "b : " << b << endl; cerr << "ave_a : " << ave_a << endl; cerr << "ave_b : " << ave_b << endl; cerr << "abs(ave_a) : " << abs(ave_a) << endl; cerr << "abs(ave_b) : " << abs(ave_b) << endl; exit(1); } return {score,hash}; }; //状態を更新する //元の状態に戻すための情報を返す RollbackOperation apply(Operation op){ a += p.a[cnt] * io->a[op.i]; b += p.a[cnt] * io->b[op.i]; RollbackOperation rop = {op.i, p.a[cnt]}; cnt++; unused.remove(op.i); return rop; } //applyから返された情報を元に状態を戻す void rollback(RollbackOperation op){ a -= op.mul * io->a[op.i]; b -= op.mul * io->b[op.i]; cnt--; unused.add(op.i); } }; 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;ichild; // 有効な子だけにする 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){ ull turn = io.n; constexpr ull beam_width = 10000; 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()); } cerr << "best score : " << next_states[0].score << endl; 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); bool zero_merged = false; int last = -1; reverse(ops.begin(),ops.end()); cout << ops.size()-1 << endl; for(auto op:ops){ if(last == -1){ last = op.i; } else{ if(zero_merged){ cout << 1 << " " << op.i+1 << endl; } else{ cout << last+1 << " " << op.i+1 << endl; } last = op.i; } if(last == 0){ zero_merged = true; } } #ifndef ONLINE_JUDGE cerr << "time : " << get_time()-start_time << "ms" << endl; #endif }