#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; int sz = 50; int half = 25; int loop = 0; long double start_temp = 10,end_temp = 50; 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; } auto diff = [&M](long long a,long long b) -> long long { return max(abs(a - M),abs(b - M)); }; { vector C = A,D = B; for(int i = 0;i < half;i++) { while(true) { int u = rng() % (N - 1) + 2; /* int v = rng() % (N - 1) + 2; */ int U = T[u] ^ 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; } } 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; } 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; /* int v = rng() % (N - 1) + 2; */ int U = T[u] ^ 3; int v = G[U][rng() % G[U].size()] + 1; if(u == v) { continue; } n_ans[id] = make_pair(u,v); 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; } /* if(n_score > score) */ /* { */ /* 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(); }