結果

問題 No.282 おもりと天秤(2)
ユーザー Mamonbo
提出日時 2015-10-07 18:10:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 216 ms / 5,000 ms
コード長 2,217 bytes
コンパイル時間 105 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 27,864 KB
平均クエリ数 30.58
最終ジャッジ日時 2024-07-16 21:37:50
合計ジャッジ時間 4,757 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#coding=UTF-8
#日本語準備 あーテステス

#quick sortじゃ2000回に間に合わない😢👎
#そこでBitonic Sortを実装して圧倒的成長💪😆👍
#まともなソースが英語版Wikipediaにしかないことにより
#「グローバル人材」として圧倒的成長💪🙌
#作問者に圧倒的感謝🙏
import sys

def makered(start,end,reverse=False):
    hanuke=redbox_len//2
    if not reverse:
        for idx in range(start,end-hanuke,1):
            kensa.append((idx,idx+hanuke))
    else:
        for idx in range(end-1,start-1+hanuke,-1):
            kensa.append((idx,idx-hanuke))
            
N=int(input())
#bitnic sortは2**k個のときしか出来ない
for idx in range(0,10,1):
    if N<= 2**idx:
        next_kiri=2**idx
        next_kata=idx
        break

narabi=[0]*(next_kiri-N)+list(range(1,N+1,1))
#print(narabi)        
for idx in range(1,next_kata+1,1):
    #2**idx個要素があるソート列を作る
    #wikipediaの青緑の列1つ分にあたる
    for idy in range(idx,0,-1):
        #要素数が2**idy個ある赤い箱を作る
        #wikipediaの赤い箱が並んでいる列に相当する
        kensa=[]
        redbox_len=2**idy
        reverse=False
        for idz in range(0,2**(next_kata-idy),1):
            makered(redbox_len*idz,redbox_len*(idz+1),\
                    (redbox_len*idz//(2**idx)%2)==1)
            #reverseは対象の第idx+1番目のビットで決まる
        #print(kensa)    
        #クエリを作る
        #具体的には参照して文字列化と0パディング
        nage='?'
        for mono in kensa:
            nage=nage + ' {0} {1}'.format(narabi[mono[0]],narabi[mono[1]])
        paddin=N-next_kiri//2
        nage=nage+' 0 0'*paddin
        print(nage)
        sys.stdout.flush()
        mojir=input()
        kekka=mojir.split(' ')
        for idz in range(0,len(kensa),1):
            if kekka[idz]=='>':
                narabi[kensa[idz][0]],narabi[kensa[idz][1]]=\
                narabi[kensa[idz][1]],narabi[kensa[idz][0]]


#遂に結果の出力
demoji='!'
for suu in narabi:
    if suu != 0:
        demoji=demoji+' '+str(suu)

print(demoji)
#SKK辞書euc-jpなんだよね
0