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

• 問題: No.5020 Averaging
• ユーザー: eijirou
• 提出日時: 2024-02-25 16:07:32
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 953 ms / 1,000 ms
• コード長: 11,435 bytes
• コンパイル時間: 8,423 ms
• コンパイル使用メモリ: 351,236 KB
• 実行使用メモリ: 6,548 KB
• スコア: 55,138,965
• 最終ジャッジ日時: 2024-02-25 16:08:31
• 合計ジャッジ時間: 58,368 ms
• ジャッジサーバーID （参考情報）: judge12 / judge15

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	952 ms; 6,548 KB
testcase_01	AC	952 ms; 6,548 KB
testcase_02	AC	952 ms; 6,548 KB
testcase_03	AC	951 ms; 6,548 KB
testcase_04	AC	952 ms; 6,548 KB
testcase_05	AC	952 ms; 6,548 KB
testcase_06	AC	952 ms; 6,548 KB
testcase_07	AC	952 ms; 6,548 KB
testcase_08	AC	952 ms; 6,548 KB
testcase_09	AC	952 ms; 6,548 KB
testcase_10	AC	952 ms; 6,548 KB
testcase_11	AC	952 ms; 6,548 KB
testcase_12	AC	952 ms; 6,548 KB
testcase_13	AC	952 ms; 6,548 KB
testcase_14	AC	952 ms; 6,548 KB
testcase_15	AC	952 ms; 6,548 KB
testcase_16	AC	952 ms; 6,548 KB
testcase_17	AC	953 ms; 6,548 KB
testcase_18	AC	951 ms; 6,548 KB
testcase_19	AC	952 ms; 6,548 KB
testcase_20	AC	953 ms; 6,548 KB
testcase_21	AC	952 ms; 6,548 KB
testcase_22	AC	952 ms; 6,548 KB
testcase_23	AC	952 ms; 6,548 KB
testcase_24	AC	952 ms; 6,548 KB
testcase_25	AC	952 ms; 6,548 KB
testcase_26	AC	952 ms; 6,548 KB
testcase_27	AC	952 ms; 6,548 KB
testcase_28	AC	952 ms; 6,548 KB
testcase_29	AC	952 ms; 6,548 KB
testcase_30	AC	952 ms; 6,548 KB
testcase_31	AC	952 ms; 6,548 KB
testcase_32	AC	951 ms; 6,548 KB
testcase_33	AC	952 ms; 6,548 KB
testcase_34	AC	952 ms; 6,548 KB
testcase_35	AC	952 ms; 6,548 KB
testcase_36	AC	952 ms; 6,548 KB
testcase_37	AC	952 ms; 6,548 KB
testcase_38	AC	952 ms; 6,548 KB
testcase_39	AC	952 ms; 6,548 KB
testcase_40	AC	952 ms; 6,548 KB
testcase_41	AC	952 ms; 6,548 KB
testcase_42	AC	953 ms; 6,548 KB
testcase_43	AC	953 ms; 6,548 KB
testcase_44	AC	952 ms; 6,548 KB
testcase_45	AC	952 ms; 6,548 KB
testcase_46	AC	951 ms; 6,548 KB
testcase_47	AC	952 ms; 6,548 KB
testcase_48	AC	952 ms; 6,548 KB
testcase_49	AC	952 ms; 6,548 KB

ソースコード

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#ifdef ONLINE_JUDGE
// #define NDEBUG
#endif // ONLINE_JUDGE

#include <bits/stdc++.h>
#include <atcoder/all>

#ifndef ONLINE_JUDGE
#include <omp.h>
#endif // ONLINE_JUDGE

using namespace std;
using namespace atcoder;

#define ll long long int
#define ull unsigned long long int

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;
}

class Xorshift {
    public:
        explicit Xorshift(uint32_t seed): x_(seed) {
            assert(seed);
        }

        // [0, stop)
        uint32_t randrange(uint32_t stop) {
            assert(stop > 0);
            next();
            return x_ % stop;
        }

        // [start, stop)
        uint32_t randrange(uint32_t start, uint32_t stop) {
            assert(start < stop);
            next();
            return start + x_ % (stop - start);
        }

        // [a, b]
        uint32_t randint(uint32_t a, uint32_t b) {
            assert(a <= b);
            return randrange(a, b + 1);
        }

        // [0.0, 1.0]
        double random() {
            next();
            return static_cast<double>(x_) * (1.0 / static_cast<double>(UINT32_MAX));
        }

        // [a, b] or [b, a]
        double uniform(double a, double b) {
            return a + (b - a) * random();
        }

    private:
        uint32_t x_;

        void next() {
            x_ ^= x_ << 13;
            x_ ^= x_ >> 17;
            x_ ^= x_ << 5;
        }
};

