結果

問題 No.5007 Steiner Space Travel
ユーザー titan23titan23
提出日時 2022-07-30 17:49:18
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 971 ms / 1,000 ms
コード長 2,360 bytes
コンパイル時間 281 ms
実行使用メモリ 87,124 KB
スコア 5,935,673
最終ジャッジ日時 2022-07-30 17:50:06
合計ジャッジ時間 32,299 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 968 ms
86,932 KB
testcase_01 AC 968 ms
86,344 KB
testcase_02 AC 969 ms
85,956 KB
testcase_03 AC 971 ms
85,336 KB
testcase_04 AC 968 ms
85,668 KB
testcase_05 AC 970 ms
85,944 KB
testcase_06 AC 964 ms
84,752 KB
testcase_07 AC 969 ms
86,040 KB
testcase_08 AC 970 ms
84,916 KB
testcase_09 AC 969 ms
86,340 KB
testcase_10 AC 968 ms
85,144 KB
testcase_11 AC 965 ms
86,736 KB
testcase_12 AC 966 ms
85,160 KB
testcase_13 AC 967 ms
86,308 KB
testcase_14 AC 966 ms
86,684 KB
testcase_15 AC 966 ms
85,736 KB
testcase_16 AC 964 ms
86,044 KB
testcase_17 AC 967 ms
85,764 KB
testcase_18 AC 966 ms
85,700 KB
testcase_19 AC 967 ms
85,844 KB
testcase_20 AC 969 ms
86,036 KB
testcase_21 AC 966 ms
86,300 KB
testcase_22 AC 967 ms
85,548 KB
testcase_23 AC 964 ms
85,948 KB
testcase_24 AC 968 ms
86,160 KB
testcase_25 AC 966 ms
87,044 KB
testcase_26 AC 966 ms
85,524 KB
testcase_27 AC 964 ms
86,528 KB
testcase_28 AC 970 ms
86,052 KB
testcase_29 AC 962 ms
87,124 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import time
import random
from heapq import heapify, heappush, heappop
input = lambda: sys.stdin.readline().rstrip()

#  -----------------------  #

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(n)]
ab_set = set(ab)
ALP = 5
ALP2 = 25
LIMIT = 0.86
START = time.time()

def calc_score(root):
  ans = 0
  E = []
  for i in range(1, n):
    u, v = root[i][1]-1, root[i-1][1]-1
    tmp = (ab[u][0] - ab[v][0])*(ab[u][0] - ab[v][0]) + (ab[u][1] - ab[v][1])*(ab[u][1] - ab[v][1])
    heappush(E, (tmp, i))
    if len(E) > 8:
      heappop(E)
    ans += ALP2 * tmp

  v = root[-1][1]
  tmp = (ab[0][0] - ab[v][0])*(ab[0][0] - ab[v][0]) + (ab[0][1] - ab[v][1])*(ab[0][1] - ab[v][1])
  ans += ALP2 * tmp
  heappush(E, (tmp, n))
  if len(E) > 8:
    heappop(E)

  stations = []
  E.sort(key=lambda x: x[1])
  for c,i in E:
    if i == n:
      v = root[-1][1]-1
      stations.append(((ab[0][0] + ab[v][0])>>1, (ab[0][1] + ab[v][1])>>1))
      ans -= c * ALP2
      ans += c * ALP
    else:
      u, v = root[i][1]-1, root[i-1][1]-1
      stations.append(((ab[u][0] + ab[v][0])>>1, (ab[u][1] + ab[v][1])>>1))
      ans -= c * ALP2
      ans += c * ALP

  for i in range(8):
    if E[i][1] + i > len(root):
      root.append((E[i][1]+i, (2, i+1, 0)))
    else:
      root.insert(E[i][1]+i, (2, i+1, 0))
  return root, stations, ans

def make_stations():
  stations = []
  return stations

def make_root():
  C = [(1, i, ab[i-1]) for i in range(2, n+1)]

  c = []
  d1 = random.randint(10, 300)
  d2 = random.randint(10, 300)
  a, b = list(range(1000//d1 + 3)), list(range(1000//d2 + 3))
  i = random.randint(0, len(a))
  a = a[i:] + a[:i]
  b = b[i:] + b[:i]
  for i in a:
    b = b[::-1]
    for j in b:
      tmp = []
      for k in C:
        if d1*i <= k[2][0] <= d1*(i+1) and d2*j <= k[2][1] <= d2*(j+1):
          tmp.append(k)
      for t in tmp:
        C.remove(t)
      tmp.sort(key=lambda x: sum(x[2]))
      c.extend(tmp)
  return [(1, 1, 0)] + c

vestscore = float('inf')
st, ro = [], []
while time.time() - START < LIMIT:
  root = make_root()
  try:
    root, stations, score = calc_score(root)
    if score < vestscore:
      vestscore = score
      st = stations[:]
      ro = root[:]
  except IndexError:
    pass
for i,j in st:
  print(i, j)
print(len(ro)+1)
for i,j,_ in ro:
  print(i, j)
print(1, 1)
0