#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(); 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); }; // 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 = 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}; } // ビット全探索ができるサイズ 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; } } long long State::calc_score() { ll a = 0, b = 0; rep(i, 0, 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; } 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) j++; shuffle(res.idx.begin() + i, res.idx.begin() + j, ryuka.engine); assert(res.idx[0] == 0); res.calc_score(); 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; // 実際に使うインデックスを決定する。 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; }