結果

問題 No.5020 Averaging
ユーザー momoharamomohara
提出日時 2024-02-25 16:48:10
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 6,882 bytes
コンパイル時間 6,005 ms
コンパイル使用メモリ 318,608 KB
実行使用メモリ 6,548 KB
スコア 30,614,714
最終ジャッジ日時 2024-02-25 16:50:17
合計ジャッジ時間 53,259 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 903 ms
6,548 KB
testcase_01 AC 902 ms
6,548 KB
testcase_02 AC 901 ms
6,548 KB
testcase_03 AC 902 ms
6,548 KB
testcase_04 AC 902 ms
6,548 KB
testcase_05 AC 902 ms
6,548 KB
testcase_06 AC 901 ms
6,548 KB
testcase_07 AC 903 ms
6,548 KB
testcase_08 AC 903 ms
6,548 KB
testcase_09 AC 902 ms
6,548 KB
testcase_10 AC 903 ms
6,548 KB
testcase_11 AC 903 ms
6,548 KB
testcase_12 AC 903 ms
6,548 KB
testcase_13 AC 902 ms
6,548 KB
testcase_14 AC 902 ms
6,548 KB
testcase_15 AC 902 ms
6,548 KB
testcase_16 AC 903 ms
6,548 KB
testcase_17 AC 903 ms
6,548 KB
testcase_18 AC 902 ms
6,548 KB
testcase_19 AC 903 ms
6,548 KB
testcase_20 AC 902 ms
6,548 KB
testcase_21 AC 902 ms
6,548 KB
testcase_22 AC 902 ms
6,548 KB
testcase_23 AC 903 ms
6,548 KB
testcase_24 AC 903 ms
6,548 KB
testcase_25 AC 902 ms
6,548 KB
testcase_26 AC 902 ms
6,548 KB
testcase_27 AC 902 ms
6,548 KB
testcase_28 AC 903 ms
6,548 KB
testcase_29 AC 902 ms
6,548 KB
testcase_30 AC 903 ms
6,548 KB
testcase_31 AC 902 ms
6,548 KB
testcase_32 AC 903 ms
6,548 KB
testcase_33 AC 902 ms
6,548 KB
testcase_34 AC 902 ms
6,548 KB
testcase_35 AC 902 ms
6,548 KB
testcase_36 AC 902 ms
6,548 KB
testcase_37 AC 902 ms
6,548 KB
testcase_38 AC 903 ms
6,548 KB
testcase_39 AC 903 ms
6,548 KB
testcase_40 AC 903 ms
6,548 KB
testcase_41 AC 902 ms
6,548 KB
testcase_42 AC 902 ms
6,548 KB
testcase_43 AC 902 ms
6,548 KB
testcase_44 AC 903 ms
6,548 KB
testcase_45 AC 902 ms
6,548 KB
testcase_46 AC 902 ms
6,548 KB
testcase_47 AC 903 ms
6,548 KB
testcase_48 AC 902 ms
6,548 KB
testcase_49 AC 902 ms
6,548 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;
using namespace atcoder;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<ll, ll>;
using tp = tuple<ll, ll, ll>;

template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;

#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
#define rep(i, m, n) for(ll i = (ll)(m); i < (ll)(n); ++i)
#define rep2(i, m, n) for(ll i = (ll)(n)-1; i >= (ll)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)

constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
// constexpr long long MOD = (ll)1e9 + 7;
constexpr long long MOD = 998244353LL;
static const ld pi = 3.141592653589793L;

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

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

constexpr double TL = 0.9;

struct Timer {
    chrono::system_clock::time_point start, last_updated;

    Timer() {
        start = chrono::system_clock::now();
        last_updated = chrono::system_clock::now();
    }

    void reset() {
        start = chrono::system_clock::now();
    }

    void update() {
        last_updated = chrono::system_clock::now();
    }

    double getTime() {
        auto now = chrono::system_clock::now();
        return chrono::duration<double>(now - start).count();
    }
    double should_finish_search1() {
        return getTime() > TL;
    }
    bool should_reset() {
        auto now = chrono::system_clock::now();
        return chrono::duration<double>(now - last_updated).count() > 1.0 ||
               chrono::duration<double>(now - start).count() > TL;
    }
};
Timer timer;

struct Xor128 {
    unsigned x, y, z, w;

    Xor128() : x(123456789), y(362436069), z(521288629), w(88675123){};

