int DBG = 0; double TL = 1.0; #include #include #include #include #include #include #include #include #include #include #include #include #include #include int STANDARD = 1; using namespace std; #define F0(i,n) for (int i=0; i=0; i--) #define F1(i,n) for (int i=1; i<=n; i++) #define CL(a,x) memset(x, a, sizeof(x)); #define SZ(x) ((int)x.size()) const int inf = 1000000000; const double pi = acos(-1.0); typedef pair pii; typedef long long ll; typedef unsigned long long ull; const double EPS = 1e-9; #define PR(x) cerr << #x << "=" << x << endl template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template ostream& operator<<(ostream& os, const tuple& p) { os << "(" << get<0>(p) << "," << get<1>(p) << "," << get<2>(p) << ")"; return os; } istream& operator>>(istream& is, pii& p) { is>>p.first>>p.second; return is; } template ostream& operator<<(ostream& os, const vector& v) { os << "["; F0(i,SZ(v)) { if (i>0) os << ","; os << v[i]; } os << "]"; return os; } template ostream& operator<<(ostream& os, const set& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ","; cerr << i; } os << "}"; return os; } template ostream& operator<<(ostream& os, const map& v) { os << "{"; int f=1; for(auto i:v) { if(f)f=0;else os << ", "; cerr << i.first << ":" << i.second; } os << "}"; return os; } #pragma GCC optimize("O3,Ofast,omit-frame-pointer,unroll-all-loops,tree-loop-vectorize,tree-slp-vectorize") #ifdef XYZ inline ll GetTSC() { ll lo, hi; asm volatile ("rdtsc": "=a"(lo), "=d"(hi)); return lo + (hi << 32); } inline double GetSeconds() { return GetTSC() / 3.0e9; } #else #include double GetSeconds() { timeval tv; gettimeofday(&tv, 0); return tv.tv_sec + tv.tv_usec * 1e-6; } #endif const int MAX_RAND = 1 << 30; struct Rand { ll x, y, z, w, o; Rand() {} Rand(ll seed) { reseed(seed); o = 0; } inline void reseed(ll seed) { x = 0x498b3bc5 ^ seed; y = 0; z = 0; w = 0; F0(i, 20) mix(); } inline void mix() { ll t = x ^ (x << 11); x = y; y = z; z = w; w = w ^ (w >> 19) ^ t ^ (t >> 8); } inline ll rand() { mix(); return x & (MAX_RAND - 1); } inline int nextInt(int n) { return rand() % n; } inline int nextInt(int L, int R) { return rand()%(R - L + 1) + L; } inline int nextBool() { if (o < 4) o = rand(); o >>= 2; return o & 1; } double nextDouble() { return rand() * 1.0 / MAX_RAND; } }; Rand my(2023); double saveTime; double t_o[20]; ll c_o[20]; void Init() { saveTime = GetSeconds(); F0(i, 20) t_o[i] = 0.0; F0(i, 20) c_o[i] = 0; } double Elapsed() { return GetSeconds() - saveTime; } void Report() { double tmp = Elapsed(); cerr << "-------------------------------------" << endl; cerr << "Elapsed time: " << tmp << " sec" << endl; double total = 0.0; F0(i, 20) { if (t_o[i] > 0) cerr << "t_o[" << i << "] = " << t_o[i] << endl; total += t_o[i]; } cerr << endl; //if (total > 0) cerr << "Total spent: " << total << endl; F0(i, 20) if (c_o[i] > 0) cerr << "c_o[" << i << "] = " << c_o[i] << endl; cerr << "-------------------------------------" << endl; } struct AutoTimer { int x; double t; AutoTimer(int x) : x(x) { t = Elapsed(); } ~AutoTimer() { t_o[x] += Elapsed() - t; } }; #define AT(i) AutoTimer a##i(i) //#define AT(i) // CONSTANTS const int N = 64; int n, m; ll bscore, score; vector bsol, sol; ll inA[N], inB[N], A[N], B[N]; pii way[N]; const int LOGN = 1 << 16; double logs[LOGN]; template void RS(vector& v) { F1(i, SZ(v)-1) { int j = my.nextInt(0, i); swap(v[i], v[j]); } } template T sqr(T x) { return x*x; } const ll T = 5e17; ll total_bscore; void Prepare() { //PR(n); bscore = inf; F0(i, LOGN) logs[i] = -log((i+0.5)/LOGN); // solve 1D version first ll bv = abs(inA[0] - T); bsol.clear(); my.reseed(2024); F0(runs, 100000) { F0(i, n) { A[i] = inA[i]; B[i] = inB[i]; } F0(it, 50) { F1(j, n - 1) { ll na = (A[0] + A[j]) / 2; ll nb = (B[0] + B[j]) / 2; ll av = max(abs(na - T), abs(nb - T)); if (av < bv) { bsol.clear(); F0(i, it) bsol.push_back(way[i]); bsol.push_back({0, j}); bv = av; } } int i0 = 0; int i1 = my.nextInt(1, n-1); if (my.nextInt(64) == 0) i0 = my.nextInt(1, n-1); while (A[i0] == A[i1]) { i1 = my.nextInt(1, n-1); } A[i0] = A[i1] = (A[i0] + A[i1]) / 2; B[i0] = B[i1] = (B[i0] + B[i1]) / 2; way[it] = {i0, i1}; } } // A=B 56397873 // 34857358 bscore = 2000000-100000*(log10(bv))+1; bscore = (bv == 0LL ? 2000050LL - SZ(bsol) : (long long)(2000000.0L - 100000.0L * log10(bv + 1.0L))); PR(bscore); total_bscore += bscore; } void UpdateBest() { if (score < bscore) { bscore = score; bsol = sol; } } void Solve() { Prepare(); cout << SZ(bsol) << endl; F0(i, SZ(bsol)) { cout << bsol[i].first + 1 << " " << bsol[i].second + 1 << endl; } //Report(); } void ReadInput() { cin >> n; F0(i, n) cin >> inA[i] >> inB[i]; } int main(int argc, char* argv[]) { Init(); int FIRST_TEST = 1; // atcoder int seed1 = FIRST_TEST, seed2 = 50; if(argc>1) { if (argc == 2) { seed1 = seed2 = atoi(argv[1]); } else { seed1 = atoi(argv[1]); seed2 = atoi(argv[2]); } STANDARD=0; } if(STANDARD) { ReadInput(); Solve(); return 0; } for (int seed=seed1; seed<=seed2; seed++) { if(seed>=FIRST_TEST && seed<100) { char inp[128]; sprintf(inp, "in/in%03d.txt", seed); char outp[128]; sprintf(outp, "out/%04d.txt", seed); ignore = freopen(inp, "r", stdin); ignore = freopen(outp, "w", stdout); ReadInput(); cerr << endl << "Seed #" << seed << " " << endl; Solve(); //cerr << bscore << endl; //cout << "Score would be " << bscore << endl; } else { // Generate throw; Rand my(seed); } } PR(total_bscore); return 0; }