#include #include #define rep(i,a,b) for(int i=a;i=a;i--) #define all(x) (x).begin(),(x).end() #define pb(x) push_back(x); templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b P; const int N = 45; const int M = 50; ll A[N],B[N]; void Input(){ int _n;cin >> _n; rep(i,0,N)cin >> A[i] >> B[i]; } struct Solution{ int X=0; vector u,v; P Simulate(){ ll a[N],b[N];rep(i,0,N)a[i]=A[i],b[i]=B[i]; rep(i,0,X){ ll tmp1=(a[u[i]]+a[v[i]])/2; ll tmp2=(b[u[i]]+b[v[i]])/2; a[u[i]]=tmp1;a[v[i]]=tmp1; b[u[i]]=tmp2;b[v[i]]=tmp2; } return P(a[0],b[0]); } ll CalcScore(){ P score=Simulate(); return max(abs(BASE-score.first),abs(BASE-score.second)); } void Output(){ cout << X << endl; rep(i,0,X)cout << u[i]+1 << " " << v[i]+1 << endl; } }; Solution InitSolve(){ // Solution res_sol; // rep(i,1,N){ // res_sol.u.pb(0); // res_sol.v.pb(i); // res_sol.X++; // } // shuffle(all(res_sol.v),engine); Solution res_sol; set st; st.insert(0); rep(i,0,M){ int x=random()%N; int y=random()%N; while(true){ if(x!=y&&(st.count(x)||st.count(y))){ break; } x=random()%N; y=random()%N; } res_sol.u.pb(x); res_sol.v.pb(y); res_sol.X++; st.insert(x); st.insert(y); } reverse(all(res_sol.u)); reverse(all(res_sol.v)); return res_sol; } Solution Suggest(Solution &sol){ // Solution next_sol=sol; // int idx1=random()%sol.X; // int idx2=random()%sol.X; // while(idx1==idx2){ // idx2=random()%sol.X; // } // swap(next_sol.u[idx1],next_sol.u[idx2]); // swap(next_sol.v[idx1],next_sol.v[idx2]); Solution next_sol=sol; int idx=random()%M; int x=random()%N; int y=random()%N; while(true){ bool break_flag=true; if(x!=y){ break_flag=false; rep(nidx,idx+1,M){ if(sol.u[nidx]==x||sol.v[nidx]==x){ break_flag=true; break; } if(sol.u[nidx]==y||sol.v[nidx]==y){ break_flag=true; break; } } } else{ break_flag=false; } if(break_flag){ break; } idx=random()%M; x=random()%N; y=random()%N; } next_sol.u[idx]=x; next_sol.v[idx]=y; return next_sol; } Solution HillClimbing(Solution sol){ Solution now_sol=sol; ll now_score=now_sol.CalcScore(); Solution best_sol=now_sol; ll best_score=now_score; while((double)(clock()-start)/CLOCKS_PER_SEC