結果
問題 | No.332 数列をプレゼントに |
ユーザー |
![]() |
提出日時 | 2023-12-01 05:02:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 257 ms / 2,000 ms |
コード長 | 1,865 bytes |
コンパイル時間 | 851 ms |
コンパイル使用メモリ | 81,904 KB |
実行使用メモリ | 76,988 KB |
最終ジャッジ日時 | 2024-09-26 15:09:06 |
合計ジャッジ時間 | 5,610 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 42 |
ソースコード
import sysreadline=sys.stdin.readlinedef Hirschberg_Algorithm(N,lst,S,bit_set=False):partial_sum=[0]*(N+1)partial_sum[0]=0partial_sum[N]=Sstack=[(0,N)]while stack:l,r=stack.pop()mid=(l+r)//2s=partial_sum[r]-partial_sum[l]if bit_set:dpL=Bit_Set(1,element_range=s+1)else:dpL=1for i in range(l,mid):dpL|=dpL<<lst[i]if not bit_set:dpL&=(1<<s+1)-1if bit_set:dpR=Bit_Set(1<<s,element_range=s+1)else:dpR=1<<sfor i in range(mid,r):dpR|=dpR>>lst[i]dp=dpL&dpRif bit_set and not dp.bit_set or not bit_set and dp==0:return Nonepartial_sum[mid]=partial_sum[l]+(dp.Find_First() if bit_set else (dp&-dp).bit_length()-1)if mid-l>=2:stack.append((l,mid))if r-mid>=2:stack.append((mid,r))return partial_sumN,X=map(int,readline().split())A=list(map(int,readline().split()))M=10**5idx0=[]idx1=[]s1=0for i in range(N):if A[i]>=M:idx0.append(i)else:idx1.append(i)s1+=A[i]le0=len(idx0)le1=len(idx1)dp=1for i in range(1,le1+1):dp|=dp<<A[idx1[i-1]]for bit in range(1<<le0):s=sum(A[idx0[i]] for i in range(le0) if bit&1<<i)if s1>=X-s>=0 and dp&1<<X-s:ans_lst=[None]*Nfor i in range(le0):if bit&1<<i:ans_lst[idx0[i]]="o"else:ans_lst[idx0[i]]="x"cumsum_A=Hirschberg_Algorithm(le1,[A[i] for i in idx1],X-s)for i in range(le1):if cumsum_A[i]<cumsum_A[i+1]:ans_lst[idx1[i]]="o"else:ans_lst[idx1[i]]="x"print(*ans_lst,sep="")breakelse:print("No")