/* 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>>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 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(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); } //http://gasin.hatenadiary.jp/entry/2019/09/03/162613 struct SimulatedAnnealing{ long double temp_start; //差の最大値(あくまでも参考) long double temp_end; //差の最小値(あくまでも参考) float time_start; float time_end; bool is_hill; bool minimum; int interval; //intervalごとに温度の再計算 long double temp_now; int cnt_calc_temp; /* 0:線形 1:pow pow 2:指数 */ int temp_type; //SimulatedAnnealing(){} SimulatedAnnealing(long double temp_start,long double 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; long double temp=calc_temp(); return exp(diff/temp); } inline bool operator()(long double 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; long double prob = exp(diff/calc_temp()); if(Rand32.gen_bool(prob)){ testCounter.count("minus_change"); return true; } else return false; } //最大化の場合,返り値<変化量なら遷移してもよい long double calc_tolerance(long double prob){ long double tolerance=log(prob)*calc_temp(); if(minimum) tolerance*=-1; return tolerance; } //log(prob)*temp prob:[0,1]の乱数 long double calc_tolerance(){ long double 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); }; const int num_cards=45; struct Card{ ll A; ll B; }; vector inputs; ll middle=500000000000000000; void input(){ int dummy; cin>>dummy; inputs.resize(num_cards); for(int i=0;i>inputs[i].A>>inputs[i].B; } } struct Solver{ vector perm; vector ratio; ll a=0,b=0; ll calc_score(const vector &perm,bool output=false){ a=0,b=0; for(int i=0;i<45;i++){ int j=i+1; if(i==44) j=44; a+=(inputs[perm[i]].A>>ratio[i]); b+=(inputs[perm[i]].B>>ratio[i]); } if(output) cout< &perm,array &uv,bool update=false){ ll new_a=a,new_b=b; for(int i=0;i<2;i++){ new_a-=(inputs[perm[uv[i]]].A>>ratio[uv[i]]); new_b-=(inputs[perm[uv[i]]].B>>ratio[uv[i]]); int j=1-i; new_a+=(inputs[perm[uv[j]]].A>>ratio[uv[i]]); new_b+=(inputs[perm[uv[j]]].B>>ratio[uv[i]]); } if(update){ a=new_a; b=new_b; } return max(abs(middle-new_a),abs(middle-new_b)); } void solve(){ ratio.push_back(11); for(int i=14;i>=4;i--){ ratio.push_back(i); ratio.push_back(i); ratio.push_back(i-1); ratio.push_back(i-2); } for(int i=0;i900) break; } auto uv=Rand32.two(num_cards); if(uv[0]==0 or uv[1]==0) continue; ll now_score=calc_score_diff(perm,uv); //swap(perm[uv[0]],perm[uv[1]]); //cerr<now_score){ best_score=now_score; best_perm=perm; } } } perm=best_perm; } void output(){ cout<<44<=1;i--){ // cout<>T; while(T--) solve(); }