結果

問題 No.1743 Permutation Code
ユーザー tnodinotnodino
提出日時 2022-08-18 21:53:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,167 bytes
コンパイル時間 698 ms
コンパイル使用メモリ 82,012 KB
実行使用メモリ 179,432 KB
最終ジャッジ日時 2024-10-06 17:09:28
合計ジャッジ時間 17,802 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

def popcount(x):
    return bin(x).count('1')

C = list(map(int,input()))
B = len(C)
x = 0
N = 0
while x < B:
    N += 1
    x += N.bit_length()
M = N.bit_length()
DP = [[set() for _ in range(B)] for _ in range(B)]
for i in range(B):
    x = 0
    for j in range(M):
        if i + j == B:
            break
        x <<= 1
        x += C[i+j]
        if x == 0 or x > N:
            break
        DP[i][i+j].add((1<<(x-1), -1, -1, -1))
for d in range(1,B):
    for i in range(B-d):
        j = i + d
        for k in range(i,j):
            for a,ai,ak,aj in DP[i][k]:
                for b,bi,bk,bj in DP[k+1][j]:
                    x = a | b
                    if popcount(a) + popcount(b) == popcount(x):
                        DP[i][j].add((x, i, k, j))

def dfs(l, r):
    for a,ai,ak,aj in DP[l][r]:
        if ai == -1:
            for b in range(N):
                if a & (1 << b):
                    idx[b] = (l, b+1)
                    return
        else:
            dfs(ai, ak)
            dfs(ak+1, aj)
            return

idx = [(-1, -1) for _ in range(N)]
dfs(0, B-1)
idx.sort()
ans = []
for i in range(N):
    ans.append(idx[i][1])
print(*ans)
0