#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 rand_generator { random_device seed_gen; mt19937 engine; rand_generator() : engine(seed_gen()) {} int rand(int mod) { return engine() % mod; } } 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; // 2べき判定 bool is_2beki(ll val) { ll cnt = 0; while(val) { cnt += val % 2; val /= 2; } return cnt == 1; } // 与えられた集合に対して、全パターンを試し、 // 最もTARGETに近くなるパターンと、その誤差を返す。 pair> search_lowest_diff_pattern(const vector& idx) { const ll size = idx.size(); ll best_diff = inf; ll best_mask = -1; rep(mask, 0, 1< res; rep(i, 0, size) if(best_mask & (1<& idx) { const ll size = idx.size(); ll sum_front = 0; ll sum_back = 0; 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}; } // ビット全探索ができるサイズ N=10くらいまで、ピックアップして、 // 平均値をなるべく5*10^17に近づけようとしてみる // N=10の場合、unsiged long longならばオーバーフローしない。 vector decide_indicies_to_use(const double time_limit = 0.6) { const double start_time = toki.gettime(); ll best_diff = inf; vector best_idx_to_use; vector idx(N); iota(all(idx), 0); ll counter = 0; while(toki.gettime() - start_time < time_limit) { counter++; shuffle(all(idx), ryuka.engine); rep(i, 0, idx.size()) { if(idx[i] == 0 && i != 0) { swap(idx[i], idx[0]); break; } } auto [diff, pos] = calc_max_diff(idx); if(diff < best_diff) { best_diff = diff; best_idx_to_use = vector(idx.begin(), idx.begin()+pos+1); } } dump(counter); dump(toki.gettime() - start_time); assert(!best_idx_to_use.empty()); assert(best_idx_to_use[0] == 0); return best_idx_to_use; } // 順々に足す vector add_ordinally(const vector& idx) { vector ans; rep(i, 1, idx.size()) ans.push_back({0, idx[i]}); return ans; } // トーナメント方式でたす vector add_uniformly(const vector& idx) { assert(idx[0] == 0); assert(is_2beki(idx.size())); vector debug_v = V; vector ans; for(ll b = 0; (1<& ans) { cout << ans.size() << endl; for(auto [u, v]: ans) { cout << u+1 << " " << v+1 << endl; } } void solve() { // 入力を受け取る。 cin >> N; V.resize(N); for(auto& [a, b]: V) cin >> a >> b; // 実際に使うインデックスを決定する。 vector idx_to_use = decide_indicies_to_use(); 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; }