結果

問題 No.282 おもりと天秤(2)
ユーザー MamonboMamonbo
提出日時 2015-10-07 18:10:19
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
AC  
実行時間 165 ms / 5,000 ms
コード長 2,217 bytes
コンパイル時間 463 ms
コンパイル使用メモリ 10,888 KB
実行使用メモリ 24,368 KB
平均クエリ数 30.58
最終ジャッジ日時 2023-09-23 21:50:00
合計ジャッジ時間 3,646 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 41 ms
23,672 KB
testcase_01 AC 34 ms
24,312 KB
testcase_02 AC 33 ms
23,568 KB
testcase_03 AC 33 ms
23,724 KB
testcase_04 AC 36 ms
23,412 KB
testcase_05 AC 34 ms
23,980 KB
testcase_06 AC 36 ms
23,556 KB
testcase_07 AC 34 ms
24,060 KB
testcase_08 AC 36 ms
23,440 KB
testcase_09 AC 34 ms
23,652 KB
testcase_10 AC 74 ms
24,048 KB
testcase_11 AC 146 ms
23,828 KB
testcase_12 AC 63 ms
24,092 KB
testcase_13 AC 81 ms
24,368 KB
testcase_14 AC 156 ms
24,164 KB
testcase_15 AC 156 ms
24,012 KB
testcase_16 AC 43 ms
24,060 KB
testcase_17 AC 81 ms
24,132 KB
testcase_18 AC 124 ms
24,020 KB
testcase_19 AC 133 ms
24,136 KB
testcase_20 AC 165 ms
24,040 KB
testcase_21 AC 165 ms
23,940 KB
testcase_22 AC 160 ms
23,788 KB
testcase_23 AC 34 ms
23,596 KB
権限があれば一括ダウンロードができます

ソースコード

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