#if __INCLUDE_LEVEL__ == 0 #include __BASE_FILE__ namespace { constexpr int K = 16; constexpr int S = 1; void solve() { int n; scan(n); std::vector a(n), b(n); for (const int i : rep(n)) { scan(a[i], b[i]); a[i] >>= S; b[i] >>= S; } std::vector p(n); std::iota(p.begin(), p.end(), 0); i64 s = 0; i64 t = 0; for (const int i : rep(K)) { s += a[i]; t += b[i]; } const auto evaluate = [&] { constexpr i64 H = (500'000'000'000'000'000 >> S) * K; return std::max(std::abs(s - H), std::abs(t - H)); }; i64 cur = evaluate(); i64 best = cur; auto ans = p; for (const auto& sa : Sa<256>(1 << 25, 1e20, 1e15)) { const int i = randint(1, K - 1); const int j = randint(K, n - 1); s += a[p[j]] - a[p[i]]; t += b[p[j]] - b[p[i]]; std::swap(p[i], p[j]); const i64 nxt = evaluate(); if (cur + sa.tol < nxt) { std::swap(p[i], p[j]); s -= a[p[j]] - a[p[i]]; t -= b[p[j]] - b[p[i]]; } else { cur = nxt; } if (chmin(best, cur)) { ans = p; } } print(K - 1); for (int k = 1; k < K; k *= 2) { for (int i = 0; i < K; i += k * 2) { print(ans[i] + 1, ans[i + k] + 1); } } } } // namespace int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout << std::setprecision(DBL_DECIMAL_DIG); solve(); } #else // __INCLUDE_LEVEL__ #include namespace xorshift { using u64 = std::uint64_t; using u128 = ::__uint128_t; inline u64 x = std::chrono::steady_clock::now().time_since_epoch().count(); inline u64 next() { x ^= x << 7; x ^= x >> 9; return x; } int randint(int a, int b) { const u64 m = static_cast(b) - static_cast(a) + 1; return a + static_cast(u128{next()} * m >> 64); } template void shuffle(R&& r) { const int n = static_cast(std::ranges::size(r)); if (n < 2) { return; } for (const int i : std::views::iota(1, n)) { if (const int j = randint(0, i); j < i) { std::ranges::swap(r[i], r[j]); } } } double uniform() { return static_cast(next()) / static_cast(UINT64_MAX); } double uniform(double a, double b) { return a + (b - a) * uniform(); } } // namespace xorshift using xorshift::randint; using xorshift::shuffle; using xorshift::uniform; template class Sa { public: explicit Sa(std::int64_t n_iters, double start_temp = 0, double end_temp = 0) : n_iters_(n_iters), start_temp_(start_temp), cooling_rate_(start_temp ? end_temp / start_temp : 1), iter_(0), elapsed_(0), temp_(start_temp) { assert(0 <= end_temp && end_temp <= start_temp); } Sa begin() const { return *this; } int end() const { return 0; } bool operator!=(int) const { return iter_ < n_iters_; } void operator++() { if (++iter_ % UpdateInterval == 0) { elapsed_ = static_cast(iter_) / static_cast(n_iters_); temp_ = start_temp_ * std::pow(cooling_rate_, elapsed_); } } auto operator*() const { struct { std::int64_t iter; double elapsed; double temp; double tol; } sa{iter_, elapsed_, temp_, temp_ * -std::log(uniform())}; return sa; } private: std::int64_t n_iters_; double start_temp_; double cooling_rate_; std::int64_t iter_; double elapsed_; double temp_; }; template bool chmin(T& x, U&& y) { return y < x && (x = std::forward(y), true); } template bool chmax(T& x, U&& y) { return x < y && (x = std::forward(y), true); } template T inf() { T ret; std::memset(&ret, 0x3f, sizeof(ret)); return ret; } template T inf() { return std::numeric_limits::infinity(); } template concept Range = std::ranges::range && !std::convertible_to; template concept Tuple = std::__is_tuple_like::value && !Range; namespace std { istream& operator>>(istream& is, Range auto&& r) { for (auto&& e : r) { is >> e; } return is; } istream& operator>>(istream& is, Tuple auto&& t) { return apply([&](auto&... xs) -> istream& { return (is >> ... >> xs); }, t); } ostream& operator<<(ostream& os, Range auto&& r) { for (string_view sep = ""; auto&& e : r) { os << exchange(sep, " ") << e; } return os; } ostream& operator<<(ostream& os, Tuple auto&& t) { const auto f = [&](auto&... xs) -> ostream& { [[maybe_unused]] string_view sep = ""; ((os << exchange(sep, " ") << xs), ...); return os; }; return apply(f, t); } } // namespace std void scan(auto&&... xs) { std::cin >> std::tie(xs...); } void print(auto&&... xs) { std::cout << std::tie(xs...) << '\n'; } template class fix { public: explicit fix(F f) : f_(std::move(f)) {} decltype(auto) operator()(auto&&... xs) const { return f_(std::ref(*this), std::forward(xs)...); } private: F f_; }; inline auto rep(int l, int r) { return std::views::iota(std::min(l, r), r); } inline auto rep(int n) { return rep(0, n); } inline auto rep1(int l, int r) { return rep(l, r + 1); } inline auto rep1(int n) { return rep(1, n + 1); } namespace ranges = std::ranges; namespace views = std::views; using i64 = std::int64_t; #endif // __INCLUDE_LEVEL__