#include #include using namespace std; using namespace atcoder; using ll = long long; using pl = std::pair; //using mint = atcoder::modint1000000007; using mint = atcoder::modint998244353; #define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++) #define all(v) (v).begin(), (v).end() #define dump(var) do{ if(debug::enable) { std::cerr << #var << " : "; debug::print(var); } } while(0); constexpr int di[4] = {1, -1, 0, 0}; constexpr int dj[4] = {0, 0, 1, -1}; constexpr long long inf = 1LL<<60; template inline void chmax(T &a, T b) { a = std::max(a, b); }; template inline void chmin(T &a, T b) { a = std::min(a, b); }; template void vprint(const std::vector& v) { for(int i = 0; i < v.size(); i++) { std::cout << v[i] << (i == v.size()-1 ? "\n" : " "); } } template void vprintln(const std::vector& v) { for(int i = 0; i < v.size(); i++) { std::cout << v[i] << "\n"; } } template void vprint(const std::vector>& v) { for(int i = 0; i < v.size(); i++) { std::cout << v[i].val() << (i == v.size()-1 ? "\n" : " "); } } template void vprintln(const std::vector>& v) { for(int i = 0; i < v.size(); i++) { std::cout << v[i].val() << "\n"; } } namespace debug { #if defined(ONLINE_JUDGE) const bool enable = false; #else const bool enable = true; #endif template void push(const T& e) { std::cerr << e; } template void push(const atcoder::static_modint& e) { std::cerr << e.val(); } template void push(const std::pair& e) { std::cerr << "("; push(e.first); std::cerr << ","; push(e.second); std::cerr << ")"; } template void push(const std::tuple& e) { std::cerr << "("; push(get<0>(e)); std::cerr << ","; push(get<1>(e)); std::cerr << ","; push(get<2>(e)); std::cerr << ")"; } template void print(const T& e) { push(e); std::cerr << "\n"; } template void print(const std::vector& v) { for(int i = 0; i < v.size(); i++) { push(v[i]); std::cerr << " "; } std::cerr << "\n"; } template void print(const std::vector>& v) { std::cerr << "\n"; for(int i = 0; i < v.size(); i++) { std::cerr << i << ": "; print(v[i]); } } }; struct RandGenerator { random_device seed_gen; mt19937 engine; mt19937_64 engine64; static const int pshift = 1000000000; RandGenerator() : engine(seed_gen()), engine64(seed_gen()) {} /*mod以下の乱数を返す(32bit)*/ int rand(int mod) { return engine() % mod; } /*mod以下の乱数を返す(64bit)*/ long long randll(long long mod) { return engine64() % mod; } /*確率pでTrueを返す*/ bool pjudge(double p) { int p_int; if(p > 1) p_int = pshift; else p_int = p * pshift; return rand(pshift) < p_int; } } ryuka; #include struct timer { double global_start; double gettime() { struct timeval tv; gettimeofday(&tv, NULL); return tv.tv_sec + tv.tv_usec * 1e-6; } void init() { global_start = gettime(); } double elapsed() { return gettime() - global_start; } } toki; constexpr ll TARGET = 500000000000000000; ll N; vector V; struct State { vector idx; long long end_pos; long long score; State() : score(-inf) {}; long long calc_score(); long long calc_score(ll); static State initState(); static State generateState(const State& input_state); }; template struct IterationControl { int iteration_counter; int swap_counter; double average_time; double start_time; IterationControl() : iteration_counter(0), swap_counter(0) {} STATE climb(double time_limit, STATE initial_state); STATE anneal(double time_limit, double temp_start, double temp_end, STATE initial_state); }; // 前から順に足していって、もっとも誤差が小さくなるタイミングを返す pl calc_max_diff(const vector& idx) { const ll size = idx.size(); ll sum_front = V[idx[0]].first; ll sum_back = V[idx[0]].second; ll min_diff = inf, min_i = 0; rep(i, 1, size) { sum_front = (sum_front + V[idx[i]].first) / 2; sum_back = (sum_back + V[idx[i]].second) / 2; ll diff = max(abs(TARGET - sum_front), abs(TARGET - sum_back)); if(diff < min_diff) { min_diff = diff; min_i = i; } } return {min_diff, min_i}; } // 順々に足す vector add_ordinally(const vector& idx) { vector ans; rep(i, 1, idx.size()) ans.push_back({0, idx[i]}); return ans; } void print_ans(const vector& ans) { cout << ans.size() << endl; for(auto [u, v]: ans) { cout << u+1 << " " << v+1 << endl; } } long long State::calc_score() { ll a = V[idx[0]].first, b = V[idx[0]].second; rep(i, 1, end_pos) { a = (a + V[idx[i]].first) / 2; b = (b + V[idx[i]].second) / 2; } ll diff = max(abs(a - TARGET), abs(b - TARGET)); this->score = 2000000 - 100000 * log10(diff+1); return this->score; } long long State::calc_score(ll diff) { this->score = 2000000 - 100000 * log10(diff+1); return this->score; } State State::initState() { State res; res.idx.resize(N); iota(all(res.idx), 0); shuffle(res.idx.begin()+1, res.idx.end(), ryuka.engine); auto [_, pos] = calc_max_diff(res.idx); res.end_pos = pos + 1; res.calc_score(); return res; } State State::generateState(const State& input_state) { State res = input_state; { ll i = ryuka.rand(N-1) + 1; ll j = ryuka.rand(N) + 1; if(i > j) swap(i, j); if(i == j) j++; shuffle(res.idx.begin() + i, res.idx.begin() + j, ryuka.engine); } auto [diff, pos] = calc_max_diff(res.idx); res.end_pos = pos + 1; assert(res.idx[0] == 0); res.calc_score(diff); return res; } template STATE IterationControl::climb(double time_limit, STATE initial_state) { start_time = toki.gettime(); average_time = 0; STATE best_state = initial_state; double time_stamp = start_time; cerr << "[INFO] - IterationControl::climb - Starts climbing...\n"; while(time_stamp - start_time + average_time < time_limit) { STATE current_state = STATE::generateState(best_state); if(current_state.score > best_state.score) { swap(best_state, current_state); swap_counter++; } iteration_counter++; time_stamp = toki.gettime(); average_time = (time_stamp - start_time) / iteration_counter; } cerr << "[INFO] - IterationControl::climb - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n"; return best_state; } template STATE IterationControl::anneal(double time_limit, double temp_start, double temp_end, STATE initial_state) { start_time = toki.gettime(); average_time = 0; STATE best_state = initial_state; double elapsed_time = 0; cerr << "[INFO] - IterationControl::anneal - Starts annealing...\n"; while(elapsed_time + average_time < time_limit) { double normalized_time = elapsed_time / time_limit; double temp_current = pow(temp_start, 1.0 - normalized_time) * pow(temp_end, normalized_time); STATE current_state = STATE::generateState(best_state); long long delta = current_state.score - best_state.score; if(delta > 0 || ryuka.pjudge(exp(1.0 * delta / temp_current)) ) { swap(best_state, current_state); swap_counter++; } iteration_counter++; elapsed_time = toki.gettime() - start_time; average_time = elapsed_time / iteration_counter; } cerr << "[INFO] - IterationControl::anneal - Iterated " << iteration_counter << " times and swapped " << swap_counter << " times.\n"; return best_state; } void solve() { // 入力を受け取る。 cin >> N; V.resize(N); for(auto& [a, b]: V) cin >> a >> b; // 実際に使うインデックスを決定する。 IterationControl sera; State stat = sera.anneal(0.9, 100000, 100, State::initState()); dump(stat.score); vector idx_to_use = vector(stat.idx.begin(), stat.idx.begin()+stat.end_pos); dump(idx_to_use); // 出力 vector ans = add_ordinally(idx_to_use); print_ans(ans); } int main() { toki.init(); ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }