結果
問題 |
No.2978 Lexicographically Smallest and Largest Subarray
|
ユーザー |
|
提出日時 | 2024-12-02 12:38:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 334 ms / 2,000 ms |
コード長 | 1,140 bytes |
コンパイル時間 | 289 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 94,440 KB |
平均クエリ数 | 1499.00 |
最終ジャッジ日時 | 2024-12-02 12:38:32 |
合計ジャッジ時間 | 20,973 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 57 |
ソースコード
import collections,random n,q = map(int,input().split()) #p = [random.randint(0,10000) for i in range(1000)] def query(a,b,c,d): print('?',a+1,b+1,c+1,d+1,flush=True) x = int(input()) #x = 1 if p[a:b+1] < p[c:d+1] else 0 return x a = collections.deque(range(n)) b = collections.deque() c = collections.deque() for i in range(n//2): x = a.popleft() y = a.popleft() z = query(x,x,y,y) if z == 1: c.append(x) b.append(y) else: c.append(y) b.append(x) a = c + a while len(a) > 1: c = collections.deque() while len(a) > 1: x = a.popleft() y = a.popleft() z = query(x,x,y,y) if z == 1: c.append(x) else: c.append(y) a = a + c ans = [a[0],a[0]] a = b #print(a,b) while len(a) > 1: c = collections.deque() while len(a) > 1: x = a.popleft() y = a.popleft() z = query(x,n-1,y,n-1) if z == 0: c.append(x) else: c.append(y) a = a + c ans.extend([a[0],n-1]) #print(ans) ans = list(map(lambda x:x+1,ans)) print('!',*ans) #1 3 4 2