#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; void Main() { int start_time = clock(); //input int N; cin >> N; vector A(N),B(N); for(int i = 0;i < N;i++) { cin >> A[i] >> B[i]; } const long long M = (long long)5e17; const int TIME_LIMIT = 0.9 * CLOCKS_PER_SEC; mt19937_64 rng{(unsigned)time(nullptr)}; vector> ans; long double score = 0; const int sz = 50; const int half = 25; int loop = 0; const long double start_temp = 1000,end_temp = 10000; auto diff = [&M](long long a,long long b) -> long long { return max(abs(a - M),abs(b - M)); }; auto averaging = [&](long long &a,long long &b) -> void { long long x = (a + b) / 2; a = b = x; return; }; auto calc_score = [&](long long a,long long b) -> long double { return 2e6 - 1e5 * log10(diff(a,b) + 1); }; { vector C = A,D = B; vector ord(N); iota(ord.begin(),ord.end(),0); sort(ord.begin() + 1,ord.end(),[&](int i,int j) { return diff(C[i],D[i]) > diff(C[j],D[j]); }); for(int i = 2;i <= N;i++) { int id = ord[i - 1] + 1; ans.push_back(make_pair(1,id)); averaging(C[0],C[id - 1]); averaging(D[0],D[id - 1]); } score = calc_score(C[0],D[0]); } while(clock() - start_time < TIME_LIMIT) { loop++; vector> n_ans = ans; { while(true) { int i = rng() % n_ans.size(); int j = rng() % n_ans.size(); if(i == j) { continue; } swap(n_ans[i],n_ans[j]); break; } } vector C = A,D = B; for(const auto &[u,v] : n_ans) { averaging(C[u - 1],C[v - 1]); averaging(D[u - 1],D[v - 1]); } long double n_score = calc_score(C[0],D[0]); long double temp = start_temp + (end_temp - start_temp) * (clock() - start_time) / TIME_LIMIT; long double prob = exp((n_score - score) / temp); if(prob > (long double)(rng() % M) / M) { swap(ans,n_ans); score = n_score; } } /* vector> G(1 << 2); */ /* vector T(N); */ /* for(int i = 0;i < N;i++) */ /* { */ /* int S = 0; */ /* if(A[i] > M) */ /* { */ /* S |= 1; */ /* } */ /* if(B[i] > M) */ /* { */ /* S |= 2; */ /* } */ /* if(i > 0) */ /* { */ /* G[S].push_back(i); */ /* } */ /* T[i] = S; */ /* } */ /* { */ /* vector C = A,D = B; */ /* vector ord(N); */ /* iota(ord.begin(),ord.end(),0); */ /* sort(ord.begin() + 1,ord.end(),[&](int i,int j) */ /* { */ /* return diff(C[i],D[i]) > diff(C[j],D[j]); */ /* }); */ /* for(int i = 0;i < half;i++) */ /* { */ /* while(true) */ /* { */ /* /1* int u = rng() % (N - 1) + 2; *1/ */ /* /1* int v = rng() % (N - 1) + 2; *1/ */ /* int u = ord[N - i - 1] + 1; */ /* int U = T[u - 1] ^ 3; */ /* int v = G[U][rng() % G[U].size()] + 1; */ /* if(u == v) */ /* { */ /* continue; */ /* } */ /* { */ /* long long x = (C[u - 1] + C[v - 1]) / 2; */ /* C[u - 1] = C[v - 1] = x; */ /* } */ /* { */ /* long long x = (D[u - 1] + D[v - 1]) / 2; */ /* D[u - 1] = D[v - 1] = x; */ /* } */ /* ans.push_back(make_pair(u,v)); */ /* break; */ /* } */ /* } */ /* iota(ord.begin(),ord.end(),0); */ /* sort(ord.begin() + 1,ord.end(),[&](int i,int j) */ /* { */ /* return diff(C[i],D[i]) > diff(C[j],D[j]); */ /* }); */ /* for(int i = N - (sz - half);i < N;i++) */ /* { */ /* int id = ord[i]; */ /* { */ /* long long x = (C[0] + C[id]) / 2; */ /* C[0] = C[id] = x; */ /* } */ /* { */ /* long long x = (D[0] + D[id]) / 2; */ /* D[0] = D[id] = x; */ /* } */ /* ans.push_back(make_pair(1,id + 1)); */ /* } */ /* score = 2e6 - 1e5 * log10(diff(C[0],D[0]) + 1); */ /* } */ /* while(clock() - start_time < TIME_LIMIT) */ /* { */ /* loop++; */ /* vector> n_ans(ans.begin(),ans.begin() + half); */ /* { */ /* int id = rng() % half; */ /* while(true) */ /* { */ /* int u = rng() % (N - 1) + 2; */ /* /1* int v = rng() % (N - 1) + 2; *1/ */ /* /1* int U = T[u - 1] ^ 3; *1/ */ /* /1* int v = G[U][rng() % G[U].size()] + 1; *1/ */ /* if(u == n_ans[id].first) */ /* { */ /* continue; */ /* } */ /* n_ans[id].second = u; */ /* swap(n_ans[id].first,n_ans[id].second); */ /* /1* n_ans[id] = make_pair(u,v); *1/ */ /* break; */ /* } */ /* } */ /* long double n_score = 0; */ /* vector C = A,D = B; */ /* for(const auto &[u,v] : n_ans) */ /* { */ /* { */ /* long long x = (C[u - 1] + C[v - 1]) / 2; */ /* C[u - 1] = C[v - 1] = x; */ /* } */ /* { */ /* long long x = (D[u - 1] + D[v - 1]) / 2; */ /* D[u - 1] = D[v - 1] = x; */ /* } */ /* } */ /* vector ord(N); */ /* iota(ord.begin(),ord.end(),0); */ /* sort(ord.begin() + 1,ord.end(),[&](int i,int j) */ /* { */ /* return diff(C[i],D[i]) > diff(C[j],D[j]); */ /* }); */ /* for(int i = N - (sz - half);i < N;i++) */ /* { */ /* int id = ord[i]; */ /* { */ /* long long x = (C[0] + C[id]) / 2; */ /* C[0] = C[id] = x; */ /* } */ /* { */ /* long long x = (D[0] + D[id]) / 2; */ /* D[0] = D[id] = x; */ /* } */ /* n_ans.push_back(make_pair(1,id + 1)); */ /* } */ /* n_score = 2e6 - 1e5 * log10(diff(C[0],D[0]) + 1); */ /* long double temp = start_temp + (end_temp - start_temp) * (clock() - start_time) / TIME_LIMIT; */ /* long double prob = exp((n_score - score) / temp); */ /* if(prob > (long double)(rng() % M) / M) */ /* { */ /* swap(ans,n_ans); */ /* score = n_score; */ /* } */ /* } */ //output cout << ans.size() << "\n"; for(int i = 0;i < (int)ans.size();i++) { cout << ans[i].first << " " << ans[i].second << "\n"; } cerr << "Score : " << score << "\n"; cerr << "Loop : " << loop << "\n"; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int tt = 1; /* cin >> tt; */ while(tt--) Main(); }