結果

問題 No.5020 Averaging
ユーザー eijirou
提出日時 2024-02-25 15:06:19
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 953 ms / 1,000 ms
コード長 10,400 bytes
コンパイル時間 8,259 ms
コンパイル使用メモリ 351,208 KB
実行使用メモリ 6,676 KB
スコア 50,388,579
最終ジャッジ日時 2024-02-25 15:07:18
合計ジャッジ時間 58,129 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge14
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
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);
        for (int turn = 0; turn < max_turn; ++turn) {
            do {
                ans[turn].first = choose_first(turn) ? 0 : rng.randrange(1, n);
                ans[turn].second = rng.randrange(1, n);
            } while (ans[turn].first == ans[turn].second);
        }
        return ans;
    }
    bool choose_first(int turn) {
        return (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(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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0