#include #include #include using namespace std; using namespace atcoder; using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using tp = tuple; template using vec = vector; template using vvec = vector>; #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 inline bool chmin(T &a, T b) { if(a > b) { a = b; return true; } return false; } template 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(now - start).count(); } double should_finish_search1() { return getTime() > TL; } bool should_reset() { auto now = chrono::system_clock::now(); return chrono::duration(now - last_updated).count() > 1.0 || chrono::duration(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 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

&op, ll x) -> P { auto aa = a; auto bb = b; ll max_score = calc_score(aa[0], bb[0], 0); ll max_x = 0; REP2(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

ma_op; ll ma_x = 0; ll th = 12; auto dfs = [&](auto &&self, vec

&op, vec &updated, vec &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

op; vector updated(n, -1); vector cand({0}); dfs(dfs, op, updated, cand); } // // ランダムに操作を作成 // do { // vec

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 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 << timer.getTime() << en; 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; }