結果
問題 | No.5020 Averaging |
ユーザー |
![]() |
提出日時 | 2024-02-25 13:42:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 101 ms / 1,000 ms |
コード長 | 2,245 bytes |
コンパイル時間 | 318 ms |
コンパイル使用メモリ | 81,828 KB |
実行使用メモリ | 79,928 KB |
スコア | 19,167,042 |
最終ジャッジ日時 | 2024-02-25 13:43:01 |
合計ジャッジ時間 | 7,276 ms |
ジャッジサーバーID (参考情報) |
judge10 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 50 |
ソースコード
from dataclasses import dataclass, field # from sortedcontainers import SortedList, SortedDict, SortedSet from random import random, seed, randrange, choice, sample # from itertools import permutations, combinations, product from collections import deque, defaultdict, Counter # from heapq import heapify, heappush, heappop # from bisect import bisect_right, bisect_left from time import time import sys sys.setrecursionlimit(1000000) seed(0) def input(): return sys.stdin.buffer.readline().rstrip().decode(encoding='utf-8') try: isLocal except: isLocal = False if isLocal: input = line def randrange_s(stop:int)->int: return int(random()*stop) def randrange_ss(start:int, stop:int)->int: return int(random()*(stop-start)+start) class AHC(): def __init__(self): self.sTime = time() self.get_input() self.preprocessing() def get_input(self): self.N = int(input()) AB = [list(map(int, input().split())) for _ in range(self.N)] self.A, self.B = [], [] for a, b in AB: self.A.append(float(a)) self.B.append(float(b)) return def preprocessing(self): self.target = float(5*10**17) return def get_score(self): return max(abs(self.target-self.A[0]), abs(self.target-self.B[0])) def get_score2(self, a, b): return max(abs(self.target-a), abs(self.target-b)) def greedy(self): self.ans = [] self.cur = self.get_score() for _ in range(50): evaList = [] for i in range(1, self.N): a = (self.A[0]+self.A[i])/2 b = (self.B[0]+self.B[i])/2 evaList.append([self.get_score2(a, b), i]) nxt, v = min(evaList) if nxt>=self.cur: break self.cur = nxt self.ans.append(f"1 {v+1}") mean = (self.A[0]+self.A[v])/2 self.A[0] = mean self.A[v] = mean mean = (self.B[0]+self.B[v])/2 self.B[0] = mean self.B[v] = mean return def update(self): pass def output(self): print(len(self.ans)) print("\n".join(self.ans)) ahc = AHC() ahc.greedy() ahc.output()