結果

問題 No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ
コンテスト
ユーザー titia
提出日時 2024-02-28 02:24:22
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,234 bytes
コンパイル時間 424 ms
コンパイル使用メモリ 82,944 KB
実行使用メモリ 87,128 KB
最終ジャッジ日時 2024-09-29 12:13:49
合計ジャッジ時間 9,387 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline

from random import randint,shuffle

T=int(input())
for tests in range(T):
    N,L=map(int,input().split())
    P=[list(map(int,input().split())) for i in range(N)]

    ANS=list(range(N))
    shuffle(ANS)
    
    NOW=0

    for i in range(1,len(ANS)):
        x,y=P[ANS[i]]
        z,w=P[ANS[i-1]]

        NOW+=abs(x-z)+abs(y-w)

    while NOW>998*L:
        c0=randint(0,len(ANS)-1)
        c1=randint(0,len(ANS)-1)

        if x==y:
            continue

        NOW2=NOW

        for i in [c0,c0+1,c1,c1+1] :
            if 0<=i-1 and i<len(ANS):
                x,y=P[ANS[i]]
                z,w=P[ANS[i-1]]

                NOW2-=abs(x-z)+abs(y-w)

        ANS[c0],ANS[c1]=ANS[c1],ANS[c0]

        for i in [c0,c0+1,c1,c1+1] :
            if 0<=i-1 and i<len(ANS):
                x,y=P[ANS[i]]
                z,w=P[ANS[i-1]]

                NOW2+=abs(x-z)+abs(y-w)

        if NOW2<=NOW:
            NOW=NOW2
            pass
        else:
            ANS[c0],ANS[c1]=ANS[c1],ANS[c0]

    print(len(ANS)+1)
    for i in range(len(ANS)):
        x,y=P[ANS[i]]

        print(x,y)

    x,y=P[ANS[0]]
    print(x,y)
0