#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
コンパイル時間	328 ms
コンパイル使用メモリ	82,176 KB
実行使用メモリ	95,548 KB
平均クエリ数	249.53
最終ジャッジ日時	2024-09-26 23:43:21
合計ジャッジ時間	30,306 ms
ジャッジサーバーID （参考情報）	judge2 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	66 ms 71,392 KB
testcase_01	AC	436 ms 94,856 KB
testcase_02	AC	195 ms 93,988 KB
testcase_03	AC	73 ms 77,536 KB
testcase_04	AC	246 ms 94,456 KB
testcase_05	AC	263 ms 93,848 KB
testcase_06	AC	510 ms 95,268 KB
testcase_07	AC	510 ms 95,288 KB
testcase_08	AC	522 ms 95,280 KB
testcase_09	AC	519 ms 95,412 KB
testcase_10	AC	509 ms 95,404 KB
testcase_11	AC	76 ms 77,920 KB
testcase_12	AC	66 ms 71,512 KB
testcase_13	AC	114 ms 91,872 KB
testcase_14	AC	93 ms 84,064 KB
testcase_15	AC	71 ms 77,920 KB
testcase_16	AC	64 ms 71,496 KB
testcase_17	AC	63 ms 71,008 KB
testcase_18	AC	66 ms 71,264 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	AC	66 ms 71,384 KB
testcase_25	RE	-
testcase_26	RE	-
testcase_27	RE	-
testcase_28	RE	-
testcase_29	RE	-
testcase_30	AC	64 ms 71,000 KB
testcase_31	AC	65 ms 71,136 KB
testcase_32	RE	-
testcase_33	AC	66 ms 71,264 KB
testcase_34	RE	-
testcase_35	AC	67 ms 71,136 KB
testcase_36	AC	65 ms 71,640 KB
testcase_37	AC	62 ms 71,008 KB
testcase_38	AC	63 ms 71,128 KB
testcase_39	AC	63 ms 70,864 KB
testcase_40	AC	65 ms 71,392 KB
testcase_41	AC	66 ms 71,136 KB
testcase_42	AC	65 ms 71,264 KB
testcase_43	RE	-
testcase_44	RE	-
testcase_45	AC	65 ms 71,136 KB
testcase_46	RE	-
testcase_47	RE	-
testcase_48	AC	66 ms 70,752 KB
testcase_49	RE	-
testcase_50	RE	-
testcase_51	AC	65 ms 70,616 KB
testcase_52	RE	-
testcase_53	RE	-
testcase_54	AC	65 ms 71,000 KB
testcase_55	RE	-
testcase_56	RE	-
testcase_57	AC	64 ms 71,128 KB
testcase_58	RE	-
testcase_59	RE	-
testcase_60	AC	64 ms 71,384 KB
testcase_61	RE	-
testcase_62	RE	-
testcase_63	RE	-
testcase_64	AC	63 ms 71,128 KB
testcase_65	AC	65 ms 71,128 KB
testcase_66	AC	66 ms 71,384 KB
testcase_67	AC	64 ms 70,744 KB
testcase_68	AC	64 ms 71,256 KB
testcase_69	AC	65 ms 71,128 KB
testcase_70	AC	67 ms 71,256 KB
testcase_71	AC	67 ms 71,512 KB
testcase_72	AC	65 ms 70,744 KB
testcase_73	AC	64 ms 71,392 KB
testcase_74	AC	106 ms 90,336 KB
testcase_75	AC	109 ms 90,592 KB
testcase_76	AC	107 ms 90,080 KB
testcase_77	AC	107 ms 90,464 KB
testcase_78	AC	108 ms 89,952 KB
testcase_79	AC	109 ms 89,824 KB
testcase_80	AC	111 ms 90,824 KB
testcase_81	AC	111 ms 90,592 KB
testcase_82	AC	112 ms 90,976 KB
testcase_83	AC	109 ms 90,976 KB
testcase_84	AC	109 ms 91,104 KB
testcase_85	AC	110 ms 91,104 KB
testcase_86	AC	114 ms 91,104 KB
testcase_87	AC	111 ms 90,952 KB
testcase_88	AC	111 ms 91,464 KB
testcase_89	AC	111 ms 90,952 KB
testcase_90	AC	112 ms 91,328 KB
testcase_91	AC	109 ms 91,080 KB
testcase_92	AC	443 ms 94,860 KB
testcase_93	AC	397 ms 94,612 KB
testcase_94	AC	385 ms 94,108 KB
testcase_95	AC	500 ms 95,548 KB
testcase_96	AC	501 ms 94,600 KB
testcase_97	AC	510 ms 95,104 KB
testcase_98	AC	468 ms 94,836 KB
testcase_99	AC	495 ms 95,524 KB
testcase_100	AC	408 ms 94,864 KB
testcase_101	AC	468 ms 94,596 KB
evil_1_rnd_1.txt	AC	871 ms 95,868 KB
evil_1_rnd_2.txt	AC	886 ms 96,248 KB
evil_2_big_1.txt	AC	1,086 ms 96,660 KB
evil_2_big_2.txt	AC	1,076 ms 97,508 KB
evil_2_big_3.txt	AC	1,087 ms 96,896 KB
evil_3_sorted_1.txt	AC	655 ms 95,740 KB
evil_4_sorted_rev_1.txt	AC	529 ms 94,852 KB
evil_4_sorted_rev_2.txt	AC	702 ms 95,492 KB
evil_400_sorted.txt	AC	1,026 ms 96,800 KB
evil_400_sorted_rev.txt	AC	1,066 ms 96,164 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

結果

テストケース

ソースコード