#define _USE_MATH_DEFINES #pragma GCC target("avx2") #pragma GCC optimize("O3") #include #include #include #include #include #include using namespace std; #define LP(I,S,G) for (long long int I = (S); I < (G); ++I) #define IN(X) for (int in = 0; in < X.size(); in++)cin >> X[in] #define OUT(X) for (int in = 0; in < X.size(); in++)cout << X[in]<<" " #define SORT(X) sort((X).begin(), (X).end()) #define CSORT(X,Y) sort(X.begin(), X.end(),Y) #define COPY(X,Y) copy(X.begin(), X.end(), Y.begin()) #define ALL(X,Y) for (auto (X) :(Y)) #define FULL(a) (a).begin(),(a).end() #define BFS(Q,S) for(Q.push(S);Q.size()!=0;Q.pop()) typedef long long int ll; typedef unsigned long long int ull; long long int M = 998244353; chrono::system_clock::time_point starttime; using namespace std::chrono; #ifndef ONLINE_JUDGE #define DEBUG #endif inline float getTime() { #ifdef DEBUG return duration_cast(system_clock::now() - starttime).count() /4.0; #else return duration_cast(system_clock::now() - starttime).count(); #endif } int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }; ll MAX(ll A, ll B) { return ((A) > (B) ? (A) : (B)); } ll MIN(ll A, ll B) { return ((A) < (B) ? (A) : (B)); } inline long long int xor128() { static long long int x = 123456789, y = 362436069, z = 521288629, w = 88675123; long long int t = (x ^ (x << 11)); x = y; y = z; z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } long long int pow_n(long long int x, long long int n) { if (n == 0) return 1; if (n % 2 == 0) return pow_n(x * x, n / 2); else return x * pow_n(x, n - 1); } ll border = 5 * pow_n(10, 17); double calc_score(array, 45> &ta, array, 45> &tb, vector>& ans, int from = 0) { for (int i = from; i < ans.size(); ++i) { int u = ans[i].first, v = ans[i].second; ll ua = (--ta[u].upper_bound(i))->second; ll va = (--ta[v].upper_bound(i))->second; ll ub = (--tb[u].upper_bound(i))->second; ll vb = (--tb[v].upper_bound(i))->second; ta[u][i + 1] = ta[v][i + 1] = (ua + va) / 2; tb[u][i + 1] = tb[v][i + 1] = (ub + vb) / 2; } return log10(max(abs(border - (--ta[0].upper_bound(50))->second) , abs(border - (--tb[0].upper_bound(50))->second)) + 1); } int main(int argc, char* argv[]) { starttime = chrono::system_clock::now(); ios::sync_with_stdio(false); std::cin.tie(nullptr); mt19937 rnd(0); ll n, t = 50, now = 0; cin >> n; array, 45> ta, tb; LP(i, 0, n) { ll a, b; cin >> a >> b; ta[i][0] = a; tb[i][0] = b; } vector> ans(t); LP(i, 0, t) { ans[i].first = xor128() % n; ans[i].second = xor128() % (n - 1); if (ans[i].second >= ans[i].first)++ans[i].second; } double score = calc_score(ta, tb, ans); vector table(t); for (int i = 0; i < t; ++i)table[i] = i; double time; shuffle(table.begin(), table.end(), rnd); int cnt = 0; while ((time=getTime()) <= 950) { double temp = 0.75*(950 - time) / 950.0; int i = table[now]; int bx = ans[i].first, by = ans[i].second; ta[bx].erase(i+1); ta[by].erase(i+1); tb[bx].erase(i+1); tb[by].erase(i+1); ans[i].first = xor128() % n; ans[i].second = xor128() % (n - 1); if (ans[i].second >= ans[i].first)++ans[i].second; if (xor128() % 10==0) { ans[i].first = 0; ll minRes = LLONG_MAX; ll ua = (--ta[0].upper_bound(i))->second; ll ub = (--tb[0].upper_bound(i))->second; for (int k = 1; k < n; ++k) { ll va = (--ta[k].upper_bound(i))->second; ll vb = (--tb[k].upper_bound(i))->second; if (max(abs((ua + va) / 2 - border), abs((ub + vb) / 2 - border)) < minRes)minRes = max(abs((ua + va) / 2 - border), abs((ub + vb) / 2 - border)), ans[i].second = k; } } double new_score = calc_score(ta, tb, ans, i); if (xor128() % 10000 < exp((score-new_score) / temp) * 10000) { score = new_score; } else { ta[ans[i].first].erase(i + 1); ta[ans[i].second].erase(i + 1); tb[ans[i].first].erase(i + 1); tb[ans[i].second].erase(i + 1); ans[i].first = bx; ans[i].second = by; calc_score(ta, tb, ans, i); } ++cnt; if (++now == t) { now = 0; shuffle(table.begin(), table.end(), rnd); } } cerr << cnt; cerr << "score:" << ll(2000000 - 100000 * log10(max(abs(border - (--ta[0].upper_bound(50))->second), abs(border - (--tb[0].upper_bound(50))->second)) + 1)) << "\n"; cerr << (--ta[0].upper_bound(50))->second << " " << (--tb[0].upper_bound(50))->second << "\n"; cout << ans.size() << "\n"; ALL(x, ans)cout << x.first+1 << " " << x.second+1 << "\n"; exit(0); }