結果

問題 No.2577 Simple Permutation Guess
コンテスト
ユーザー ecottea
提出日時 2023-12-05 00:45:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 960 ms / 2,000 ms
コード長 1,940 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 93,896 KB
平均クエリ数 248.84
最終ジャッジ日時 2024-09-26 23:48:26
合計ジャッジ時間 50,760 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 105 TLE * 6
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
dump = lambda *x : print(*x, file = sys.stderr)

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.v = [0] * (n + 1)

    def __init__(self, a):
        self.n = len(a)
        self.v = [0] + a
        pow2 = 1
        while 2 * pow2 <= self.n:
            i = 2 * pow2
            while i <= self.n:
                self.v[i] += self.v[i - pow2]
                i += 2 * pow2
            pow2 *= 2

    def sum1(self, r):
        res = 0
        while r > 0:
            res += self.v[r]
            r -= r & -r
        return res
    
    def sum(self, l, r):
        return self.sum1(r) - self.sum1(l)

    def get(self, i):
        return self.sum(i, i + 1)

    def add(self, i, x):
        i += 1
        while i <= self.n:
            self.v[i] += x
            i += i & -i

    def set(self, i, x):
        self.add(i, x - self.get(i))

    def max_right(self, dsi):
        x = 0
        l = 0

        len = 2**9
        while len > 0:
            r = l + len
            if r < self.n and x + self.v[r] <= dsi:
                x += self.v[r]
                l = r
            len //= 2

        return l
        
n = int(input())

ok = 0
ng = 1
for i in range(1, n + 1):
    ng *= i

while ng - ok >= 2:
    mid = (ok + ng) // 2
    #dump(ok, ng, mid)
    
    ds = [0] * n
    mid2 = mid
    for i in range(1, n + 1):
        ds[n - i] = mid2 % i
        mid2 //= i
    #dump(ds)
    
    p = [0] * n
    ft = FenwickTree([1] * n)
    for i in range(n):
        p[i] = ft.max_right(ds[i]) + 1
        ft.add(p[i] - 1, -1)
    #dump(p)

    print("? ", end="")
    print(*p)

    ret = int(input())

    if ret == 1:
        ok = mid
    else:
        ng = mid

ds = [0] * n
for i in range(1, n + 1):
    ds[n - i] = ok % i
    ok //= i
    
p = [0] * n
ft = FenwickTree([1] * n)
for i in range(n):
    p[i] = ft.max_right(ds[i]) + 1
    ft.add(p[i] - 1, -1)

print("! ", end="")
print(*p)
0