結果

問題 No.5020 Averaging
コンテスト
ユーザー momohara
提出日時 2024-02-25 16:54:17
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 903 ms / 1,000 ms
コード長 4,783 bytes
コンパイル時間 5,584 ms
コンパイル使用メモリ 316,164 KB
実行使用メモリ 6,548 KB
スコア 32,552,853
最終ジャッジ日時 2024-02-25 16:56:28
合計ジャッジ時間 53,514 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge10
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 50
権限があれば一括ダウンロードができます

ソースコード

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(50);
        vector updated(n, -1);
        REP2(i, 50) {
            int r1 = 0;
            int r2 = rnd.nextInt(1, n);
            while(updated[r1] == r2 and updated[r2] == r1) {
                // 同じ操作を2回連続は避ける
                r2 = rnd.nextInt(0, n - 1);
                if(r2 >= r1)
                    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
    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