結果

問題 No.282 おもりと天秤(2)
ユーザー MamonboMamonbo
提出日時 2015-10-07 18:10:19
言語 Python3
(3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果
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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
27,608 KB
testcase_01 AC 53 ms
27,096 KB
testcase_02 AC 52 ms
27,480 KB
testcase_03 AC 53 ms
27,352 KB
testcase_04 AC 53 ms
27,480 KB
testcase_05 AC 55 ms
27,608 KB
testcase_06 AC 54 ms
27,352 KB
testcase_07 AC 53 ms
27,352 KB
testcase_08 AC 55 ms
27,224 KB
testcase_09 AC 52 ms
27,864 KB
testcase_10 AC 105 ms
27,352 KB
testcase_11 AC 189 ms
27,736 KB
testcase_12 AC 85 ms
27,480 KB
testcase_13 AC 116 ms
27,352 KB
testcase_14 AC 174 ms
27,736 KB
testcase_15 AC 197 ms
27,864 KB
testcase_16 AC 63 ms
27,512 KB
testcase_17 AC 122 ms
27,352 KB
testcase_18 AC 161 ms
27,608 KB
testcase_19 AC 166 ms
27,608 KB
testcase_20 AC 216 ms
27,336 KB
testcase_21 AC 205 ms
27,568 KB
testcase_22 AC 201 ms
27,720 KB
testcase_23 AC 51 ms
27,592 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