#pragma GCC target("avx2") #pragma GCC optimize("Ofast,unroll-loops") #include #include #include #include struct timeval tt; double beg, cur; #define MT_N 624 #define MT_M 397 #define MT_MATRIX_A 0x9908b0dfUL #define MT_UPPER_MASK 0x80000000UL #define MT_LOWER_MASK 0x7fffffffUL static unsigned int mt[MT_N]; static int mti = MT_N + 1; void init_genrand(unsigned int s) { mt[0] = s & 0xffffffffUL; for (mti = 1; mti < MT_N; mti++) { mt[mti] = (1812433253UL * (mt[mti-1] ^ (mt[mti-1] >> 30)) + mti); mt[mti] &= 0xffffffffUL; } } unsigned int genrand() { unsigned int y; static unsigned int mag01[2] = {0x0UL, MT_MATRIX_A}; if (mti >= MT_N) { int kk; if (mti == MT_N + 1) init_genrand(5489UL); for (kk = 0; kk < MT_N - MT_M; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+MT_M] ^ (y >> 1) ^ mag01[y&0x1UL]; } for (; kk < MT_N - 1; kk++) { y = (mt[kk] & MT_UPPER_MASK) | (mt[kk+1] & MT_LOWER_MASK); mt[kk] = mt[kk+(MT_M-MT_N)] ^ (y >> 1) ^ mag01[y&0x1UL]; } y = (mt[MT_N-1] & MT_UPPER_MASK) | (mt[0] & MT_LOWER_MASK); mt[MT_N-1] = mt[MT_M-1] ^ (y >> 1) ^ mag01[y&0x1UL]; mti = 0; } y = mt[mti++]; y ^= (y >> 11); y ^= (y << 7) & 0x9d2c5680UL; y ^= (y << 15) & 0xefc60000UL; y ^= (y >> 18); return y; } void shuffle_permutation(int N, int p[], int K) { int i, j; while (K--) { i = genrand() % N + 1; j = genrand() % N + 1; if (i != j) { p[i] ^= p[j]; p[j] ^= p[i]; p[i] ^= p[j]; } } } void chmax(long long *a, long long b) { if (*a < b) *a = b; } const long long THR = 500000000000000000LL; int score(int N, long long A[], long long B[]) { static long long tmp; tmp = llabs(A[1] - THR); chmax(&tmp, llabs(B[1] - THR)); if (tmp == 0) return 2000050; return (int)(2000000 - 100000 * log10(tmp + 1.0)); } long long score_random_playout(int N, long long AA[], long long BB[], int K, int L) { static int i, j, k; static long long A[46], B[46], ans, tmp; ans = 0; while (L--) { for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } for (k = 1; k <= K; k++) { do { i = genrand() % N + 1; j = genrand() % N + 1; } while (i == j); tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; } ans += score(N, A, B); } return ans; } int random_playout_based_greedy(int N, long long AA[], long long BB[], int K, int move[][2]) { static int i, j, k; static long long A[46], B[46], tmp, tmpp[2][2], max; for (i = 1; i <= N; i++) { A[i] = AA[i]; B[i] = BB[i]; } for (k = 1; k <= K; k++) { if (A[i] == THR && B[i] == THR) return -(k - 1); for (i = 1, max = 0; i <= N; i++) { for (j = i + 1; j <= N; j++) { tmpp[0][0] = A[i]; tmpp[0][1] = A[j]; tmpp[1][0] = B[i]; tmpp[1][1] = B[j]; tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; tmp = score_random_playout(N, A, B, K - k, 40); if (max < tmp) { max = tmp; move[k][0] = i; move[k][1] = j; } A[i] = tmpp[0][0]; A[j] = tmpp[0][1]; B[i] = tmpp[1][0]; B[j] = tmpp[1][1]; } } i = move[k][0]; j = move[k][1]; tmp = (A[i] + A[j]) / 2; A[i] = tmp; A[j] = tmp; tmp = (B[i] + B[j]) / 2; B[i] = tmp; B[j] = tmp; } return score(N, A, B); } int main() { gettimeofday(&tt, NULL); beg = tt.tv_sec + (double)tt.tv_usec / 1000000; int i, N; long long A[46], B[46]; scanf("%d", &N); for (i = 1; i <= N; i++) scanf("%lld %lld", &(A[i]), &(B[i])); int k, move[51][2]; k = random_playout_based_greedy(N, A, B, 50, move); // printf("%d\n", k); if (k <= 0) k *= -1; else k = 50; printf("%d\n", k); for (i = 1; i <= k; i++) printf("%d %d\n", move[i][0], move[i][1]); fflush(stdout); return 0; }