結果

問題 No.282 おもりと天秤(2)
ユーザー MamonboMamonbo
提出日時 2015-10-07 17:32:43
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
RE  
実行時間 -
コード長 2,632 bytes
コンパイル時間 312 ms
コンパイル使用メモリ 12,928 KB
実行使用メモリ 28,120 KB
平均クエリ数 1.04
最終ジャッジ日時 2024-07-16 06:27:10
合計ジャッジ時間 6,395 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
27,352 KB
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 51 ms
27,336 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

#quick sortじゃ2000回に間に合わない😢👎
#そこでBitonic Sortを実装して圧倒的成長💪😆👍
#まともなソースが英語版Wikipediaにしかないことにより
#「グローバル人材」として圧倒的成長💪🙌
#作問者に圧倒的感謝🙏
import sys
def bit_sort(start,end,reverse=False):
    if end-start>=2:
        #1個のやつは(昇順、降順ともに)整列済
        bit_sort(start,end//2,False)
        bit_sort(end//2,end,True)
        bit_merge(start,end,reverse)

def bit_merge(start,end,reverse):
    #統合して(配列を)圧倒的成長
    if end-start>=2:
        bit_cmp(start,end,reverse)
        bit_merge(start,end//2,reverse)
        bit_merge(end//2,end,reverse)

        
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))
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番目のビットで決まる
            
        #クエリを作る
        #具体的には参照して文字列化と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