結果
問題 | No.1900 Don't be Powers of 2 |
ユーザー |
![]() |
提出日時 | 2022-04-08 21:37:01 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 744 ms / 2,000 ms |
コード長 | 1,340 bytes |
コンパイル時間 | 220 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 333,364 KB |
最終ジャッジ日時 | 2024-11-28 12:14:24 |
合計ジャッジ時間 | 8,430 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 42 |
ソースコード
from collections import dequeN=int(input())A=sorted(map(int,input().split()))N=len(A)V=N+2G=[[] for i in range(V)]L=[0]*VI=[0]*VINF=10**15def ae(fr,to,ca):global GG[fr].append([to,ca,len(G[to]),0])G[to].append([fr,0,len(G[fr])-1,0])def bfs(s):global INF,L,V,GL=[-1]*VQ=deque()L[s]=0Q.append(s)while(len(Q)):x=Q.popleft()for i in range(len(G[x])):if G[x][i][1]>0 and L[G[x][i][0]]<0:L[G[x][i][0]]=L[x]+1Q.append(G[x][i][0])def dfs(v,t,f):global I,G,Vif v==t:return ffor i in range(I[v],len(G[v])):if G[v][i][1]>0 and L[v]<L[G[v][i][0]]:d=dfs(G[v][i][0],t,min(f,G[v][i][1]))if d>0:G[v][i][1]-=dG[v][i][3]+=dG[G[v][i][0]][G[v][i][2]][1]+=dG[G[v][i][0]][G[v][i][2]][3]-=dreturn dI[v]+=1return 0def mf(s,t):global L,I,INF,Vfl=0while(True):bfs(s)if L[t]<0:breakI=[0]*Vf=0while(True):f=dfs(s,t,INF)if f<=0:breakfl+=freturn flD=dict()BB=set([1<<i for i in range(31)])for i in range(N):f=0if bin(A[i]).count('1')&1:ae(i,V-1,1)f=1else:ae(V-2,i,1)D[A[i]]=ifor j in range(i):if A[i]^A[j] in BB:if f:ae(j,i,1)else:ae(i,j,1)print(N-mf(V-2,V-1))