#880219 (Python3) No.1900 Don't be Powers of 2

提出ソース

結果

問題	No.1900 Don't be Powers of 2
ユーザー	vwxyz
提出日時	2023-06-13 06:28:21
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	TLE
実行時間	-
コード長	5,606 bytes
コンパイル時間	617 ms
コンパイル使用メモリ	13,312 KB
実行使用メモリ	270,364 KB
最終ジャッジ日時	2024-06-12 06:26:09
合計ジャッジ時間	12,483 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	50 ms 19,868 KB
testcase_01	AC	49 ms 12,800 KB
testcase_02	AC	52 ms 13,056 KB
testcase_03	AC	513 ms 13,952 KB
testcase_04	AC	498 ms 13,952 KB
testcase_05	AC	533 ms 13,824 KB
testcase_06	AC	512 ms 13,952 KB
testcase_07	AC	507 ms 13,952 KB
testcase_08	AC	262 ms 15,232 KB
testcase_09	AC	148 ms 14,080 KB
testcase_10	AC	77 ms 13,440 KB
testcase_11	AC	102 ms 13,440 KB
testcase_12	AC	365 ms 16,128 KB
testcase_13	AC	58 ms 13,184 KB
testcase_14	AC	349 ms 13,696 KB
testcase_15	AC	58 ms 12,928 KB
testcase_16	AC	60 ms 12,928 KB
testcase_17	AC	469 ms 13,696 KB
testcase_18	AC	404 ms 13,824 KB
testcase_19	AC	498 ms 13,824 KB
testcase_20	AC	359 ms 13,824 KB
testcase_21	AC	365 ms 13,696 KB
testcase_22	AC	341 ms 13,568 KB
testcase_23	AC	64 ms 13,952 KB
testcase_24	AC	65 ms 13,952 KB
testcase_25	AC	535 ms 13,952 KB
testcase_26	TLE	-
testcase_27	--	-
testcase_28	--	-
testcase_29	--	-
testcase_30	--	-
testcase_31	--	-
testcase_32	--	-
testcase_33	--	-
testcase_34	--	-
testcase_35	--	-
testcase_36	--	-
testcase_37	--	-
testcase_38	--	-
testcase_39	--	-
testcase_40	--	-
testcase_41	--	-
testcase_42	--	-
testcase_43	--	-
testcase_44	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

import bisect
import copy
import decimal
import fractions
import heapq
import itertools
import math
import random
import sys
import time
from collections import Counter,deque,defaultdict
from functools import lru_cache,reduce
from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max
def _heappush_max(heap,item):
    heap.append(item)
    heapq._siftdown_max(heap, 0, len(heap)-1)
def _heappushpop_max(heap, item):
    if heap and item < heap[0]:
        item, heap[0] = heap[0], item
        heapq._siftup_max(heap, 0)
    return item
from math import gcd as GCD
read=sys.stdin.read
readline=sys.stdin.readline
readlines=sys.stdin.readlines
write=sys.stdout.write
from typing import NamedTuple, Optional, List, cast

