#936407 (PyPy3) No.2577 Simple Permutation Guess

提出ソース

結果

問題	No.2577 Simple Permutation Guess
ユーザー	👑 rin204
提出日時	2023-12-05 00:24:14
言語	PyPy3 (7.3.15)
結果	RE
実行時間	-
コード長	1,853 bytes
コンパイル時間	301 ms
コンパイル使用メモリ	81,572 KB
実行使用メモリ	93,816 KB
平均クエリ数	249.53
最終ジャッジ日時	2023-12-05 00:24:46
合計ジャッジ時間	31,964 ms
ジャッジサーバーID （参考情報）	judge12 / judge13

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	65 ms 69,468 KB
testcase_01	AC	458 ms 92,924 KB
testcase_02	AC	184 ms 92,412 KB
testcase_03	AC	64 ms 75,348 KB
testcase_04	AC	262 ms 92,276 KB
testcase_05	AC	254 ms 92,380 KB
testcase_06	AC	569 ms 93,420 KB
testcase_07	AC	554 ms 93,420 KB
testcase_08	AC	571 ms 93,036 KB
testcase_09	AC	566 ms 93,036 KB
testcase_10	AC	548 ms 93,036 KB
testcase_11	AC	67 ms 75,476 KB
testcase_12	AC	62 ms 69,468 KB
testcase_13	AC	101 ms 89,196 KB
testcase_14	AC	82 ms 81,856 KB
testcase_15	AC	66 ms 75,348 KB
testcase_16	AC	67 ms 69,468 KB
testcase_17	AC	59 ms 69,468 KB
testcase_18	AC	59 ms 69,468 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	AC	59 ms 69,460 KB
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	59 ms 69,460 KB
testcase_31	AC	60 ms 69,468 KB
testcase_32	RE	-
testcase_33	AC	60 ms 69,468 KB
testcase_34	RE	-
testcase_35	AC	60 ms 69,468 KB
testcase_36	AC	60 ms 69,468 KB
testcase_37	AC	58 ms 69,460 KB
testcase_38	AC	59 ms 69,460 KB
testcase_39	AC	59 ms 69,460 KB
testcase_40	AC	60 ms 69,460 KB
testcase_41	AC	59 ms 69,460 KB
testcase_42	AC	61 ms 69,460 KB
testcase_43	RE	-
testcase_44	RE	-
testcase_45	AC	60 ms 69,460 KB
testcase_46	RE	-
testcase_47	RE	-
testcase_48	AC	60 ms 69,460 KB
testcase_49	RE	-
testcase_50	RE	-
testcase_51	AC	59 ms 69,460 KB
testcase_52	RE	-
testcase_53	RE	-
testcase_54	AC	59 ms 69,460 KB
testcase_55	RE	-
testcase_56	RE	-
testcase_57	AC	64 ms 69,460 KB
testcase_58	RE	-
testcase_59	RE	-
testcase_60	AC	60 ms 69,460 KB
testcase_61	RE	-
testcase_62	RE	-
testcase_63	RE	-
testcase_64	AC	59 ms 69,460 KB
testcase_65	AC	58 ms 69,460 KB
testcase_66	AC	60 ms 69,460 KB
testcase_67	AC	60 ms 69,460 KB
testcase_68	AC	60 ms 69,460 KB
testcase_69	AC	59 ms 69,460 KB
testcase_70	AC	58 ms 69,460 KB
testcase_71	AC	57 ms 69,460 KB
testcase_72	AC	58 ms 69,460 KB
testcase_73	AC	59 ms 69,468 KB
testcase_74	AC	94 ms 86,568 KB
testcase_75	AC	91 ms 86,572 KB
testcase_76	AC	91 ms 86,568 KB
testcase_77	AC	94 ms 86,568 KB
testcase_78	AC	93 ms 86,568 KB
testcase_79	AC	95 ms 89,192 KB
testcase_80	AC	101 ms 90,308 KB
testcase_81	AC	100 ms 90,048 KB
testcase_82	AC	100 ms 90,048 KB
testcase_83	AC	100 ms 90,056 KB
testcase_84	AC	119 ms 90,056 KB
testcase_85	AC	100 ms 90,308 KB
testcase_86	AC	102 ms 90,312 KB
testcase_87	AC	102 ms 90,312 KB
testcase_88	AC	103 ms 90,184 KB
testcase_89	AC	102 ms 90,312 KB
testcase_90	AC	99 ms 90,312 KB
testcase_91	AC	105 ms 90,184 KB
testcase_92	AC	436 ms 92,936 KB
testcase_93	AC	454 ms 92,984 KB
testcase_94	AC	422 ms 92,940 KB
testcase_95	AC	548 ms 93,300 KB
testcase_96	AC	518 ms 92,912 KB
testcase_97	AC	500 ms 92,924 KB
testcase_98	AC	496 ms 93,320 KB
testcase_99	AC	488 ms 93,816 KB
testcase_100	AC	408 ms 92,784 KB
testcase_101	AC	512 ms 93,444 KB
evil_1_rnd_1.txt	AC	979 ms 94,468 KB
evil_1_rnd_2.txt	AC	953 ms 94,588 KB
evil_2_big_1.txt	AC	1,231 ms 95,212 KB
evil_2_big_2.txt	AC	1,261 ms 95,212 KB
evil_2_big_3.txt	AC	1,150 ms 95,112 KB
evil_3_sorted_1.txt	AC	710 ms 93,792 KB
evil_4_sorted_rev_1.txt	AC	546 ms 93,004 KB
evil_4_sorted_rev_2.txt	AC	751 ms 93,752 KB
evil_400_sorted.txt	AC	1,120 ms 94,572 KB
evil_400_sorted_rev.txt	AC	1,178 ms 94,956 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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, "!")

yukicoder

結果

テストケース

ソースコード