結果

問題 No.5007 Steiner Space Travel
ユーザー Akijin_007Akijin_007
提出日時 2022-07-30 17:05:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 898 ms / 1,000 ms
コード長 2,012 bytes
コンパイル時間 501 ms
実行使用メモリ 83,252 KB
スコア 6,076,643
最終ジャッジ日時 2022-07-30 17:05:45
合計ジャッジ時間 30,099 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 889 ms
83,092 KB
testcase_01 AC 890 ms
83,016 KB
testcase_02 AC 895 ms
82,904 KB
testcase_03 AC 892 ms
83,000 KB
testcase_04 AC 890 ms
82,988 KB
testcase_05 AC 892 ms
83,236 KB
testcase_06 AC 890 ms
82,908 KB
testcase_07 AC 887 ms
82,976 KB
testcase_08 AC 886 ms
82,912 KB
testcase_09 AC 896 ms
82,960 KB
testcase_10 AC 896 ms
82,900 KB
testcase_11 AC 892 ms
82,900 KB
testcase_12 AC 895 ms
82,852 KB
testcase_13 AC 895 ms
82,948 KB
testcase_14 AC 889 ms
83,252 KB
testcase_15 AC 889 ms
83,156 KB
testcase_16 AC 895 ms
82,936 KB
testcase_17 AC 896 ms
82,960 KB
testcase_18 AC 894 ms
83,092 KB
testcase_19 AC 891 ms
82,904 KB
testcase_20 AC 891 ms
82,912 KB
testcase_21 AC 898 ms
83,036 KB
testcase_22 AC 887 ms
83,108 KB
testcase_23 AC 896 ms
82,944 KB
testcase_24 AC 886 ms
82,984 KB
testcase_25 AC 887 ms
83,044 KB
testcase_26 AC 887 ms
82,964 KB
testcase_27 AC 894 ms
82,984 KB
testcase_28 AC 889 ms
83,164 KB
testcase_29 AC 889 ms
82,928 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def printout():
    for i in range(M):
        print(c[i], d[i])
    V = len(t)
    print(V)
    for i in range(V):
        print(t[i], r[i])

def fileout():
    f = open(r"C:\Users\AwanoShota\OneDrive\ドキュメント\kojinyou\atcoder\yukicoder_marathon\out.txt", "w")
    for i in range(M):
        f.write("{} {}\n".format(c[i], d[i]))
    V = len(t)
    f.write(str(V) + "\n")
    for i in range(V):
        f.write("{} {}\n".format(t[i], r[i]))

def calc_dis(t1, t2, u, v):
    if t1 == 1:
        x1 = a[u]
        y1 = b[u]
    else:
        x1 = c[u]
        y1 = d[u]
    if t2 == 1:
        x2 = a[v]
        y2 = b[v]
    else:
        x2 = c[v]
        y2 = d[v]
    return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5

import random
import time

N, M = map(int, input().split())
a = [0] * N
b = [0] * N
for i in range(N):
    a[i], b[i] = map(int, input().split())

ut = time.time()

c = [0] * M
d = [0] * M

for i in range(M):
    c[i] = random.randint(0, 1000)
    d[i] = random.randint(0, 1000)

while time.time() - ut < 0.8:
    sc = [0] * M
    sd = [0] * M
    pos = [0] * M
    for i in range(N):
        e = 0
        f = float("INF")
        for j in range(M):
            ff = calc_dis(1, 2, i, j)
            if f > ff:
                f = ff
                e = j
        pos[e] += 1
        sc[e] += a[i]
        sd[e] += b[i]

    for i in range(M):
        if pos[i] == 0:
            continue
        c[i] = round(sc[i] / pos[i])
        d[i] = round(sd[i] / pos[i])

pos = [[] for i in range(M)]

for i in range(N):
    e = 0
    f = float("INF")
    for j in range(M):
        ff = calc_dis(1, 2, i, j)
        if f > ff:
            f = ff
            e = j
    pos[e].append(i)

t = [1]
r = [1]

# print(pos)

for i in range(M):
    if len(pos[i]) == 0:
        continue
    t.append(2)
    r.append(i+1)
    for x in pos[i]:
        t.append(1)
        r.append(x+1)
        t.append(2)
        r.append(i+1)
    t.append(2)
    r.append(i+1)

t.append(1)
r.append(1)

printout()
0