//* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //*/ #include // #include // #include using namespace std; // using namespace atcoder; // #define _GLIBCXX_DEBUG #define DEBUG(x) cerr << #x << ": " << x << endl; #define DEBUG_VEC(v) \ cerr << #v << ":"; \ for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \ cerr << " " << v[iiiiiiii]; \ cerr << endl; #define DEBUG_MAT(v) \ cerr << #v << endl; \ for (int iv = 0; iv < v.size(); iv++) { \ for (int jv = 0; jv < v[iv].size(); jv++) { \ cerr << v[iv][jv] << " "; \ } \ cerr << endl; \ } typedef long long ll; // #define int ll #define vi vector #define vl vector #define vii vector> #define vll vector> #define vs vector #define pii pair #define pis pair #define psi pair #define pll pair template pair operator+(const pair &s, const pair &t) { return pair(s.first + t.first, s.second + t.second); } template pair operator-(const pair &s, const pair &t) { return pair(s.first - t.first, s.second - t.second); } template ostream &operator<<(ostream &os, pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep1(i, n) for (int i = 1; i <= (int)(n); i++) #define rrep(i, n) for (int i = (int)(n)-1; i >= 0; i--) #define rrep1(i, n) for (int i = (int)(n); i > 0; i--) #define REP(i, a, b) for (int i = a; i < b; i++) #define in(x, a, b) (a <= x && x < b) #define all(c) c.begin(), c.end() void YES(bool t = true) { cout << (t ? "YES" : "NO") << endl; } void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; } void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; } void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; } void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; } void no(bool t = true) { cout << (t ? "no" : "yes") << endl; } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; } #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); const ll inf = 1000000001; const ll INF = (ll)1e18 + 1; const long double pi = 3.1415926535897932384626433832795028841971L; int popcount(ll t) { return __builtin_popcountll(t); } // int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; vi dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0}; vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1}; struct Setup_io { Setup_io() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(25); cerr << fixed << setprecision(25); } } setup_io; // const ll MOD = 1000000007; const ll MOD = 998244353; // #define mp make_pair // #define endl '\n' auto start = chrono::system_clock::now(); constexpr double TL = 0.98; double calc_seconds() { return static_cast(chrono::duration_cast(chrono::system_clock::now() - start).count() / 1000000.0); } class HRandom { public: HRandom() { random_mw = 1985; random_mz = 2012; } int intRandom() { random_mz = 36969 * (random_mz & 65535) + (random_mz >> 16); random_mw = 18000 * (random_mw & 65535) + (random_mw >> 16); unsigned result = (random_mz << 16) + random_mw; return result >> 1; } unsigned int uintRandom_65535() { // random_mz = 36969 * (random_mz & 65535) + (random_mz >> 16); // random_mw = 18000 * (random_mw & 65535) + (random_mw >> 16); // return random_mw & 65535; const unsigned tmp = random_mw & 65535; random_mw = 18000 * tmp + (random_mw >> 16); return tmp; } unsigned int uintRandom() { random_mz = 36969 * (random_mz & 65535) + (random_mz >> 16); random_mw = 18000 * (random_mw & 65535) + (random_mw >> 16); unsigned result = (random_mz << 16) + random_mw; return result; } double dblRandom() { random_mz = 36969 * (random_mz & 65535) + (random_mz >> 16); random_mw = 18000 * (random_mw & 65535) + (random_mw >> 16); unsigned result = (random_mz << 16) + random_mw; return (result + 1.0) * 2.328306435454494e-10; } private: unsigned random_mw; unsigned random_mz; }; HRandom hrandom; static uint32_t randxor() { static uint32_t x = 123456789; static uint32_t y = 362436069; static uint32_t z = 521288629; static uint32_t w = 88675123; uint32_t t; t = x ^ (x << 11); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } void randxor_init() {} double randdouble() { return hrandom.dblRandom(); } bool randbool(const float &p = 0.5) { return hrandom.uintRandom_65535() < (p * 65535); } inline int rnd(const int n) { assert(0 <= n); if (n == 1) { return 0; } return ((hrandom.uintRandom_65535()) * n) >> 16; } int rnd(const int &l, const int &r) { assert(l <= r); return rnd(r - l) + l; } class Parameter { public: double start_temp, end_temp; int hash_interval; int back_to_best_interval; int kick_interval; Parameter(double start_temp_ = 1.3042229737028601, double end_temp_ = 1e-06, int hash_interval_ = 82, int back_to_best_interval_ = 8335, int kick_interval_ = 2719266) { this->start_temp = start_temp; this->end_temp = end_temp; this->hash_interval = hash_interval; this->back_to_best_interval = back_to_best_interval; this->kick_interval = kick_interval; } static Parameter from_args(int argc, char **argv) { return Parameter( stof(argv[1]), stof(argv[2]), stoi(argv[3]), stoi(argv[4]), stoi(argv[5])); } }; Parameter param; std::default_random_engine engine(42); constexpr int N = 45; vector ab(N); void input() { int x; cin >> x; rep(i, N) { cin >> ab[i].first >> ab[i].second; } } double calc_score(const vector &x) { auto now = ab; for (auto [u, v] : x) { pll s = now[u] + now[v]; s.first /= 2; s.second /= 2; now[u] = now[v] = s; } return log10(max(abs(now[0].first - 5e17), abs(now[0].second - 5e17)) + 1); } pll calc_last(const vector &x) { auto now = ab; for (auto [u, v] : x) { pll s = now[u] + now[v]; s.first /= 2; s.second /= 2; now[u] = now[v] = s; } return now[0]; } signed main(int argc, char **argv) { #ifdef LOCAL if (argc > 1) { param = Parameter::from_args(argc, argv); } #endif input(); constexpr int M = 50; vector x(M); int off = M - (N - 1); rep(i, off) { x[i] = {2 * i + 1, 2 * i + 2}; } rep(i, N - 1) { x[off + i] = {0, i + 1}; } double score = calc_score(x); constexpr int HASH_MAX = 65536; vector base_hash(M); vector value_hash(N); rep(i, M) { base_hash[i].first = hrandom.uintRandom_65535(); base_hash[i].second = hrandom.uintRandom_65535(); } rep(i, N) { value_hash[i] = hrandom.uintRandom_65535(); } auto calc_hash = [&](const int &i) { // 現状の x で i のハッシュ値を計算 ll ret = 0; ret ^= base_hash[i].first * value_hash[x[i].first]; ret ^= base_hash[i].second * value_hash[x[i].second]; return ret % HASH_MAX; }; int current_hash = 0; rep(i, M) { current_hash ^= calc_hash(i); } vector last_hash(HASH_MAX, -inf); double best_score = score; int best_hash = current_hash; vector best_x = x; double temperature = param.start_temp; int acc_rate1 = 0, acc_rate2 = 0; int last_best_update = 0, last_kick = 0; auto update_best = [&](int try_num, const double &new_score, const int &new_hash, const vector &new_x) { best_score = new_score; best_hash = new_hash; best_x = new_x; last_best_update = try_num; last_kick = try_num; }; rep(try_num, inf) { if (try_num % (1 << 15) == 0) { // DEBUG((double)acc_rate / (1 << 15)); // DEBUG(make_pair((double)acc_rate1 / (1 << 15), (double)acc_rate2 / (1 << 15))); acc_rate1 = acc_rate2 = 0; } if (try_num % 16 == 0) { double sec = calc_seconds(); double rate = sec / TL; if (rate > 1) { DEBUG(try_num); break; } temperature = param.start_temp * (1 - rate) + param.end_temp * rate; } if (try_num - last_best_update > param.back_to_best_interval) { DEBUG("update"); current_hash = best_hash; x = best_x; score = best_score; last_best_update = try_num; } if (try_num - last_kick > param.kick_interval) { DEBUG("kick"); while (true) { int b = rnd(5, 10); int i1 = rnd(M - b), i2 = rnd(M - b); if (i1 > i2) { swap(i1, i2); } if (i1 + b > i2) { continue; } rep(i, b) { current_hash ^= calc_hash(i1 + i) ^ calc_hash(i2 + i); swap(x[i1 + i], x[i2 + i]); current_hash ^= calc_hash(i1 + i) ^ calc_hash(i2 + i); } score = calc_score(x); break; } last_kick = try_num; } int op_type = rnd(11); int new_hash = current_hash; if (op_type < 9) { int idx1 = rnd(off, M - 1); int idx2 = rnd(off, min(idx1 + 5, M)); new_hash ^= calc_hash(idx1) ^ calc_hash(idx2); swap(x[idx1], x[idx2]); new_hash ^= calc_hash(idx1) ^ calc_hash(idx2); if (last_hash[new_hash] > try_num - param.hash_interval) { swap(x[idx1], x[idx2]); continue; } double new_score = calc_score(x); double diff = score - new_score; double prob = exp(diff / temperature); if (randdouble() < prob) { acc_rate1++; score = new_score; current_hash = new_hash; last_hash[current_hash] = try_num; if (chmin(best_score, score)) { update_best(try_num, score, current_hash, x); } } else { swap(x[idx1], x[idx2]); } } else if (op_type < 10) { int idx = rnd(off, M - 3); rep(i, 6) { if (i % 2 == 0) { current_hash ^= calc_hash(idx) ^ calc_hash(idx + 1); swap(x[idx], x[idx + 1]); current_hash ^= calc_hash(idx) ^ calc_hash(idx + 1); } else { current_hash ^= calc_hash(idx + 1) ^ calc_hash(idx + 2); swap(x[idx + 1], x[idx + 2]); current_hash ^= calc_hash(idx + 1) ^ calc_hash(idx + 2); } if (i == 5) { break; } if (last_hash[current_hash] > try_num - param.hash_interval) { continue; } double new_score = calc_score(x); double diff = score - new_score; double prob = exp(diff / temperature); if (randdouble() < prob) { acc_rate1++; score = new_score; last_hash[current_hash] = try_num; if (chmin(best_score, score)) { update_best(try_num, score, current_hash, x); } break; } } } else { int idx = rnd(off); int b = rnd(2); int to = rnd(N); int ori; new_hash ^= calc_hash(idx); if (b) { if (x[idx].second == to) { continue; } ori = x[idx].first; x[idx].first = to; } else { if (x[idx].first == to) { continue; } ori = x[idx].second; x[idx].second = to; } new_hash ^= calc_hash(idx); if (last_hash[new_hash] > try_num - param.hash_interval) { if (b) { x[idx].first = ori; } else { x[idx].second = ori; } continue; } double new_score = calc_score(x); double diff = score - new_score; double prob = exp(diff / temperature); if (randdouble() < prob) { acc_rate2++; score = new_score; current_hash = new_hash; last_hash[current_hash] = try_num; if (chmin(best_score, score)) { update_best(try_num, score, current_hash, x); } } else { if (b) { x[idx].first = ori; } else { x[idx].second = ori; } } } } ll val_hash = 0; rep(i, M) { val_hash ^= calc_hash(i); } assert(val_hash == current_hash); DEBUG(calc_last(best_x)); DEBUG(best_score); int last_score = 2000000 - 100000 * best_score; DEBUG(last_score); cout << M << endl; for (auto [u, v] : best_x) { cout << u + 1 << " " << v + 1 << endl; } }