class IndexSet {
    public:
        explicit IndexSet(int n): n_(n), positions_(n, -1) {}

        void insert(int x) {
            assert(0 <= x && x < n_);
            assert(!contains(x));
            positions_[x] = data_.size();
            data_.push_back(x);
        }

        void erase(int x) {
            assert(0 <= x && x < n_);
            assert(contains(x));
            int i = positions_[x];
            int y = data_.back();
            data_[i] = y;
            data_.pop_back();
            positions_[y] = i;
            positions_[x] = -1;
        }

        bool contains(int x) const {
            assert(0 <= x && x < n_);
            return positions_[x] != -1;
        }

        int choice(Xorshift& rng) const {
            assert(!data_.empty());
            return data_[rng.randrange(data_.size())];
        }

        const vector<int>& get_data() const {
            return data_;
        }

        size_t size() const {
            return data_.size();
        }

        void clear() {
            for (int x : data_) {
                positions_[x] = -1;
            }
            data_.clear();
        }

    private:
        int n_;
        vector<int> data_;
        vector<int> positions_;
};

class Timer {
    public:
        explicit Timer() {
            begin();
            elapsed_time_ = 0.0;
        }

        void begin() {
            start_time_ = chrono::system_clock::now();
        }

        double get_time() {
            chrono::system_clock::time_point end_time = chrono::system_clock::now();
            elapsed_time_ = chrono::duration_cast<chrono::nanoseconds>(end_time - start_time_).count();
            elapsed_time_ *= 1e-9; // from nanoseconds to seconds
            return elapsed_time_;
        }

        double get_last_time() const {
            return elapsed_time_;
        }

        bool yet(double time_limit) {
            return get_time() < time_limit;
        }

    private:
        chrono::system_clock::time_point start_time_;
        double elapsed_time_;
};

constexpr int sa_time_counts = 1 << 4;
constexpr size_t sa_random_steps = 1ul << 12;

class SimulatedAnnealing {
    public:
        explicit SimulatedAnnealing(double t_first, double t_last, bool exponential, double time_limit, uint_fast32_t seed)
            : t_first_(t_first), t_last_(t_last), exponential_(exponential), time_limit_(time_limit) {
            assert(0.0 <= t_last_ && t_last_ <= t_first_);

            time_counter_ = sa_time_counts;
            temperature_ = t_first_;
            log2_random_index_ = 0;

            for (size_t i = 0; i < sa_random_steps; ++i) {
                log2_random_[i] = log2(static_cast<double>(i + 1) / static_cast<double>(sa_random_steps));
            }
            mt19937 rng(seed);
            shuffle(log2_random_.begin(), log2_random_.end(), rng);
        }

        template<class T>
        bool accept(T profit, const Timer& timer) {
            if (profit >= static_cast<T>(0)) {
                return true;
            } else {
                return static_cast<double>(profit) > get_threshold(timer);
            }
        }

        double get_threshold(const Timer& timer) {
            update_temperature(timer);
            ++log2_random_index_;
            log2_random_index_ &= (sa_random_steps - 1ul);
            return temperature_ * log2_random_[log2_random_index_];
        }

    private:
        double t_first_, t_last_;
        bool exponential_;
        double time_limit_;
        int time_counter_;
        double temperature_;
        size_t log2_random_index_;
        array<double,sa_random_steps> log2_random_;

        void update_temperature(const Timer& timer) {
            if (time_counter_-- == 0) {
                time_counter_ = sa_time_counts;
                double progress = timer.get_last_time() / time_limit_;
                if (exponential_) {
                    temperature_ = pow(t_first_, 1.0 - progress) * pow(t_last_, progress);
                } else {
                    temperature_ = t_first_ * (1.0 - progress) + t_last_ * progress;
                }
            }
        }
};

constexpr double time_limit = 0.95;
constexpr int n = 45;
constexpr int max_turn = 50;
constexpr ll goal = 5e17;
constexpr ll sum_goal = 1e18;

struct Input {
    array<pair<ll,ll>,n> cards;

    void input() {
        int _n;
        cin >> _n;

        assert(_n == n);

        for (int i = 0; i < n; ++i) {
            cin >> cards[i].first >> cards[i].second;
        }
    }

    void input(const string& filename) {
        ifstream in(filename);
        assert(in);

        int _n;
        in >> _n;

        assert(_n == n);

        for (int i = 0; i < n; ++i) {
            in >> cards[i].first >> cards[i].second;
        }
    }
};

constexpr double t0 = 0.5;
constexpr double t1 = 0.1;

struct Solver {
    Timer timer;
    Xorshift rng;
    const Input input;
    vector<pair<int,int>> best_ans;
    ll min_cost;

    Solver(const Input& input): rng(1), input(input) {}

