#1162813 (C++23) No.5020 Averaging

• 問題: No.5020 Averaging
• ユーザー: FplusFplusF
• 提出日時: 2026-05-04 21:37:06
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 902 ms / 1,000 ms
• コード長: 5,914 bytes
• コンパイル時間: 3,379 ms
• コンパイル使用メモリ: 346,496 KB
• 実行使用メモリ: 6,400 KB
• スコア: 42,120,291
• 最終ジャッジ日時: 2026-05-04 21:38:04
• 合計ジャッジ時間: 53,838 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
other	AC * 50

ソースコード

#include <bits/stdc++.h>
using namespace std;
using pii=pair<int,int>;
using tii=tuple<int,int,int>;
using qii=tuple<int,int,int,int>;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
constexpr int INF=1e9;
constexpr ll INF_ll=1e18;
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define replr(i,l,r) for (int i=(int)(l);i<(int)(r);i++)
#define all(v) v.begin(),v.end()
#define len(v) ((int)v.size())
template<class T> inline bool chmin(T &a,T b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T &a,T b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

template<class T> inline bool chmin_ref(T &a,const T &b){
    if(a>b){
        a=b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax_ref(T &a,const T &b){
    if(a<b){
        a=b;
        return true;
    }
    return false;
}

namespace Timer{
    chrono::steady_clock::time_point program_start,start;
    void program_start_snap(){
        program_start=start=chrono::steady_clock::now();
    }
    void snap(){
        start=chrono::steady_clock::now();
    }
    int get_ms(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-start).count();
        return ms;
    }
    int get_ms_all_program(){
        auto now=chrono::steady_clock::now();
        int ms=chrono::duration_cast<chrono::milliseconds>(now-program_start).count();
        return ms;
    }
}

mt19937 mt;
uint32_t rand_int(uint32_t r){  //[0,r)
    assert(r!=0);
    return ((uint64_t)mt()*r)>>32;
}
int rand_int(int l,int r){  //[l,r)
    assert(l<r);
    return l+rand_int(r-l);
}
constexpr double one_div_mt_max=1.0/(double)mt19937::max();
double rand_double(){  //[0.0,1.0]
    return mt()*one_div_mt_max;
}
double rand_double(double l,double r){  //[l,r]
    return l+rand_double()*(r-l);
}
template<class T> T get_random_element(const vector<T> &v){
    assert(!v.empty());
    return v[rand_int(len(v))];
}

template<class T> void add(vector<T> &a,vector<T> b){
    for(auto i:b) a.push_back(i);
}

template<class SA_State> SA_State SA(const SA_State &first_state,int limit_ms,double start_temp,double end_temp=0.0){

    SA_State state=first_state,best_state=state;
    

    
    int loop_cnt=0,accept_cnt=0,update_cnt=0;
    
    int ms=0;
    
    double temp=start_temp;
    
    Timer::snap();
    
    
    while(true){

        if((loop_cnt&63)==63){
            
            ms=Timer::get_ms();
            
            if(limit_ms<=ms) break;
            
            //double t=(double)ms/limit_ms;
            
            temp=start_temp-(start_temp-end_temp)/limit_ms*ms;
            //temp=pow(start_temp,1-t)*pow(end_temp,t);
            
        }
        
        loop_cnt++;
        
        
        double accept_diff=log(rand_double())*temp;
        

        bool accepted=state.modify(accept_diff);
        
        if(accepted){
            
            accept_cnt++;
        
            if(state.score<best_state.score){
                best_state=state;
                cerr << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
                update_cnt++;
            }
        }
    }

    
    cerr << "[result] " << "score:" << best_state.score << " ms:" << ms << " loop_cnt:" << loop_cnt << " accept_cnt:" << accept_cnt << " update_cnt:" << update_cnt << '\n';
    
    return best_state;
};


constexpr int N=45;

array<ll,N> A,B;

constexpr ll X=50,L=5e17;

namespace Solver{
    
    struct State{
        
        vector<pii> actions;
        
        ll score=0;
        
        State():actions(X){
            rep(i,X){
                actions[i].first=0;
                actions[i].second=i%(N-1)+1;
            }
            score=calc_score();
        }
        
        ll calc_score(){
            
            array<ll,N> a=A,b=B;
            
            for(auto [u,v]:actions){
                a[u]=a[v]=(a[u]+a[v])/2;
                b[u]=b[v]=(b[u]+b[v])/2;
            }
            return max(abs(L-a[0]),abs(L-b[0]));
        }
        
        bool modify1(double accept_diff){
            
            int t=rand_int(X);
            
            auto pre_action=actions[t];
            
            actions[t].second=rand_int(1,N);
            
            ll new_score=calc_score();
            
            if(accept_diff<=score-new_score){
                score=new_score;
                return true;
            }else{
                actions[t]=pre_action;
                return false;
            }
        }
        
        bool modify2(double accept_diff){
            
            int a=rand_int(X),b=rand_int(X);
            
            swap(actions[a],actions[b]);
            
            ll new_score=calc_score();
            
            if(accept_diff<=score-new_score){
                score=new_score;
                return true;
            }else{
                swap(actions[a],actions[b]);
                return false;
            }
        }
        
        bool modify(double accept_diff){
            
            if(rand_int(2)) return modify1(accept_diff);
            else return modify2(accept_diff);
        }
    };
    
    
    void solve(){
        State state;
        state=SA<State>(state,900,1e15);
        
        cout << len(state.actions) << '\n';
        
        for(auto [u,v]:state.actions){
            cout << u+1 << ' ' << v+1 << '\n';
        }
        
        cerr << (int)floor(2000000-100000*log10(state.score+1)) << '\n';
        
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Timer::program_start_snap();
    
    int n;
    cin >> n;
    assert(n==N);
    
    rep(i,N) cin >> A[i] >> B[i];


    Solver::solve();
    exit(0);
}