結果

問題 No.5020 Averaging
コンテスト
ユーザー syndrome
提出日時 2026-01-10 01:25:08
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 994 ms / 1,000 ms
コード長 8,051 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,017 ms
コンパイル使用メモリ 365,852 KB
実行使用メモリ 7,852 KB
スコア 81,283,981
最終ジャッジ日時 2026-01-10 01:26:07
合計ジャッジ時間 58,467 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// (◕ᴗ◕✿)

// #pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define srep(i, s, n) for (ll i = s; i < (n); ++i)
#define len(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
using namespace std;
template<typename T> using vc = vector<T>;
template<typename T> using vv = vc<vc<T>>;
using vi = vc<int>;using vvi = vv<int>; using vvvi = vv<vi>;
using ll = long long;using vl = vc<ll>;using vvl = vv<ll>; using vvvl = vv<vl>;
using ld = long double; using vld = vc<ld>; using vvld = vc<vld>; using vvvld = vc<vvld>;
using uint = unsigned int;
using ull = unsigned long long;
const ld pi = 3.141592653589793;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
// const ll mod = 1000000007;
const ll mod = 998244353;

#define debug(var)  do{std::cout << #var << " : \n";view(var);}while(0)
template<typename T> void view(T e){cout << e << endl;}
template<typename T> void view(const vc<T>& v){for(const auto& e : v){ cout << e << " "; } cout << endl;}
template<typename T> void view(const vv<T>& vv){ for(const auto& v : vv){ view(v); } }

// #define DEBUG

#ifdef DEBUG
constexpr bool DEBUGMODE = true;
#else
constexpr bool DEBUGMODE = false;
#endif

ifstream in;
ofstream wrt;
string outputfile = "output.txt", inputfile = "input.txt";


unsigned int randxor(){
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
}
int randint(int a, int b) {return(a + randxor() % (b - a));}

struct Timer {
    public:
        Timer(int limit){
            start = chrono::high_resolution_clock::now();
            goal = start + chrono::milliseconds(limit);
        }

        inline double rate(){
            return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count();
        }

        inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;}

    private:
        chrono::high_resolution_clock::time_point start;
        chrono::high_resolution_clock::time_point goal;  
};

double log_table[70000];
//variable
constexpr int TIME_LIMIT = 990;
constexpr int L = 4;
constexpr int N = 45;
constexpr ll base = 5e17;
__int128_t A[N], B[N];

constexpr array<array<int, 4>, 23> perm = {
array<int, 4>{0, 1, 3, 2},
{0, 2, 1, 3},
{0, 2, 3, 1},
{0, 3, 1, 2},
{0, 3, 2, 1},
{1, 0, 2, 3},
{1, 0, 3, 2},
{1, 2, 0, 3},
{1, 2, 3, 0},
{1, 3, 0, 2},
{1, 3, 2, 0},
{2, 0, 1, 3},
{2, 0, 3, 1},
{2, 1, 0, 3},
{2, 1, 3, 0},
{2, 3, 0, 1},
{2, 3, 1, 0},
{3, 0, 1, 2},
{3, 0, 2, 1},
{3, 1, 0, 2},
{3, 1, 2, 0},
{3, 2, 0, 1},
{3, 2, 1, 0}
};

namespace simulated_annealing {

constexpr int transition_num = 2;
int transition_count[transition_num];
int success_count[transition_num];

using Cost = double;

struct Config {
    int time_limit;
    int temperature_type;
    double start_temp, goal_temp;
    int probability[transition_num];
};

struct State {
    Cost score;
    array<int, N> order;
    __int128_t sma, smb;
    State(){
        score = INF;
    }

    // void operator=(const State &other) {
    //     score = other.score;
    // }

    void init(){
        iota(all(order), -1);
        sma = A[0];
        smb = B[0];
        srep(i, 1, N){
            sma += A[i] << order[i];
            smb += B[i] << order[i];
        }
        ll a = abs((ll)(sma >> (N-1)) - base), b = abs((ll)(smb >> (N-1)) - base);
        if (a < b) swap(a, b);
        score = a + b / 1e3;
    }

