#include #include #include #include #include #include using namespace std; constexpr int N = 45; constexpr int op_max = 50; long long A[N], B[N]; constexpr int timelimit = 950; class Timer { chrono::system_clock::time_point start_time = chrono::system_clock::now(); public: Timer() {} long long get_elapsed_time() { auto diff = chrono::system_clock::now() - start_time; return chrono::duration_cast(diff).count(); } } timer; void write_ans(const vector> &ans) { cout << ans.size() << '\n'; for (const auto &[a, b] : ans) cout << a + 1 << ' ' << b + 1 << '\n'; } int calc_score(const vector> &ans, bool print_result = false) { long long a[N], b[N]; copy(begin(A), end(A), begin(a)); copy(begin(B), end(B), begin(b)); for (const auto &[i, j] : ans) { long long x = (a[i] + a[j]) / 2; long long y = (b[i] + b[j]) / 2; a[i] = a[j] = x; b[i] = b[j] = y; } if (print_result) for (int i = 0; i < N; ++i) cerr << a[i] << ' ' << b[i] << '\n'; constexpr long long target = (long long)5e17; const long long diff = max(abs(target - a[0]), abs(target - b[0])); return diff > 0 ? int(floor(2'000'000 - 100'000 * log10(diff + 1))) : 2'000'050 - int(ans.size()); } int main() { { int n; cin >> n; assert(n == N); } for (int i = 0; i < N; ++i) cin >> A[i] >> B[i]; vector> ans; int score = calc_score(ans); vector> best_ans = ans; int best_score = score; mt19937 mt; int iter = 0; const auto accept = [&](int diff) { if (diff >= 0) { return true; } else { const double start_temp = 10000; const double end_temp = 1000; const double progress = double(timer.get_elapsed_time()) / timelimit; const double temp = start_temp + progress * (end_temp - start_temp); const double prob = exp(diff / temp); return bernoulli_distribution(prob)(mt); } }; while (timer.get_elapsed_time() < timelimit) { if (ans.empty() || (ans.size() < op_max && mt() % 2 == 0)) { const int i = int(mt() % (1 + ans.size())); const int p = int(mt() % N); const int q = int(mt() % N); if (p >= q) continue; iter++; ans.insert(ans.begin() + i, {p, q}); const int tmp_score = calc_score(ans); if (accept(tmp_score - score)) { // if (tmp_score > score) // cerr << iter << " " << tmp_score << '\n'; score = tmp_score; } else { ans.erase(ans.begin() + i); } } else if (mt() % 2 == 0) { const size_t i = mt() % ans.size(); const auto old = ans[i]; const int p = int(mt() % N); const int q = int(mt() % N); if (p >= q || (old.first == p && old.second == q)) continue; iter++; ans[i] = {p, q}; const int tmp_score = calc_score(ans); if (accept(tmp_score - score)) { // if (tmp_score > score) // cerr << iter << " " << tmp_score << '\n'; score = tmp_score; } else { ans[i] = old; } } else { const int i = int(mt() % ans.size()); const auto old = ans[size_t(i)]; ans.erase(ans.begin() + i); iter++; const int tmp_score = calc_score(ans); if (tmp_score >= score) { // if (tmp_score > score) // cerr << iter << " " << tmp_score << '\n'; score = tmp_score; } else { ans.insert(ans.begin() + i, old); } } if (best_score < score) { cerr << iter << " " << score << '\n'; best_score = score; best_ans = ans; } if (iter % 100000 == 0) cerr << ' ' << iter << ' ' << score << endl; } cerr << "score = " << best_score << endl; calc_score(ans, true); write_ans(best_ans); }