#936423 (PyPy3) No.2577 Simple Permutation Guess

提出ソース

結果

問題	No.2577 Simple Permutation Guess
ユーザー	👑 rin204
提出日時	2023-12-05 00:33:04
言語	PyPy3 (7.3.15)
結果	RE
実行時間	-
コード長	2,180 bytes
コンパイル時間	275 ms
コンパイル使用メモリ	81,700 KB
実行使用メモリ	94,608 KB
平均クエリ数	249.53
最終ジャッジ日時	2023-12-05 00:33:37
合計ジャッジ時間	31,874 ms
ジャッジサーバーID （参考情報）	judge14 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	69 ms 72,156 KB
testcase_01	AC	444 ms 93,940 KB
testcase_02	AC	187 ms 93,184 KB
testcase_03	AC	69 ms 78,080 KB
testcase_04	AC	230 ms 93,308 KB
testcase_05	AC	251 ms 93,176 KB
testcase_06	AC	540 ms 94,472 KB
testcase_07	AC	564 ms 94,480 KB
testcase_08	AC	567 ms 94,480 KB
testcase_09	AC	549 ms 94,484 KB
testcase_10	AC	535 ms 94,608 KB
testcase_11	AC	70 ms 78,080 KB
testcase_12	AC	62 ms 72,156 KB
testcase_13	AC	104 ms 91,236 KB
testcase_14	AC	84 ms 84,592 KB
testcase_15	AC	68 ms 78,080 KB
testcase_16	AC	64 ms 72,156 KB
testcase_17	AC	62 ms 72,156 KB
testcase_18	AC	61 ms 72,156 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	AC	63 ms 72,148 KB
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	64 ms 72,148 KB
testcase_31	AC	63 ms 72,156 KB
testcase_32	RE	-
testcase_33	AC	64 ms 72,156 KB
testcase_34	RE	-
testcase_35	AC	62 ms 72,156 KB
testcase_36	AC	62 ms 72,156 KB
testcase_37	AC	62 ms 72,148 KB
testcase_38	AC	60 ms 72,148 KB
testcase_39	AC	60 ms 72,148 KB
testcase_40	AC	64 ms 72,148 KB
testcase_41	AC	62 ms 72,148 KB
testcase_42	AC	62 ms 72,148 KB
testcase_43	RE	-
testcase_44	RE	-
testcase_45	AC	61 ms 72,148 KB
testcase_46	RE	-
testcase_47	RE	-
testcase_48	AC	62 ms 72,148 KB
testcase_49	RE	-
testcase_50	RE	-
testcase_51	AC	62 ms 72,148 KB
testcase_52	RE	-
testcase_53	RE	-
testcase_54	AC	62 ms 72,148 KB
testcase_55	RE	-
testcase_56	RE	-
testcase_57	AC	62 ms 72,148 KB
testcase_58	RE	-
testcase_59	RE	-
testcase_60	AC	61 ms 72,148 KB
testcase_61	RE	-
testcase_62	RE	-
testcase_63	RE	-
testcase_64	AC	63 ms 72,148 KB
testcase_65	AC	62 ms 72,148 KB
testcase_66	AC	63 ms 72,148 KB
testcase_67	AC	63 ms 72,148 KB
testcase_68	AC	64 ms 72,148 KB
testcase_69	AC	62 ms 72,148 KB
testcase_70	AC	62 ms 72,148 KB
testcase_71	AC	75 ms 72,148 KB
testcase_72	AC	63 ms 72,148 KB
testcase_73	AC	63 ms 72,156 KB
testcase_74	AC	95 ms 89,696 KB
testcase_75	AC	97 ms 89,696 KB
testcase_76	AC	97 ms 89,696 KB
testcase_77	AC	97 ms 89,696 KB
testcase_78	AC	97 ms 89,696 KB
testcase_79	AC	97 ms 89,696 KB
testcase_80	AC	104 ms 90,080 KB
testcase_81	AC	100 ms 90,076 KB
testcase_82	AC	100 ms 90,204 KB
testcase_83	AC	98 ms 89,948 KB
testcase_84	AC	100 ms 90,204 KB
testcase_85	AC	100 ms 90,080 KB
testcase_86	AC	102 ms 90,460 KB
testcase_87	AC	101 ms 90,460 KB
testcase_88	AC	100 ms 90,332 KB
testcase_89	AC	100 ms 90,460 KB
testcase_90	AC	99 ms 90,460 KB
testcase_91	AC	100 ms 90,332 KB
testcase_92	AC	437 ms 93,972 KB
testcase_93	AC	403 ms 93,712 KB
testcase_94	AC	389 ms 93,844 KB
testcase_95	AC	544 ms 94,412 KB
testcase_96	AC	513 ms 93,964 KB
testcase_97	AC	483 ms 93,952 KB
testcase_98	AC	469 ms 94,488 KB
testcase_99	AC	497 ms 94,488 KB
testcase_100	AC	401 ms 93,840 KB
testcase_101	AC	484 ms 93,832 KB
evil_1_rnd_1.txt	AC	970 ms 95,356 KB
evil_1_rnd_2.txt	AC	946 ms 95,360 KB
evil_2_big_1.txt	AC	1,172 ms 96,276 KB
evil_2_big_2.txt	AC	1,194 ms 96,272 KB
evil_2_big_3.txt	AC	1,174 ms 96,512 KB
evil_3_sorted_1.txt	AC	774 ms 94,832 KB
evil_4_sorted_rev_1.txt	AC	628 ms 93,816 KB
evil_4_sorted_rev_2.txt	AC	782 ms 94,584 KB
evil_400_sorted.txt	AC	1,138 ms 95,508 KB
evil_400_sorted_rev.txt	AC	1,142 ms 95,640 KB

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

ソースコード

raw source code

import random

DEBUG = 0


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())
if DEBUG:
    ans = [i for i in range(1, n + 1)]
    random.shuffle(ans)

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, 0, -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 DEBUG:
        for i in range(n):
            if P[i] < ans[i]:
                return 1
            elif P[i] > ans[i]:
                return 0
        return 1

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


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

結果

テストケース

ソースコード