#ifdef __GNUC__ #pragma GCC optimize ("O3") #pragma GCC optimize ("unroll-loops") #pragma GCC target ("avx2") #endif #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef _MSC_VER #include #else #include #endif struct xorshift64 { unsigned long long int x = 88172645463325252ULL; inline unsigned short nextUShort() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUShortMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x0000ffffffffffff) * mod) >> 48; } inline unsigned int nextUInt() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline unsigned int nextUIntMod(unsigned long long int mod) { x = x ^ (x << 7); x = x ^ (x >> 9); return ((x & 0x00000000ffffffff) * mod) >> 32; } inline unsigned long long int nextULL() { x = x ^ (x << 7); return x = x ^ (x >> 9); } inline double nextDouble() { x = x ^ (x << 7); x = x ^ (x >> 9); return (double)x * 5.42101086242752217e-20; } }; struct timer { double t = 0.0; double lastStop = 0.0; bool stopped = false; timer() { restart(); } inline void restart() { t = now(); stopped = false; } inline void start() { if (stopped) { t += now() - lastStop; stopped = false; } } inline void stop() { if (!stopped) { lastStop = now(); stopped = true; } } inline double time() { if (stopped) return lastStop - t; else return now() - t; } inline double now() { #ifdef _MSC_VER #ifdef LOCAL return __rdtsc() * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return __rdtsc() * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) //return __rdtsc() * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) // return __rdtsc() * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C6i (Xeon Platinum 8375C) return __rdtsc() * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif #else unsigned long long l, h; __asm__ ("rdtsc" : "=a"(l), "=d"(h)); #ifdef LOCAL return (double)(l | h << 32) * 2.857142857142857e-10; // 1 / 3.5e9, for local (Ryzen 9 3950X) #else //return (double)(l | h << 32) * 3.5714285714285715e-10; // 1 / 2.8e9, for AWS EC2 C3 (Xeon E5-2680 v2) //return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C4 (Xeon E5-2666 v3) //return (double)(l | h << 32) * 3.333333333333333e-10; // 1 / 3.0e9, for AWS EC2 C5 (Xeon Platinum 8124M / Xeon Platinum 8275CL) // return (double)(l | h << 32) * 3.4482758620689656e-10; // 1 / 2.9e9, for AWS EC2 C6i (Xeon Platinum 8375C) return (double)(l | h << 32) * 4.3478260869565215e-10; // 1 / 2.3e9, for yukicoder judge #endif #endif } }; using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef pair Pii; typedef unsigned char uchar; const ll mod = 1000000007; timer theTimer; xorshift64 theRandom; mt19937_64 theMersenne(1); // libraries namespace Lib { } // hyper parameters namespace HyperParameter { void load_hyper_parameter(int argc, char *argv[]) { // do nothing } } // enums // structs struct Card { ll front, back; Card(): front(0), back(0) {} Card(ll front, ll back): front(front), back(back) {} }; // constants struct Const { static constexpr ll target_value = (ll) 5e17; static constexpr int turn_max = 50; }; // inputs struct Input { int card_num; vector cards; }; // outputs struct Output { vector> merge_order; }; // internals Input get_input() { Input input; cin >> input.card_num; input.cards.resize(input.card_num); for (int i = 0; i < input.card_num; i++) { cin >> input.cards[i].front >> input.cards[i].back; } return input; } void init(Input& input) { // do nothing } Output solve(const Input& input) { struct SAState { const Input& input; vector pre_merge_order; vector merge_order; ll score; SAState(const Input& input): input(input) { pre_merge_order = vector(Const::turn_max - input.card_num + 1); merge_order = vector(input.card_num); iota(merge_order.begin(), merge_order.end(), 0); shuffle(merge_order.begin(), merge_order.end(), theMersenne); update_score_full(); } void update_score_full() { static vector cards(input.card_num); for (int i = 0; i < input.card_num; i++) cards[i] = input.cards[i]; for (int i = 0; i < Const::turn_max - input.card_num; i++) { const int idx1 = merge_order[pre_merge_order[i]]; const int idx2 = merge_order[pre_merge_order[i + 1]]; const ll front = (cards[idx1].front + cards[idx2].front) / 2; const ll back = (cards[idx1].back + cards[idx2].back) / 2; cards[idx1].front = front; cards[idx1].back = back; cards[idx2].front = front; cards[idx2].back = back; } Card result_card = cards[merge_order[0]]; for (int i = 1; i < input.card_num; i++) { const int idx = merge_order[i]; result_card.front = (result_card.front + cards[idx].front) / 2; result_card.back = (result_card.back + cards[idx].back) / 2; } score = max(abs(result_card.front - Const::target_value), abs(result_card.back - Const::target_value)); } ll get_score() { return score; } Output get_output() { Output output; for (int i = 0; i < Const::turn_max - input.card_num; i++) { if (pre_merge_order[i] != pre_merge_order[i + 1]) { output.merge_order.emplace_back(merge_order[pre_merge_order[i]], merge_order[pre_merge_order[i + 1]]); } } int smallest_idx = merge_order[0]; for (int i = 1; i < input.card_num; i++) { int next_idx = merge_order[i]; output.merge_order.emplace_back(smallest_idx, next_idx); if (next_idx < smallest_idx) { smallest_idx = next_idx; } } return output; } }; ll global_best_score = (ll) 9e18; Output global_best_output; for (int t = 0; t < 10; t++) { SAState state(input); { ll score = state.get_score(); ll last_score = score; ll best_score = score; vector best_pre_merge_order = state.pre_merge_order; vector best_merge_order = state.merge_order; const double base_temperature = 2e1; const double target_temperature = 5e0; // const double decay_rate = 4e-5; double temperature = base_temperature; int iter_count = 0; double time_start = theTimer.time(); const double time_limit = (double) (t + 1) * 0.099; while (true) { if (iter_count % 1024 == 0 && theTimer.time() > time_limit) break; const double roll = theRandom.nextDouble(); if (roll < 0.4) { const int i1 = theRandom.nextUIntMod(input.card_num); const int i2 = theRandom.nextUIntMod(input.card_num); if (i1 == i2) continue; swap(state.merge_order[i1], state.merge_order[i2]); state.update_score_full(); score = state.get_score(); #ifdef DEBUG if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score <= last_score) { last_score = score; if (score < best_score) { best_score = score; best_pre_merge_order = state.pre_merge_order; best_merge_order = state.merge_order; } } else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept last_score = score; } else { // rollback swap(state.merge_order[i1], state.merge_order[i2]); score = last_score; } } else if (roll < 0.8) { const int i1 = theRandom.nextUIntMod(input.card_num); const int i2 = theRandom.nextUIntMod(input.card_num); if (i1 == i2) continue; const int orig_c = state.merge_order[i1]; state.merge_order.erase(state.merge_order.begin() + i1); state.merge_order.insert(state.merge_order.begin() + i2, orig_c); state.update_score_full(); score = state.get_score(); #ifdef DEBUG if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score <= last_score) { last_score = score; if (score < best_score) { best_score = score; best_pre_merge_order = state.pre_merge_order; best_merge_order = state.merge_order; } } else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept last_score = score; } else { // rollback state.merge_order.erase(state.merge_order.begin() + i2); state.merge_order.insert(state.merge_order.begin() + i1, orig_c); score = last_score; } } else if (roll < 0.9) { const int i = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1); const int c = theRandom.nextUIntMod(6); const int orig_c = state.pre_merge_order[i]; state.pre_merge_order[i] = c; state.update_score_full(); score = state.get_score(); #ifdef DEBUG if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score <= last_score) { last_score = score; if (score < best_score) { best_score = score; best_pre_merge_order = state.pre_merge_order; best_merge_order = state.merge_order; } } else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept last_score = score; } else { // rollback state.pre_merge_order[i] = orig_c; score = last_score; } } else if (roll < 0.95) { const int i1 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1); const int i2 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1); if (i1 == i2) continue; swap(state.pre_merge_order[i1], state.pre_merge_order[i2]); state.update_score_full(); score = state.get_score(); #ifdef DEBUG if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score <= last_score) { last_score = score; if (score < best_score) { best_score = score; best_pre_merge_order = state.pre_merge_order; best_merge_order = state.merge_order; } } else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept last_score = score; } else { // rollback swap(state.pre_merge_order[i1], state.pre_merge_order[i2]); score = last_score; } } else if (roll < 1.0) { const int i1 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1); const int i2 = theRandom.nextUIntMod(Const::turn_max - input.card_num + 1); if (i1 == i2) continue; const int orig_c = state.pre_merge_order[i1]; state.pre_merge_order.erase(state.pre_merge_order.begin() + i1); state.pre_merge_order.insert(state.pre_merge_order.begin() + i2, orig_c); state.update_score_full(); score = state.get_score(); #ifdef DEBUG if (iter_count % 10000 == 0) cerr << iter_count << " " << score << " " << last_score << " " << best_score << " " << temperature << " " << theTimer.time() << endl; #endif if (score <= last_score) { last_score = score; if (score < best_score) { best_score = score; best_pre_merge_order = state.pre_merge_order; best_merge_order = state.merge_order; } } else if (theRandom.nextDouble() < exp(double(last_score - score) / temperature)) { // accept last_score = score; } else { // rollback state.pre_merge_order.erase(state.pre_merge_order.begin() + i2); state.pre_merge_order.insert(state.pre_merge_order.begin() + i1, orig_c); score = last_score; } } // temperature *= 1.0 - decay_rate; temperature = (double) best_score * exp(log(base_temperature) - ((log(base_temperature) - log(target_temperature)) * ((theTimer.time() - time_start) * (1.0 / (time_limit - time_start))))); iter_count++; } cerr << "iter_count = " << iter_count << endl; cerr << "last_score = " << last_score << endl; cerr << "best_score = " << best_score << endl; cerr << "temperature = " << temperature << endl; state.pre_merge_order = best_pre_merge_order; state.merge_order = best_merge_order; state.update_score_full(); if (score < global_best_score) { global_best_score = score; global_best_output = state.get_output(); } } } cerr << "global_best_score = " << global_best_score << endl; cerr << "raw_score = " << (int) (2e6 - 1e5 * log10(global_best_score + 1)) << endl; return global_best_output; } void print_output(const Output& output) { cout << output.merge_order.size() << endl; for (auto p: output.merge_order) { cout << p.first + 1 << " " << p.second + 1 << endl; } } int main(int argc, char *argv[]) { cin.tie(0); ios::sync_with_stdio(false); HyperParameter::load_hyper_parameter(argc, argv); auto input = get_input(); init(input); auto output = solve(input); print_output(output); return 0; }