結果
| 問題 | No.1900 Don't be Powers of 2 |
| ユーザー |
 Shirotsume
|
| 提出日時 | 2022-02-15 00:10:29 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,329 ms / 2,000 ms |
| コード長 | 7,462 bytes |
| コンパイル時間 | 282 ms |
| コンパイル使用メモリ | 87,076 KB |
| 実行使用メモリ | 383,680 KB |
| 最終ジャッジ日時 | 2023-09-25 14:43:03 |
| 合計ジャッジ時間 | 12,959 ms |
|
ジャッジサーバーID （参考情報） |
judge14 / judge15 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 72 ms
71,376 KB |
| testcase_01 | AC | 71 ms
71,312 KB |
| testcase_02 | AC | 72 ms
71,460 KB |
| testcase_03 | AC | 121 ms
78,668 KB |
| testcase_04 | AC | 119 ms
78,716 KB |
| testcase_05 | AC | 120 ms
78,812 KB |
| testcase_06 | AC | 116 ms
78,748 KB |
| testcase_07 | AC | 117 ms
78,720 KB |
| testcase_08 | AC | 136 ms
80,872 KB |
| testcase_09 | AC | 124 ms
78,664 KB |
| testcase_10 | AC | 101 ms
77,572 KB |
| testcase_11 | AC | 113 ms
77,944 KB |
| testcase_12 | AC | 141 ms
81,012 KB |
| testcase_13 | AC | 79 ms
76,432 KB |
| testcase_14 | AC | 110 ms
78,172 KB |
| testcase_15 | AC | 77 ms
76,184 KB |
| testcase_16 | AC | 77 ms
75,888 KB |
| testcase_17 | AC | 116 ms
78,712 KB |
| testcase_18 | AC | 116 ms
78,584 KB |
| testcase_19 | AC | 117 ms
78,948 KB |
| testcase_20 | AC | 118 ms
78,768 KB |
| testcase_21 | AC | 110 ms
78,132 KB |
| testcase_22 | AC | 107 ms
78,168 KB |
| testcase_23 | AC | 92 ms
77,176 KB |
| testcase_24 | AC | 92 ms
77,220 KB |
| testcase_25 | AC | 103 ms
77,192 KB |
| testcase_26 | AC | 1,329 ms
383,024 KB |
| testcase_27 | AC | 287 ms
112,744 KB |
| testcase_28 | AC | 151 ms
80,420 KB |
| testcase_29 | AC | 149 ms
80,276 KB |
| testcase_30 | AC | 109 ms
78,152 KB |
| testcase_31 | AC | 72 ms
71,328 KB |
| testcase_32 | AC | 72 ms
71,428 KB |
| testcase_33 | AC | 1,217 ms
383,588 KB |
| testcase_34 | AC | 1,208 ms
383,540 KB |
| testcase_35 | AC | 1,226 ms
383,680 KB |
| testcase_36 | AC | 894 ms
313,760 KB |
| testcase_37 | AC | 154 ms
80,008 KB |
| testcase_38 | AC | 281 ms
136,316 KB |
| testcase_39 | AC | 165 ms
101,896 KB |
| testcase_40 | AC | 144 ms
79,836 KB |
| testcase_41 | AC | 181 ms
82,988 KB |
| testcase_42 | AC | 72 ms
71,564 KB |
| testcase_43 | AC | 72 ms
71,428 KB |
| testcase_44 | AC | 71 ms
71,376 KB |
ソースコード
class maxflow:
"""It solves maximum flow problem.
"""
def __init__(self, n):
"""It creates a graph of n vertices and 0 edges.
Constraints
-----------
> 0 <= n <= 10 ** 8
Complexity
----------
> O(n)
"""
self.n = n
self.g = [[] for _ in range(self.n)]
self.pos = []
def add_edge(self, from_, to, capacity):
cap=capacity
"""It adds an edge oriented from the vertex `from_` to the vertex `to`
with the capacity `cap` and the flow amount 0.
It returns an integer k such that this is the k-th edge that is added.
Constraints
-----------
> 0 <= from_, to < n
> 0 <= cap
Complexity
----------
> O(1) amortized
"""
# assert 0 <= from_ < self.n
# assert 0 <= to < self.n
# assert 0 <= cap
m = len(self.pos)
self.pos.append((from_, len(self.g[from_])))
self.g[from_].append(self.__class__._edge(to, len(self.g[to]), cap))
self.g[to].append(self.__class__._edge(
from_, len(self.g[from_]) - 1, 0))
return m
class edge:
def __init__(self, from_, to, cap, flow):
self.from_ = from_
self.to = to
self.cap = cap
self.flow = flow
def get_edge(self, i):
"""It returns the current internal state of the edges.
The edges are ordered in the same order as added by add_edge.
Complexity
----------
> O(1)
"""
# assert 0 <= i < len(self.pos)
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
return self.__class__.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap)
def edges(self):
"""It returns the current internal state of the edges.
The edges are ordered in the same order as added by add_edge.
Complexity
----------
> O(m), where m is the number of added edges.
"""
result = []
for i in range(len(self.pos)):
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
result.append(self.__class__.edge(
self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap))
return result
def change_edge(self, i, new_cap, new_flow):
"""It changes the capacity and the flow amount of the ii-th edge to new_cap and new_flow, respectively. It doesn't change the capacity or the flow amount of other edges. See Appendix for further details.
Constraints
-----------
> 0 <= newflow <= newcap
Complexity
----------
> O(1)
"""
# assert 0 <= i < len(self.pos)
# assert 0 <= new_flow <= new_cap
_e = self.g[self.pos[i][0]][self.pos[i][1]]
_re = self.g[_e.to][_e.rev]
_e.cap = new_cap - new_flow
_re.cap = new_flow
def _bfs(self, s, t):
self.level = [-1] * self.n
self.level[s] = 0
q = [s]
while q:
nq = []
for v in q:
for e in self.g[v]:
if e.cap and self.level[e.to] == -1:
self.level[e.to] = self.level[v] + 1
if e.to == t:
return True
nq.append(e.to)
q = nq
return False
def _dfs(self, s, t, up):
st = [t]
while st:
v = st[-1]
if v == s:
st.pop()
flow = up
for w in st:
e = self.g[w][self.it[w]]
flow = min(flow, self.g[e.to][e.rev].cap)
for w in st:
e = self.g[w][self.it[w]]
e.cap += flow
self.g[e.to][e.rev].cap -= flow
return flow
while self.it[v] < len(self.g[v]):
e = self.g[v][self.it[v]]
w = e.to
cap = self.g[e.to][e.rev].cap
if cap and self.level[v] > self.level[w]:
st.append(w)
break
self.it[v] += 1
else:
st.pop()
self.level[v] = self.n
return 0
def flow(self, s, t, flow_limit=float('inf')):
"""It augments the flow from s to t as much as possible.
It returns the amount of the flow augmented.
You may call it multiple times.
See Appendix in the document of AC Library for further details.
Constraints
-----------
> s != t
Complexity
----------
> O(min(n^(2/3)m, m^(3/2))) (if all the capacities are 1) or
> O(n^2 m) (general),
where m is the number of added edges.
"""
# assert 0 <= s < self.n
# assert 0 <= t < self.n
# assert s != t
flow = 0
while flow < flow_limit and self._bfs(s, t):
self.it = [0] * self.n
while flow < flow_limit:
f = self._dfs(s, t, flow_limit - flow)
if not f:
break
flow += f
return flow
def min_cut(self, s):
"""It returns a vector of length n,
such that the i-th element is true if and only if there is a directed path from s to i in the residual network.
The returned vector corresponds to a s−t minimum cut after calling flow(s, t) exactly once without flow_limit.
See Appendix in the document of AC Library for further details.
Complexity
----------
> O(n + m), where m is the number of added edges.
"""
visited = [False] * self.n
q = [s]
while q:
nq = []
for p in q:
visited[p] = True
for e in self.g[p]:
if e.cap and not visited[e.to]:
nq.append(e.to)
q = nq
return visited
class _edge:
def __init__(self, to, rev, cap):
self.to = to
self.rev = rev
self.cap = cap
#https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
def Popcount(x):
'''xの立っているビット数をカウントする関数
(xは64bit整数)'''
# 2bitごとの組に分け、立っているビット数を2bitで表現する
x = x - ((x >> 1) & 0x5555555555555555)
# 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
x = x + (x >> 8) # 16bitごと
x = x + (x >> 16) # 32bitごと
x = x + (x >> 32) # 64bitごと = 全部の合計
return x & 0x0000007f
N = int(input())
A = list(map(int,input().split()))
even = []
odd = []
G = maxflow(N + 2)
for i in range(N):
if Popcount(A[i]) % 2:
odd.append(A[i])
else:
even.append(A[i])
n = len(odd)
m = len(even)
for i in range(n):
G.add_edge(0, i + 1, 1)
for i in range(m):
G.add_edge(n + i + 1, N + 1, 1)
for i in range(n):
for j in range(m):
if Popcount(odd[i] ^ even[j]) == 1:
G.add_edge(i + 1, n + j + 1, 1)
f = G.flow(0, N + 1)
print(N - f)