#include #include using namespace std; using ll = long long; #define TARGET (500000000000000000) random_device seed_gen; mt19937 engine(seed_gen()); uniform_real_distribution<> uniform_distribution(0.0, 1.0); double getRandomValue() { return uniform_distribution(engine); } int main() { int N; cin >> N; vector A(N), B(N); for (int i = 0; i < N; i++) { cin >> A[i] >> B[i]; } vector contribution(N, -1); contribution[0] = 0; for (int i = 1; i < N; i++) { int j = getRandomValue() * i; contribution[j]++; contribution[i] = contribution[j]; } ll sumA = 0; ll sumB = 0; for (int i = 0; i < N; i++) { sumA += A[i] / (1LL << (contribution[i])); sumB += B[i] / (1LL << (contribution[i])); } clock_t start = clock(); while (true) { clock_t end = clock(); double elapsed = (double)(end - start) / CLOCKS_PER_SEC; if (elapsed > 0.90) { break; } ll score = max(abs(sumA - TARGET), abs(sumB - TARGET)); if (false && getRandomValue() < 0.3) { // add vector in, out; for (int i = 0; i < N; i++) { if (contribution[i] == -1) { out.push_back(i); } else { in.push_back(i); } } int i = getRandomValue() * out.size(); i = out[i]; int j = getRandomValue() * in.size(); j = in[j]; sumA -= A[j] / (1LL << contribution[j]); sumB -= B[j] / (1LL << contribution[j]); contribution[j]++; contribution[i] = contribution[j]; sumA += A[j] / (1LL << contribution[j]); sumB += B[j] / (1LL << contribution[j]); sumA += A[i] / (1LL << contribution[i]); sumB += B[i] / (1LL << contribution[i]); ll score_tmp = max(abs(sumA - TARGET), abs(sumB - TARGET)); if (score_tmp > score) { sumA -= A[j] / (1LL << contribution[j]); sumB -= B[j] / (1LL << contribution[j]); sumA -= A[i] / (1LL << contribution[i]); sumB -= B[i] / (1LL << contribution[i]); contribution[j]--; contribution[i] = 0; sumA += A[j] / (1LL << contribution[j]); sumB += B[j] / (1LL << contribution[j]); } } else if (false && getRandomValue() < 0.5) { // delete vector in; for (int i = 1; i < N; i++) { if (contribution[i] != -1) { in.push_back(i); } } if (in.size() == 0) { continue; } int i = getRandomValue() * in.size(); i = in[i]; vector same; for (int j = 0; j < N; j++) { if (i == j) { continue; } if (contribution[i] == contribution[j]) { same.push_back(j); } } if (same.size() == 0) { continue; } } else { int i = getRandomValue() * N; int j = getRandomValue() * N; if (contribution[i] == contribution[j]) { continue; } sumA -= A[i] / (1LL << contribution[i]); sumB -= B[i] / (1LL << contribution[i]); sumA -= A[j] / (1LL << contribution[j]); sumB -= B[j] / (1LL << contribution[j]); swap(contribution[i], contribution[j]); sumA += A[i] / (1LL << contribution[i]); sumB += B[i] / (1LL << contribution[i]); sumA += A[j] / (1LL << contribution[j]); sumB += B[j] / (1LL << contribution[j]); ll score_tmp = max(abs(sumA - TARGET), abs(sumB - TARGET)); if (score_tmp > score) { sumA -= A[i] / (1LL << contribution[i]); sumB -= B[i] / (1LL << contribution[i]); sumA -= A[j] / (1LL << contribution[j]); sumB -= B[j] / (1LL << contribution[j]); swap(contribution[i], contribution[j]); sumA += A[i] / (1LL << contribution[i]); sumB += B[i] / (1LL << contribution[i]); sumA += A[j] / (1LL << contribution[j]); sumB += B[j] / (1LL << contribution[j]); } } } vector> ans; priority_queue> pq; for (int i = 0; i < N; i++) { pq.push({contribution[i], i}); } while (pq.size() > 1) { int u = pq.top().second; pq.pop(); int v = pq.top().second; int d = pq.top().first; pq.pop(); if (u > v) { swap(u, v); } ans.push_back({u, v}); pq.push({d, u}); } cout << ans.size() << '\n'; for (auto [u, v] : ans) { cout << u + 1 << ' ' << v + 1 << '\n'; } }