class MFGraph:
    class Edge(NamedTuple):
        src: int
        dst: int
        cap: int
        flow: int

    class _Edge:
        def __init__(self, dst: int, cap: int) -> None:
            self.dst = dst
            self.cap = cap
            self.rev: Optional[MFGraph._Edge] = None

    def __init__(self, n: int) -> None:
        self._n = n
        self._g: List[List[MFGraph._Edge]] = [[] for _ in range(n)]
        self._edges: List[MFGraph._Edge] = []

    def add_edge(self, src: int, dst: int, cap: int) -> int:
        assert 0 <= src < self._n
        assert 0 <= dst < self._n
        assert 0 <= cap
        m = len(self._edges)
        e = MFGraph._Edge(dst, cap)
        re = MFGraph._Edge(src, 0)
        e.rev = re
        re.rev = e
        self._g[src].append(e)
        self._g[dst].append(re)
        self._edges.append(e)
        return m

    def get_edge(self, i: int) -> Edge:
        assert 0 <= i < len(self._edges)
        e = self._edges[i]
        re = cast(MFGraph._Edge, e.rev)
        return MFGraph.Edge(
            re.dst,
            e.dst,
            e.cap + re.cap,
            re.cap
        )

    def edges(self) -> List[Edge]:
        return [self.get_edge(i) for i in range(len(self._edges))]

    def change_edge(self, i: int, new_cap: int, new_flow: int) -> None:
        assert 0 <= i < len(self._edges)
        assert 0 <= new_flow <= new_cap
        e = self._edges[i]
        e.cap = new_cap - new_flow
        assert e.rev is not None
        e.rev.cap = new_flow

    def flow(self, s: int, t: int, flow_limit: Optional[int] = None) -> int:
        assert 0 <= s < self._n
        assert 0 <= t < self._n
        assert s != t
        if flow_limit is None:
            flow_limit = cast(int, sum(e.cap for e in self._g[s]))

        current_edge = [0] * self._n
        level = [0] * self._n

        def fill(arr: List[int], value: int) -> None:
            for i in range(len(arr)):
                arr[i] = value

        def bfs() -> bool:
            fill(level, self._n)
            queue = []
            q_front = 0
            queue.append(s)
            level[s] = 0
            while q_front < len(queue):
                v = queue[q_front]
                q_front += 1
                next_level = level[v] + 1
                for e in self._g[v]:
                    if e.cap == 0 or level[e.dst] <= next_level:
                        continue
                    level[e.dst] = next_level
                    if e.dst == t:
                        return True
                    queue.append(e.dst)
            return False

        def dfs(lim: int) -> int:
            stack = []
            edge_stack: List[MFGraph._Edge] = []
            stack.append(t)
            while stack:
                v = stack[-1]
                if v == s:
                    flow = min(lim, min(e.cap for e in edge_stack))
                    for e in edge_stack:
                        e.cap -= flow
                        assert e.rev is not None
                        e.rev.cap += flow
                    return flow
                next_level = level[v] - 1
                while current_edge[v] < len(self._g[v]):
                    e = self._g[v][current_edge[v]]
                    re = cast(MFGraph._Edge, e.rev)
                    if level[e.dst] != next_level or re.cap == 0:
                        current_edge[v] += 1
                        continue
                    stack.append(e.dst)
                    edge_stack.append(re)
                    break
                else:
                    stack.pop()
                    if edge_stack:
                        edge_stack.pop()
                    level[v] = self._n
            return 0

        flow = 0
        while flow < flow_limit:
            if not bfs():
                break
            fill(current_edge, 0)
            while flow < flow_limit:
                f = dfs(flow_limit - flow)
                flow += f
                if f == 0:
                    break
        return flow

    def min_cut(self, s: int) -> List[bool]:
        visited = [False] * self._n
        stack = [s]
        visited[s] = True
        while stack:
            v = stack.pop()
            for e in self._g[v]:
                if e.cap > 0 and not visited[e.dst]:
                    visited[e.dst] = True
                    stack.append(e.dst)
        return visited

N=int(readline())
A=list(map(int,readline().split()))
pow2={1<<i for i in range(30)}
cnt=[sum(1 for b in range(30) if a&1<<b) for a in A]
MFG=MFGraph(N+2)
s=0
t=N+1
for i in range(N):
    if cnt[i]%2==0:
        MFG.add_edge(s,i+1,1)
    else:
        MFG.add_edge(i+1,t,1)
    if cnt[i]%2==0:
        for j in range(N):
            if cnt[j]%2 and A[i]^A[j] in pow2:
                MFG.add_edge(i+1,j+1,1)
flow=MFG.flow(s,t)
ans=N-flow
print(ans)

yukicoder

結果

テストケース

ソースコード