結果

問題 No.1743 Permutation Code
ユーザー tnodino
提出日時 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 2 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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