import copy import random from time import perf_counter import argparse import sys import math class TimeKeeper: def __init__(self): self.start_time = perf_counter() def is_time_over(self, LIMIT): return (perf_counter() - self.start_time) >= LIMIT def time_now(self): return (perf_counter() - self.start_time) def calscore(ans, C0): C = C0[:] X = len(ans) sc = 0 for i in range(X): u, v = ans[i] a0, b0 = C[u] a1, b1 = C[v] C[u] = (a0 + a1)//2, (b0 + b1)//2 C[v] = (a0 + a1)//2, (b0 + b1)//2 V1 = abs(C[0][0] - 5*10**17) V2 = abs(C[0][1] - 5*10**17) sc = int(2*10**6 - 10**5 * math.log10(max(V1, V2) + 1)) return sc ########################################### def main(DEBUG): tk = TimeKeeper() if DEBUG == True: LIMIT = 0.85 else: LIMIT = 0.85 def output(ans): print(len(ans)) for i in range(len(ans)): u, v = ans[i] u += 1 v += 1 print(u, v) return def solve1(LIMIT): C = C0[:] ans = [] a0 = C[0][0] b0 = C[0][1] V1 = abs(a0 - 5*10**17) V2 = abs(b0 - 5*10**17) nowV = max(V1, V2) while len(ans) < 50: if tk.is_time_over(LIMIT): break for i in range(1, N): ai, bi = C[i][0], C[i][1] nxV1 = abs((a0 + ai) // 2 - 5*10**17) nxV2 = abs((b0 + bi) // 2 - 5*10**17) nxtV = max(nxV1, nxV2) if nxtV < nowV: nowV = nxtV a0 = (a0 + ai) // 2 b0 = (b0 + bi) // 2 C[i] = (a0, b0) ans.append((0, i)) sc = int(2*10**6 - 10**5 * math.log10(nowV + 1)) print(sc, nowV, a0, b0, file=sys.stderr) return ans def solve2(LIMIT): C = C0[:] ans = [] a0 = C[0][0] b0 = C[0][1] V1 = abs(a0 - 5*10**17) V2 = abs(b0 - 5*10**17) nowV = max(V1, V2) finish = False while len(ans) < 50 and finish == False: finish = True for i in range(1, N): ai, bi = C[i][0], C[i][1] nxV1 = abs((a0 + ai) // 2 - 5*10**17) nxV2 = abs((b0 + bi) // 2 - 5*10**17) nxtV = max(nxV1, nxV2) if nxtV < nowV: nowV = nxtV a0 = (a0 + ai) // 2 b0 = (b0 + bi) // 2 C[i] = (a0, b0) ans.append((0, i)) sc = int(2*10**6 - 10**5 * math.log10(nowV + 1)) print(sc, nowV, a0, b0, file=sys.stderr) finish = False ### while True: if tk.is_time_over(LIMIT): print("timeover", file=sys.stderr) break inow = random.randint(1, N-1) a0 = C[inow][0] b0 = C[inow][1] V1 = abs(a0 - 5*10**17) V2 = abs(b0 - 5*10**17) nowV = max(V1, V2) finish = False while len(ans) < 50 and finish == False: finish = True for i in range(1, N): if i == inow: continue ai, bi = C[i][0], C[i][1] nxV1 = abs((a0 + ai) // 2 - 5*10**17) nxV2 = abs((b0 + bi) // 2 - 5*10**17) nxtV = max(nxV1, nxV2) if nxtV < nowV: nowV = nxtV a0 = (a0 + ai) // 2 b0 = (b0 + bi) // 2 C[i] = (a0, b0) ans.append((inow, i)) # sc = int(2*10**6 - 10**5 * math.log10(nowV + 1)) # print(sc, nowV, a0, b0, file=sys.stderr) finish = False a0 = C[0][0] b0 = C[0][1] V1 = abs(a0 - 5*10**17) V2 = abs(b0 - 5*10**17) nowV = max(V1, V2) finish = False while len(ans) < 50 and finish == False: finish = True for i in range(1, N): ai, bi = C[i][0], C[i][1] nxV1 = abs((a0 + ai) // 2 - 5*10**17) nxV2 = abs((b0 + bi) // 2 - 5*10**17) nxtV = max(nxV1, nxV2) if nxtV < nowV: nowV = nxtV a0 = (a0 + ai) // 2 b0 = (b0 + bi) // 2 C[i] = (a0, b0) ans.append((0, i)) sc = int(2*10**6 - 10**5 * math.log10(nowV + 1)) print(sc, nowV, a0, b0, file=sys.stderr) finish = False return ans def solve3(LIMIT): C = C0[:] ans = [] N = int(input()) C0 = [] for i in range(N): a, b = map(int, input().split()) C0.append((a, b)) ans = solve2(LIMIT) sc = calscore(ans[:50], C0) print("SC", sc, file=sys.stderr) output(ans[:50]) return if __name__ == '__main__': parser = argparse.ArgumentParser(description='Debug mode') parser.add_argument('--debug', action='store_true', help='Enable debug mode') args = parser.parse_args() main(args.debug)