    void transition01(Cost &threshold){
        transition_count[0]++;
        int a = randint(1, N), b = randint(1, N);
        while (b == a) b = randint(1, N);
        int c = randint(1, N);
        while (c == a || c == b) c = randint(1, N);
        int d = randint(1, N);
        while (d == a || d == b || d == c) d = randint(1, N);
        array<int, 4> idx = {a, b, c, d};
        array<int, 4> neword;
        int p = randint(0, 23);
        __int128_t mysma = sma, mysmb = smb;
        rep(i, 4){
            mysma -= A[idx[i]] << order[idx[i]];
            mysmb -= B[idx[i]] << order[idx[i]];
            neword[i] = order[idx[perm[p][i]]];
            mysma += A[idx[i]] << neword[i];
            mysmb += B[idx[i]] << neword[i];
        }
        ll ad = llabs((ll)(mysma >> (N-1)) - base), bd = llabs((ll)(mysmb >> (N-1)) - base);
        if (ad < bd) swap(ad, bd);
        Cost newscore = ad + bd / 1e3;
        if (newscore <= threshold){
            success_count[0]++;
            score = newscore;
            sma = mysma;
            smb = mysmb;
            rep(i, 4) order[idx[i]] = neword[i];
        }
    }
};

State simulated_annealing(const Config& config) {
    State best;
    State state[L];
    rep(i, L) state[i].init();
    Timer timer(config.time_limit);
    int roop = 0;
    double tmp = config.start_temp;
    double rate = 0;
    while (true){
        roop++;
        int randomint = randint(0, 100);
        rep(i, L){
            Cost threshold = state[i].score - tmp * log_table[randint(0, 70000)];
    
            // if (randomint < config.probability[0]){ // transition 01
            //     state[i].transition01(threshold);
            // }else{
            // }
            state[i].transition01(threshold);
    
            if (best.score > state[i].score){ // update best
                best = state[i];
            }
        }

        if (roop % 1000 == 0){
            // if (roop % 10000 == 0) cerr << state.score << " " << best.score << endl;
            rate = timer.rate();
            if (config.temperature_type == 0){
                tmp = config.start_temp + rate * (config.goal_temp - config.start_temp);
            }else{
                tmp = config.start_temp * pow(config.goal_temp / config.start_temp, rate);
            }
            if (rate > 1.0){
                break;
            }
        }
    }
    cerr << "roop : " << roop << endl;
    cerr << "score : " << best.score << endl;
    rep(i, transition_num) cerr << "transition" << i << " conversion rate : " << fixed << setprecision(4) << success_count[i] / (double)transition_count[i] * 100 << " %  " << success_count[i] << " / " << transition_count[i] << endl;
    return best;
};

}// namespace simulated_annealing

struct Solver{
    simulated_annealing::State ans;
    void input(){
        if (DEBUGMODE){
            in.open(inputfile);
            cin.rdbuf(in.rdbuf());
        }
        int n; cin >> n;
        rep(i, N){
            ll a, b; cin >> a >> b;
            A[i] = a;
            B[i] = b;
        }
    }

    void init(){
		double n = 1 / (double)(2 * 70000);
		for (int i = 0; i < 70000; i++) {
			log_table[i] = log(((double)i / 70000) + n);
		}
    }

    void output(){
        array<int, N - 1> P; iota(all(P), 1);
        sort(all(P), [&](auto i, auto j){return ans.order[i] < ans.order[j];});
        if (DEBUGMODE){
            wrt << N - 1 << endl;
            for (auto id : P){
                wrt << 1 << ' ' << id + 1 << endl;
                ll a = (A[0] + A[id]) / 2, b = (B[0] + B[id]) / 2;
                A[0] = a;
                B[0] = b;
                A[id] = a;
                B[id] = b;
            }
            rep(i, N) wrt << (ll)A[i] << ' ' << (ll)B[i] << endl;
        }else{
            cout << N - 1 << endl;
            for (auto id : P){
                cout << 1 << ' ' << id + 1 << endl;
            }
        }
    }

    void run(){
        Timer timer(TIME_LIMIT);
        input();
        init();
        simulated_annealing::Config config = {
            TIME_LIMIT - timer.get_time(),
            1,
            1e19,
            3,
            {70, 100}
        };
        ans = simulated_annealing::simulated_annealing(config);
        output();
    }
};

int main(){
    wrt.open(outputfile, ios::out);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    Solver solver;
    solver.run();
    wrt.close();
    return 0;
}
0