結果
問題 | No.1743 Permutation Code |
ユーザー |
![]() |
提出日時 | 2022-04-21 19:10:43 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,875 bytes |
コンパイル時間 | 228 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 249,984 KB |
最終ジャッジ日時 | 2024-06-22 22:17:47 |
合計ジャッジ時間 | 19,780 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 7 TLE * 1 -- * 22 |
ソースコード
from sys import setrecursionlimit setrecursionlimit(10**6) from heapq import heappop, heappush def operator1(C): M = len(C) cnt = 0 S = 0 for b in range(1,1<<16): cnt += len(bin(b)) - 2 if cnt == M: return b, M, len(bin(b)) - 2 def operator2(C, N, M, B): G = [[] for _ in range(M+1)] for i in range(M): for b in range(1,B+1): if i + b - 1 >= M: break if i + b < M and C[i+b] == '0': continue c = int(C[i:i+b], 2) if c == 0 or c > N: break G[i].append((i+b, 1<<(B-b))) return G def operator3(N, B): S = 0 for i in range(1,N+1): S += 1 << (B - (len(bin(i)) - 2)) return S def dfs(x, y): global Flg, ans, Num, Cnt if x == len(Cnt[y]): x = 0 y -= 1 if y == -1: Answer() C = Cnt[y][x] B = len(bin(C)) - 2 for i in Num[C]: Flg2 = 1 for b in range(B): if Flg[i+b]: Flg2 = 0 break if Flg2: ans[C] = i for b in range(B): Flg[i+b] = 1 dfs(x+1, y) for b in range(B): Flg[i+b] = 0 def Answer(): global ans for i in range(N+1): ans[i] = [ans[i], i] ans = ans[1:] ans.sort() for i in range(N): ans[i] = ans[i][1] print(*ans) exit() C = input() N,M,B = operator1(C) G = operator2(C, N, M, B) S = operator3(N, B) heap = [] heappush(heap, (0, 0, [])) while heap: H,pos,L = heappop(heap) if pos == M: print(*L) break for nxt,cost in G[pos]: c = cost if int(C[pos:nxt], 2) in L: c += S if H + c > S: continue heappush(heap, (H + c, nxt, L + [int(C[pos:nxt], 2)]))