結果

問題 No.2577 Simple Permutation Guess
ユーザー 👑 rin204rin204
提出日時 2023-12-05 00:24:14
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 1,853 bytes
コンパイル時間 426 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 95,024 KB
平均クエリ数 249.53
最終ジャッジ日時 2024-09-26 23:36:54
合計ジャッジ時間 33,524 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 70 ms
68,960 KB
testcase_01 AC 469 ms
93,824 KB
testcase_02 AC 210 ms
93,352 KB
testcase_03 AC 72 ms
75,744 KB
testcase_04 AC 257 ms
93,092 KB
testcase_05 AC 286 ms
93,632 KB
testcase_06 AC 571 ms
94,248 KB
testcase_07 AC 592 ms
94,508 KB
testcase_08 AC 616 ms
94,024 KB
testcase_09 AC 621 ms
95,024 KB
testcase_10 AC 571 ms
94,512 KB
testcase_11 AC 77 ms
76,512 KB
testcase_12 AC 68 ms
69,472 KB
testcase_13 AC 116 ms
90,368 KB
testcase_14 AC 97 ms
82,008 KB
testcase_15 AC 74 ms
75,104 KB
testcase_16 AC 66 ms
68,960 KB
testcase_17 AC 67 ms
68,704 KB
testcase_18 AC 66 ms
69,344 KB
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 AC 68 ms
69,592 KB
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 AC 67 ms
69,336 KB
testcase_31 AC 67 ms
69,088 KB
testcase_32 RE -
testcase_33 AC 65 ms
69,472 KB
testcase_34 RE -
testcase_35 AC 66 ms
69,856 KB
testcase_36 AC 66 ms
69,600 KB
testcase_37 AC 66 ms
69,088 KB
testcase_38 AC 65 ms
68,184 KB
testcase_39 AC 65 ms
69,288 KB
testcase_40 AC 65 ms
69,472 KB
testcase_41 AC 66 ms
68,832 KB
testcase_42 AC 65 ms
69,216 KB
testcase_43 RE -
testcase_44 RE -
testcase_45 AC 65 ms
69,216 KB
testcase_46 RE -
testcase_47 RE -
testcase_48 AC 66 ms
68,960 KB
testcase_49 RE -
testcase_50 RE -
testcase_51 AC 66 ms
68,568 KB
testcase_52 RE -
testcase_53 RE -
testcase_54 AC 65 ms
68,952 KB
testcase_55 RE -
testcase_56 RE -
testcase_57 AC 66 ms
69,208 KB
testcase_58 RE -
testcase_59 RE -
testcase_60 AC 66 ms
68,824 KB
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 AC 67 ms
68,952 KB
testcase_65 AC 67 ms
68,696 KB
testcase_66 AC 67 ms
69,592 KB
testcase_67 AC 65 ms
68,696 KB
testcase_68 AC 64 ms
69,592 KB
testcase_69 AC 65 ms
69,720 KB
testcase_70 AC 65 ms
69,464 KB
testcase_71 AC 66 ms
69,336 KB
testcase_72 AC 66 ms
68,824 KB
testcase_73 AC 66 ms
69,472 KB
testcase_74 AC 110 ms
87,648 KB
testcase_75 AC 111 ms
87,468 KB
testcase_76 AC 108 ms
87,136 KB
testcase_77 AC 110 ms
87,520 KB
testcase_78 AC 108 ms
87,520 KB
testcase_79 AC 113 ms
88,928 KB
testcase_80 AC 120 ms
91,264 KB
testcase_81 AC 117 ms
90,848 KB
testcase_82 AC 119 ms
91,616 KB
testcase_83 AC 116 ms
91,360 KB
testcase_84 AC 118 ms
90,592 KB
testcase_85 AC 121 ms
91,072 KB
testcase_86 AC 124 ms
91,232 KB
testcase_87 AC 116 ms
91,208 KB
testcase_88 AC 115 ms
90,824 KB
testcase_89 AC 117 ms
91,208 KB
testcase_90 AC 119 ms
91,240 KB
testcase_91 AC 120 ms
91,592 KB
testcase_92 AC 474 ms
93,744 KB
testcase_93 AC 445 ms
93,696 KB
testcase_94 AC 423 ms
94,096 KB
testcase_95 AC 552 ms
94,680 KB
testcase_96 AC 545 ms
93,844 KB
testcase_97 AC 521 ms
93,720 KB
testcase_98 AC 510 ms
94,108 KB
testcase_99 AC 544 ms
94,716 KB
testcase_100 AC 438 ms
93,980 KB
testcase_101 AC 516 ms
94,876 KB
evil_1_rnd_1.txt AC 964 ms
95,392 KB
evil_1_rnd_2.txt AC 957 ms
95,372 KB
evil_2_big_1.txt AC 1,180 ms
96,532 KB
evil_2_big_2.txt AC 1,186 ms
95,884 KB
evil_2_big_3.txt AC 1,198 ms
96,288 KB
evil_3_sorted_1.txt AC 718 ms
95,356 KB
evil_4_sorted_rev_1.txt AC 570 ms
94,236 KB
evil_4_sorted_rev_2.txt AC 789 ms
94,576 KB
evil_400_sorted.txt AC 1,158 ms
95,368 KB
evil_400_sorted_rev.txt AC 1,174 ms
95,272 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        if n == 0:
            self.n0 = 0
        else:
            self.n0 = 1 << (n.bit_length() - 1)

    def sum_(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def sum(self, l, r=-1):
        if r == -1:
            return self.sum_(l)
        else:
            return self.sum_(r) - self.sum_(l)

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

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

    def lower_bound(self, x):
        if x <= 0:
            return 0
        i = 0
        k = self.n0
        while k > 0:
            if i + k <= self.n and self.data[i + k] < x:
                x -= self.data[i + k]
                i += k
            k //= 2
        return i + 1


n = int(input())
L = [0] * n
R = [i for i in range(n)]


def f():
    X = [(l + r) for l, r in zip(L, R)]
    for i in range(n - 1):
        if X[i] > i:
            X[i] -= i + 1
            X[i + 1] += 1

    for i in range(n - 1, -1, -1):
        if X[i] % 2 == 1:
            X[i - 1] += i
        X[i] //= 2
    X[0] //= 2
    return X


def ask(X, q="?"):
    P = []
    bit = BIT(n)
    for i in range(n):
        bit.add(i, 1)
    for x in X[::-1]:
        p = bit.lower_bound(x + 1) - 1
        P.append(p + 1)
        bit.add(p, -1)
    print(q, *P, flush=True)

    if len(set(P)) != n:
        return -1
    if q == "?":
        return int(input())


while 1:
    mid = f()
    if mid == L:
        break

    res = ask(mid)
    if res == -1:
        exit()
    if res == 0:
        R = mid
    else:
        L = mid

res = ask(R)
if res == -1:
    exit()
if res == 1:
    ask(R, "!")
else:
    ask(L, "!")
0