結果

問題 No.5020 Averaging
ユーザー momoharamomohara
提出日時 2024-02-25 14:01:56
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 4,745 bytes
コンパイル時間 5,798 ms
コンパイル使用メモリ 317,132 KB
実行使用メモリ 6,676 KB
スコア 29,030,572
最終ジャッジ日時 2024-02-25 14:02:49
合計ジャッジ時間 53,727 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 902 ms
6,676 KB
testcase_01 AC 902 ms
6,676 KB
testcase_02 AC 902 ms
6,676 KB
testcase_03 AC 902 ms
6,676 KB
testcase_04 AC 902 ms
6,676 KB
testcase_05 AC 901 ms
6,676 KB
testcase_06 AC 902 ms
6,676 KB
testcase_07 AC 902 ms
6,676 KB
testcase_08 AC 902 ms
6,676 KB
testcase_09 AC 902 ms
6,676 KB
testcase_10 AC 901 ms
6,676 KB
testcase_11 AC 902 ms
6,676 KB
testcase_12 AC 902 ms
6,676 KB
testcase_13 AC 902 ms
6,676 KB
testcase_14 AC 902 ms
6,676 KB
testcase_15 AC 902 ms
6,676 KB
testcase_16 AC 902 ms
6,676 KB
testcase_17 AC 902 ms
6,676 KB
testcase_18 AC 902 ms
6,676 KB
testcase_19 AC 902 ms
6,676 KB
testcase_20 AC 902 ms
6,676 KB
testcase_21 AC 902 ms
6,676 KB
testcase_22 AC 902 ms
6,676 KB
testcase_23 AC 902 ms
6,676 KB
testcase_24 AC 902 ms
6,676 KB
testcase_25 AC 902 ms
6,676 KB
testcase_26 AC 901 ms
6,676 KB
testcase_27 AC 903 ms
6,676 KB
testcase_28 AC 902 ms
6,676 KB
testcase_29 AC 902 ms
6,676 KB
testcase_30 AC 902 ms
6,676 KB
testcase_31 AC 902 ms
6,676 KB
testcase_32 AC 902 ms
6,676 KB
testcase_33 AC 902 ms
6,676 KB
testcase_34 AC 902 ms
6,676 KB
testcase_35 AC 902 ms
6,676 KB
testcase_36 AC 902 ms
6,676 KB
testcase_37 AC 902 ms
6,676 KB
testcase_38 AC 902 ms
6,676 KB
testcase_39 AC 902 ms
6,676 KB
testcase_40 AC 901 ms
6,676 KB
testcase_41 AC 902 ms
6,676 KB
testcase_42 AC 902 ms
6,676 KB
testcase_43 AC 902 ms
6,676 KB
testcase_44 AC 902 ms
6,676 KB
testcase_45 AC 902 ms
6,676 KB
testcase_46 AC 902 ms
6,676 KB
testcase_47 AC 901 ms
6,676 KB
testcase_48 AC 902 ms
6,676 KB
testcase_49 AC 902 ms
6,676 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;
        REP(i, x) {
            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], i + 1);
            if(chmax(max_score, score)) {
                max_x = i + 1;
            }
        }
        return {max_score, max_x};
    };

    ll ma_score = calc_score(a[0], b[0], 0);
    vec<P> ma_op;
    ll ma_x = 0;
    do {
        // ランダムに操作を作成
        vec<P> op;
        REP(i, 49) {
            int r1 = rnd.nextInt(0, n);
            int r2 = rnd.nextInt(0, n - 1);
            if(r2 >= r1)
                r2++;
            if(r1 > r2)
                swap(r1, r2);
            op.push_back({r1, r2});
        }
        {
            // lastは1と何かをする
            int r1 = 0;
            int r2 = rnd.nextInt(1, n);
            op.push_back({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
    cout << ma_x << en;
    REP(i, ma_x) {
        auto [u, v] = ma_op[i];
        cout << u + 1 << " " << v + 1 << en;
    }

#if !defined(ONLINE_JUDGE)
    // ローカル用出力
    cerr << ma_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