結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 13:59:52 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 903 ms / 1,000 ms |
コード長 | 16,838 bytes |
コンパイル時間 | 3,745 ms |
コンパイル使用メモリ | 234,208 KB |
実行使用メモリ | 6,676 KB |
スコア | 29,252,036 |
最終ジャッジ日時 | 2024-02-25 14:00:45 |
合計ジャッジ時間 | 51,913 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge12 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
/*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<bits/stdc++.h>using namespace std;using ll=long long int;//using Int=__int128;#define mask(x) ((1LL<<x)-1)#define ALL(A) A.begin(),A.end()template<typename T1,typename T2> bool chmin(T1 &a,T2 b){if(a<=b)return 0; a=b; return 1;}template<typename T1,typename T2> bool chmax(T1 &a,T2 b){if(a>=b)return 0; a=b; return 1;}template<typename T> 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<int,int>;using pil=pair<int,ll>;using pli=pair<ll,int>;using pll=pair<ll,ll>;using psi=pair<string,int>;using pis=pair<int,string>;using psl=pair<string,ll>;using pls=pair<ll,string>;using pss=pair<string,string>;template<class T>using minimum_queue=priority_queue<T,vector<T>,greater<T>>;using Graph=vector<vector<int>>;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 cintemplate<typename T>inline istream &operator>>(istream &is,vector<T> &v) {for(size_t i=0;i<v.size();i++) is>>v[i];return is;}//0-indexed vector cintemplate<typename T>inline istream &operator>>(istream &is,vector<vector<T>> &v) {for(size_t i=0;i<v.size();i++){is>>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<int,2> 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_JUDGElocal=1.0;#endifstart();}void start(){st=chrono::high_resolution_clock::now();}int span()const{auto now=chrono::high_resolution_clock::now();return chrono::duration_cast<chrono::milliseconds>(now-st).count();}};struct TestTimer{chrono::high_resolution_clock::time_point st;unordered_map<string,ll> sum_time;unordered_map<string,chrono::high_resolution_clock::time_point> start_time;TestTimer(){}void start(const string &s){#ifndef ONLINE_JUDGEstart_time[s]=chrono::high_resolution_clock::now();#endif}void end(const string &s){#ifndef ONLINE_JUDGEauto now=chrono::high_resolution_clock::now();sum_time[s]+=chrono::duration_cast<chrono::nanoseconds>(now-start_time[s]).count();#endif}void output()const{#ifndef ONLINE_JUDGEfor(auto m:sum_time){cerr<<m.first<<": "<<m.second/1e6<<"ms"<<endl;}#endif}};struct TestCounter{unordered_map<string,ll> cnt;TestCounter(){}void count(const string &s){#ifndef ONLINE_JUDGEcnt[s]++;#endif}void output()const{#ifndef ONLINE_JUDGEfor(auto m:cnt){cerr<<m.first<<": "<<m.second<<endl;}#endif}};Timer TIME;Xor32 Rand32;Xor64 Rand64;TestTimer testTimer;TestCounter testCounter;//https://atcoder.jp/contests/asprocon9/submissions/34659956template<class T,int CAPACITY>class DynamicArray{public:array<T,CAPACITY> 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<e.size_;i++){array_[i]=e[i];}size_=e.size_;}bool operator==(const DynamicArray &v){if(size_!=v.size_) return false;for(int i=0;i<size_;i++){if(array_[i]!=v[i]){return false;}}return true;}bool operator==(const vector<T> &v){if(size_!=v.size()) return false;for(int i=0;i<size_;i++){if(array_[i]!=v[i]){return false;}}return true;}void clear(){size_=0;}//O(1)//末尾と入れ替える。順序が保持されないが高速void swap_remove(int idx){array_[idx]=array_[size_-1];size_--;}//最初から見ていき、一致したものを削除(remove)bool erase(T value){for(int i=0;i<size_;i++){if(array_[i]==value){remove(i);return true;}}return false;}void reverse(){for(int i=0;i<size_/2;i++){swap(array_[i],array_[size_-1-i]);}}//O(size)//順序を気にしない場合、swap_removeの方がいいvoid remove(int idx){for(int i=idx;i<size_-1;i++){array_[i]=array_[i+1];}size_--;}void fill(T x){for(int i=0;i<size_;i++){array_[i]=x;}}};//ソートtemplate<typename T>inline void vsort(vector<T> &v){sort(v.begin(),v.end());}//逆順ソートtemplate<typename T>inline void rvsort(vector<T> &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<typename T>inline void Compress(vector<T> &C){sort(C.begin(),C.end());C.erase(unique(C.begin(),C.end()),C.end());}//要素数n 初期値xtemplate<typename T>inline vector<T> vmake(size_t n,T x){return vector<T>(n,x);}//a,b,c,x data[a][b][c] 初期値xtemplate<typename... Args>auto vmake(size_t n,Args... args){auto v=vmake(args...);return vector<decltype(v)>(n,move(v));}//vは昇順bool is_in(const vector<int> &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]<x) ng=mid;else ok=mid;}if(v[ok]==x) return true;return false;}template<typename T >struct edge {int to;T cost;int id;edge()=default;edge(int to, T cost,int id) : to(to), cost(cost), id(id) {}};template<class T >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<T> &e){return cost<e.cost;}bool operator<=(const Edge<T> &e){return cost<=e.cost;}};template<typename T>using WeightGraph=vector<vector<edge<T>>>;//vector couttemplate<typename T>inline ostream &operator<<(ostream &os,const vector<T> &v) {bool sp=true;if(string(typeid(T).name())=="c") sp=false;for(size_t i=0;i<v.size();i++){if(i and sp) os<<" ";os<<v[i];}return os;}//vector<vector> couttemplate<typename T>inline ostream &operator<<(ostream &os,const vector<vector<T>> &v) {for(size_t i=0;i<v.size();i++){os<<v[i];if(i+1!=v.size()) os<<"\n";}return os;}//pair couttemplate<typename T, typename U>inline ostream &operator<<(ostream &os,const pair<T,U> &p) {os<<p.first<<" "<<p.second;return os;}//map couttemplate<typename F, typename S>inline ostream &operator<<(ostream &os,const map<F,S> &M) {bool first=false;for(auto x:M){if(first) os<<endl;first=true;os<<x;}return os;}//set couttemplate<typename T>inline ostream &operator<<(ostream &os,const set<T> &S) {bool first=false;for(auto x:S){if(first) os<<endl;first=true;os<<x;}return os;}//pair cintemplate<typename T, typename U>inline istream &operator>>(istream &is,pair<T,U> &p) {is>>p.first>>p.second;return is;}template<typename T>void append(vector<T> &v,const vector<T> &vp){for(auto p:vp){v.push_back(p);}}//Fisher–Yatesアルゴリズムtemplate<typename T>void shuffle(vector<T> &v){int sz=v.size();for(int i=sz-1;i>0;i--){swap(v[Rand32()%(i+1)],v[i]);}}template<class T,class U>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/162613struct SimulatedAnnealing{float temp_start; //差の最大値(あくまでも参考)float temp_end; //差の最小値(あくまでも参考)float time_start;float time_end;bool is_hill;bool minimum;int interval; //intervalごとに温度の再計算float temp_now;int cnt_calc_temp;/*0:線形1:pow pow2:指数*/int temp_type;//SimulatedAnnealing(){}SimulatedAnnealing(float temp_start,float 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/35326979temp_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%8Btemp_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;float temp=calc_temp();return exp(diff/temp);}inline bool operator()(float 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;float prob = exp(diff/calc_temp());if(Rand32.gen_bool(prob)){testCounter.count("minus_change");return true;}else return false;}//最大化の場合,返り値<変化量なら遷移してもよいfloat calc_tolerance(float prob){float tolerance=log(prob)*calc_temp();if(minimum) tolerance*=-1;return tolerance;}//log(prob)*temp prob:[0,1]の乱数float calc_tolerance(){float 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#endifnamespace 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<Card> inputs;ll middle=500000000000000000;void input(){int dummy;cin>>dummy;inputs.resize(num_cards);for(int i=0;i<num_cards;i++){cin>>inputs[i].A>>inputs[i].B;}}struct Solver{vector<int> perm;ll calc_score(const vector<int> &perm){ll 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>>j);b+=(inputs[perm[i]].B>>j);}//cout<<abs(middle-a)<<" "<<abs(middle-b)<<endl;return max(abs(middle-a),abs(middle-b));}void solve(){for(int i=0;i<num_cards;i++){perm.push_back(i);}SimulatedAnnealing SA(1000,0,TIME.span(),900,false,true,0,10000);ll best_score=calc_score(perm);auto best_perm=perm;while(TIME.span()<900){perm=best_perm;auto uv=Rand32.two(num_cards);if(uv[0]==0 or uv[1]==0) continue;swap(perm[uv[0]],perm[uv[1]]);ll now_score=calc_score(perm);if(SA(now_score-best_score)){//cout<<best_score<<endl;best_score=now_score;best_perm=perm;}}perm=best_perm;}void output(){cout<<44<<endl;for(int i=44;i>=1;i--){cout<<perm[i]+1<<" "<<perm[i-1]+1<<endl;assert(perm[i]!=perm[i-1]);}ll score=calc_score(perm);cerr<<ll(2e6-1e5*log10l(score+1))<<endl;}};void solve(){input();Solver solver;solver.solve();solver.output();#ifndef ONLINE_JUDGEtestTimer.output();testCounter.output();cerr<<TIME.span()<<"ms"<<endl;//cerr<<"score: "<<simulate(best_grid,true)<<endl;#endif}int main(const int argc,const char** argv){#ifndef OPTUNAif(argc!=1){}#endifFastIO();int T=1;//cin>>T;while(T--) solve();}