// (◕ᴗ◕✿) // #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #define rep(i, n) for (int i = 0; i < (n); ++i) #define srep(i, s, n) for (ll i = s; i < (n); ++i) #define len(x) ((int)(x).size()) #define all(x) (x).begin(), (x).end() using namespace std; template using vc = vector; template using vv = vc>; using vi = vc;using vvi = vv; using vvvi = vv; using ll = long long;using vl = vc;using vvl = vv; using vvvl = vv; using ld = long double; using vld = vc; using vvld = vc; using vvvld = vc; using uint = unsigned int; using ull = unsigned long long; const ld pi = 3.141592653589793; const int inf = 0x3f3f3f3f; const ll INF = 0x3f3f3f3f3f3f3f3f; // const ll mod = 1000000007; const ll mod = 998244353; #define debug(var) do{std::cout << #var << " : \n";view(var);}while(0) template void view(T e){cout << e << endl;} template void view(const vc& v){for(const auto& e : v){ cout << e << " "; } cout << endl;} template void view(const vv& vv){ for(const auto& v : vv){ view(v); } } // #define DEBUG #ifdef DEBUG constexpr bool DEBUGMODE = true; #else constexpr bool DEBUGMODE = false; #endif ifstream in; ofstream wrt; string outputfile = "output.txt", inputfile = "input.txt"; unsigned int randxor(){ static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123; unsigned int t; t = (x ^ (x << 11)); x = y; y = z; z = w; return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)); } int randint(int a, int b) {return(a + randxor() % (b - a));} struct Timer { public: Timer(int limit){ start = chrono::high_resolution_clock::now(); goal = start + chrono::milliseconds(limit); } inline double rate(){ return (chrono::high_resolution_clock::now() - start).count() / (double)(goal - start).count(); } inline int get_time(){return (chrono::high_resolution_clock::now() - start).count() / 1e6;} private: chrono::high_resolution_clock::time_point start; chrono::high_resolution_clock::time_point goal; }; double log_table[70000]; //variable constexpr int TIME_LIMIT = 990; constexpr int L = 4; constexpr int N = 45; constexpr ll base = 5e17; __int128_t A[N], B[N]; constexpr array, 23> perm = { array{0, 1, 3, 2}, {0, 2, 1, 3}, {0, 2, 3, 1}, {0, 3, 1, 2}, {0, 3, 2, 1}, {1, 0, 2, 3}, {1, 0, 3, 2}, {1, 2, 0, 3}, {1, 2, 3, 0}, {1, 3, 0, 2}, {1, 3, 2, 0}, {2, 0, 1, 3}, {2, 0, 3, 1}, {2, 1, 0, 3}, {2, 1, 3, 0}, {2, 3, 0, 1}, {2, 3, 1, 0}, {3, 0, 1, 2}, {3, 0, 2, 1}, {3, 1, 0, 2}, {3, 1, 2, 0}, {3, 2, 0, 1}, {3, 2, 1, 0} }; namespace simulated_annealing { constexpr int transition_num = 2; int transition_count[transition_num]; int success_count[transition_num]; using Cost = double; struct Config { int time_limit; int temperature_type; double start_temp, goal_temp; int probability[transition_num]; }; struct State { Cost score; array order; __int128_t sma, smb; State(){ score = INF; } // void operator=(const State &other) { // score = other.score; // } void init(){ iota(all(order), -1); sma = A[0]; smb = B[0]; srep(i, 1, N){ sma += A[i] << order[i]; smb += B[i] << order[i]; } ll a = abs((ll)(sma >> (N-1)) - base), b = abs((ll)(smb >> (N-1)) - base); if (a < b) swap(a, b); score = a + b / 1e3; } void transition01(Cost &threshold){ transition_count[0]++; int a = randint(1, N), b = randint(1, N); while (b == a) b = randint(1, N); int c = randint(1, N); while (c == a || c == b) c = randint(1, N); int d = randint(1, N); while (d == a || d == b || d == c) d = randint(1, N); array idx = {a, b, c, d}; array neword; int p = randint(0, 23); __int128_t mysma = sma, mysmb = smb; rep(i, 4){ mysma -= A[idx[i]] << order[idx[i]]; mysmb -= B[idx[i]] << order[idx[i]]; neword[i] = order[idx[perm[p][i]]]; mysma += A[idx[i]] << neword[i]; mysmb += B[idx[i]] << neword[i]; } ll ad = llabs((ll)(mysma >> (N-1)) - base), bd = llabs((ll)(mysmb >> (N-1)) - base); if (ad < bd) swap(ad, bd); Cost newscore = ad + bd / 1e3; if (newscore <= threshold){ success_count[0]++; score = newscore; sma = mysma; smb = mysmb; rep(i, 4) order[idx[i]] = neword[i]; } } }; State simulated_annealing(const Config& config) { State best; State state[L]; rep(i, L) state[i].init(); Timer timer(config.time_limit); int roop = 0; double tmp = config.start_temp; double rate = 0; while (true){ roop++; int randomint = randint(0, 100); rep(i, L){ Cost threshold = state[i].score - tmp * log_table[randint(0, 70000)]; // if (randomint < config.probability[0]){ // transition 01 // state[i].transition01(threshold); // }else{ // } state[i].transition01(threshold); if (best.score > state[i].score){ // update best best = state[i]; } } if (roop % 1000 == 0){ // if (roop % 10000 == 0) cerr << state.score << " " << best.score << endl; rate = timer.rate(); if (config.temperature_type == 0){ tmp = config.start_temp + rate * (config.goal_temp - config.start_temp); }else{ tmp = config.start_temp * pow(config.goal_temp / config.start_temp, rate); } if (rate > 1.0){ break; } } } cerr << "roop : " << roop << endl; cerr << "score : " << best.score << endl; rep(i, transition_num) cerr << "transition" << i << " conversion rate : " << fixed << setprecision(4) << success_count[i] / (double)transition_count[i] * 100 << " % " << success_count[i] << " / " << transition_count[i] << endl; return best; }; }// namespace simulated_annealing struct Solver{ simulated_annealing::State ans; void input(){ if (DEBUGMODE){ in.open(inputfile); cin.rdbuf(in.rdbuf()); } int n; cin >> n; rep(i, N){ ll a, b; cin >> a >> b; A[i] = a; B[i] = b; } } void init(){ double n = 1 / (double)(2 * 70000); for (int i = 0; i < 70000; i++) { log_table[i] = log(((double)i / 70000) + n); } } void output(){ array P; iota(all(P), 1); sort(all(P), [&](auto i, auto j){return ans.order[i] < ans.order[j];}); if (DEBUGMODE){ wrt << N - 1 << endl; for (auto id : P){ wrt << 1 << ' ' << id + 1 << endl; ll a = (A[0] + A[id]) / 2, b = (B[0] + B[id]) / 2; A[0] = a; B[0] = b; A[id] = a; B[id] = b; } rep(i, N) wrt << (ll)A[i] << ' ' << (ll)B[i] << endl; }else{ cout << N - 1 << endl; for (auto id : P){ cout << 1 << ' ' << id + 1 << endl; } } } void run(){ Timer timer(TIME_LIMIT); input(); init(); simulated_annealing::Config config = { TIME_LIMIT - timer.get_time(), 1, 1e19, 3, {70, 100} }; ans = simulated_annealing::simulated_annealing(config); output(); } }; int main(){ wrt.open(outputfile, ios::out); ios_base::sync_with_stdio(false); cin.tie(nullptr); Solver solver; solver.run(); wrt.close(); return 0; }