結果

問題 No.3590 I Love Inversions
コンテスト
ユーザー tassei903
提出日時 2026-07-17 21:54:00
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 2,376 ms / 5,000 ms
+ 36µs
コード長 1,924 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 529 ms
コンパイル使用メモリ 96,232 KB
実行使用メモリ 90,548 KB
平均クエリ数 12103.46
最終ジャッジ日時 2026-07-17 21:54:28
合計ジャッジ時間 28,344 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 43
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
# input = lambda :sys.stdin.readline()[:-1]
ni = lambda :int(input())
na = lambda :list(map(int,input().split()))
yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")
no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")
#######################################################################

"""
1 2 3  0
1 3 2  1
2 1 3  1
2 3 1  2
3 1 2  2
3 2 1  3



"""


# Binary Indexed Tree (Fenwick Tree)
# 0-indexed
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        assert 0 <= i < self.n
        i = i+1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def set(self, i, x):
        assert 0 <= i <= self.n
        self.add(i,x-self.get(i))
    def get(self, i, j):
        return self.sum(j) - self.sum(i)
    def lower_bound(self, k):# a[0],…,a[i]>kなる最小のi
        n = self.n
        x = 0
        r = 1
        while r <= n:r <<= 1
        size = r
        while size:
            if x + size <= n and self.data[x+size] <= k:
                k-=self.data[x+size]
                x += size
            size >>= 1
        return x
    def debug(self):
        res = []
        n = self.n
        for i in range(n):
            res.append(self.get(i))
        print(*res)
    
def ask(l, r):
    print("?", l + 1, r, flush=True)
    x = ni()
    if x == -1:
        exit()
    return x
n = ni()

a = [0] + [ask(0, i + 1) for i in range(1, n)]

b = [0] + [a[i+1] - a[i] for i in range(n-1)]
bit = BIT(n)
for i in range(n):
    bit.add(i, 1)
# print(b)
ans = []
for i in range(n-1, -1, -1):
    x = bit.lower_bound(i - b[i])
    ans.append(x)
    bit.add(x, -1)
# print(ans)

print("!", *[x+1 for x in ans[::-1]], flush=True)
0