    vector<pair<int,int>> init_ans() {
        vector<pair<int,int>> ans(max_turn);
        array<pair<ll,ll>,n> cards = input.cards;

        for (int turn = 0; turn < max_turn; ++turn) {
            int best_u = -1;
            int best_v = -1;
            double max_profit = -numeric_limits<double>::infinity();
            for (int u = 0; u < n; ++u) {
                auto [ux, uy] = cards[u];
                for (int v = u + 1; v < n; ++v) {
                    auto [vx, vy] = cards[v];
                    double profit = log(abs(ux - goal) + abs(uy - goal) + 1) + log(abs(vx - goal) + abs(vy - goal) + 1);
                    profit -= 2 * log(abs((ux + vx) / 2 - goal) + abs((uy + vy) / 2 - goal) + 1);
                    if (chmax(max_profit, profit)) {
                        best_u = u;
                        best_v = v;
                    }
                }
                if (turn == 0) {
                    break;
                }
            }
            auto [ux, uy] = cards[best_u];
            auto [vx, vy] = cards[best_v];
            cards[best_u].first = cards[best_v].first = (ux + vx) / 2;
            cards[best_u].second = cards[best_v].second = (uy + vy) / 2;
            ans[turn] = {best_u, best_v};
        }
        return ans;
    }

    bool choose_first(int turn) {
        return true;//(int)rng.randrange(max_turn) < turn;
    }

    ll calc_cost(const vector<pair<int,int>>& ans) {
        array<pair<ll,ll>,n> cards = input.cards;
        for (auto [u, v] : ans) {
            ll a = (cards[u].first + cards[v].first) / 2;
            ll b = (cards[u].second + cards[v].second) / 2;
            cards[u] = {a, b};
            cards[v] = {a, b};
        }
        return max(abs(cards[0].first - goal), abs(cards[0].second - goal));
    }

    void solve() {
        SimulatedAnnealing sa(t0, t1, false, time_limit, 0);

        vector<pair<int,int>> ans = init_ans();
        ll cost = calc_cost(ans);
        best_ans = ans;
        min_cost = cost;
        while (timer.yet(time_limit)) {
            int turn = rng.randrange(20, ans.size());
            auto [a, b] = ans[turn];
            int u = choose_first(turn) ? 0 : rng.randrange(1, n);
            int v = rng.randrange(n - 1);
            if (v >= u) {
                ++v;
            }
            ans[turn] = {u, v};
            ll new_cost = calc_cost(ans);
            if (new_cost <= cost || sa.accept(log2(cost) - log2(new_cost), timer)) {
                cost = new_cost;
                if (chmin(min_cost, cost)) {
                    best_ans = ans;
                }
            } else {
                ans[turn] = {a, b};
            }
        }
    }

    void print() const {
        cout << best_ans.size() << "\n";
        for (auto [u, v] : best_ans) {
            cout << u + 1 << " " << v + 1 << "\n";
        }
    }

    void print(const string& filename) const {
        ofstream out(filename);
        assert(out);

        out << best_ans.size() << "\n";
        for (auto [u, v] : best_ans) {
            out << u + 1 << " " << v + 1 << "\n";
        }
    }

    ll score() const {
        return 2000000 - 100000 * log10(min_cost + 1);
    }
};

void multi_test(int cases, int num_threads) {
    if (cases <= 0) {
        return;
    }
    cerr << "cases: " << cases << endl;

    vector<ll> scores(cases);
    vector<double> times(cases);

#ifndef ONLINE_JUDGE
    omp_set_num_threads(num_threads);
    #pragma omp parallel for
#endif // ONLINE_JUDGE
    for (int seed = 0; seed < cases; ++seed) {
        string filename = to_string(seed + 1);
        filename = "in/in" + string(3 - filename.size(), '0') + filename + ".txt";
 
        Input input;
        input.input(filename);
 
        Solver solver(input);
        solver.solve();

        times[seed] = solver.timer.get_time();
        scores[seed] = solver.score();

        cerr << filename << " " << scores[seed] << " " << times[seed] << " sec" << endl;

        solver.print("out" + filename.substr(2));
    }
    cerr << "Average Score: " << accumulate(scores.begin(), scores.end(), 0ll) / cases << endl;
    cerr << "Max Time: " << *max_element(times.begin(), times.end()) << " sec" << endl;
    cerr << "Average Time: " << accumulate(times.begin(), times.end(), 0.0) / cases << " sec" << endl;
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    Input input;
    input.input();

    Solver solver(input);
    solver.solve();
    solver.print();

#ifndef ONLINE_JUDGE
    cerr << "Score = " << solver.score() << ", " << solver.timer.get_time() << " sec" << endl;

    int cases = 50;
    int num_threads = 10;
    multi_test(cases, num_threads);
#endif // ONLINE_JUDGE

    return 0;
}