    inline unsigned xor128() {
        unsigned t;
        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    int nextInt(int x, int y) {
        return xor128() % (y - x) + x;
    }

    double nextDouble(double a, double b) {
        return (double)(xor128() & 0xffff) / 0xffff * (b - a) + a;
    }
};
auto rnd = Xor128();

void solve() {
    timer = Timer();
    // input
    ll n;
    cin >> n;
    vec<ll> a(n), b(n);
    REP(i, n) {
        cin >> a[i] >> b[i];
    }

    // calc
    ll base = (ll)5e17;
    auto calc_score = [&](ll a0, ll b0, ll x) -> ll {
        ll v1 = abs(a0 - base);
        ll v2 = abs(b0 - base);
        ll v = max(v1, v2);
        ll score = 2000050 - x;
        if(v)
            score = 2000000 - 100000 * log10(v + 1);
        return score;
    };

    auto play_score = [&](vec<P> &op, ll x) -> P {
        auto aa = a;
        auto bb = b;
        ll max_score = calc_score(aa[0], bb[0], 0);
        ll max_x = 0;
        ll con = 0;
        REP2(i, op.size()) {
            con++;
            auto [u, v] = op[i];
            ll na = (aa[u] + aa[v]) / 2;
            ll nb = (bb[u] + bb[v]) / 2;
            aa[u] = aa[v] = na;
            bb[u] = bb[v] = nb;
            ll score = calc_score(aa[0], bb[0], con);
            if(chmax(max_score, score)) {
                max_x = con;
            }
        }
        return {max_score, max_x};
    };

    ll ma_score = calc_score(a[0], b[0], 0);
    vec<P> ma_op;
    ll ma_x = 0;
    ll th = 12;

    auto dfs = [&](auto &&self, vec<P> &op, vec<int> &updated, vec<int> &cand) -> void {
        if(op.size() >= th or timer.should_finish_search1())
            return;
        REP(ii, cand.size()) {
            REP(j, n) {
                int i = cand[ii];
                if(i == j or updated[i] == j and updated[j] == i)
                    continue;
                // oparation
                if(updated[j] == -1)
                    cand.push_back(j);
                int pi = updated[i];
                updated[i] = j;
                int pj = updated[j];
                updated[j] = i;
                op.push_back({i, j});
                // playout
                auto [score, x] = play_score(op, op.size());
                if(chmax(ma_score, score)) {
                    ma_op = op;
                    ma_x = x;
                }
                // dfs
                self(self, op, updated, cand);
                // rollback
                op.pop_back();
                updated[i] = pi;
                updated[j] = pj;
                if(updated[j] == -1)
                    cand.pop_back();
            }
        }
    };
    // 深さthまで全探索
    {
        vec<P> op;
        vector updated(n, -1);
        vector cand({0});
        dfs(dfs, op, updated, cand);
    }

    // // ランダムに操作を作成
    // do {
    //     vec<P> op(50);
    //     vector updated(n, -1);
    //     vector cand({0});
    //     REP(i, 50) {
    //         int r1 = cand[rnd.nextInt(0, cand.size())];
    //         int r2 = rnd.nextInt(0, n - 1);
    //         if(r2 >= r1)
    //             r2++;
    //         while(updated[r1] == r2 and updated[r2] == r1) {
    //             // 同じ操作を2回連続は避ける
    //             r2 = rnd.nextInt(0, n - 1);
    //             if(r2 >= r1)
    //                 r2++;
    //         }
    //         if(updated[r2] == -1)
    //             cand.push_back(r2);
    //         updated[r1] = r2;
    //         updated[r2] = r1;
    //         op[i] = {r1, r2};
    //     }

    //     // playout
    //     auto [score, x] = play_score(op, op.size());
    //     if(chmax(ma_score, score)) {
    //         ma_op = op;
    //         ma_x = x;
    //     }
    // } while(!timer.should_finish_search1());

    // output
    vec<P> ans;
    REP(i, ma_x) {
        ans.push_back(ma_op.back());
        ma_op.pop_back();
    }
    cout << ans.size() << en;
    for(auto [u, v] : ans)
        cout << u + 1 << " " << v + 1 << en;

#if !defined(ONLINE_JUDGE)
    // ローカル用出力
    // cerr << timer.getTime() << en;
    {
        auto aa = a;
        auto bb = b;
        ll max_x = 0;
        REP(i, ans.size()) {
            auto [u, v] = ans[i];
            ll na = (aa[u] + aa[v]) / 2;
            ll nb = (bb[u] + bb[v]) / 2;
            aa[u] = aa[v] = na;
            bb[u] = bb[v] = nb;
        }
        ll score = calc_score(aa[0], bb[0], ans.size());
        cerr << score << en;
    }
#endif
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // cout << fixed << setprecision(10);

    // ll t;
    // cin >> t;
    // REP(i, t - 1) {
    //     solve();
    // }

    solve();

    return 0;
}
0