#880218 (PyPy3) No.1900 Don't be Powers of 2

提出ソース

結果

問題	No.1900 Don't be Powers of 2
ユーザー	vwxyz
提出日時	2023-06-13 06:25:08
言語	PyPy3 (7.3.15)
結果	TLE
実行時間	-
コード長	5,481 bytes
コンパイル時間	846 ms
コンパイル使用メモリ	82,004 KB
実行使用メモリ	575,364 KB
最終ジャッジ日時	2024-06-12 06:22:48
合計ジャッジ時間	22,638 ms
ジャッジサーバーID （参考情報）	judge3 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	163 ms 89,752 KB
testcase_01	AC	163 ms 89,344 KB
testcase_02	AC	156 ms 89,216 KB
testcase_03	AC	269 ms 90,932 KB
testcase_04	AC	272 ms 90,624 KB
testcase_05	AC	273 ms 90,624 KB
testcase_06	AC	272 ms 90,696 KB
testcase_07	AC	276 ms 90,752 KB
testcase_08	AC	270 ms 95,764 KB
testcase_09	AC	241 ms 93,568 KB
testcase_10	AC	210 ms 92,288 KB
testcase_11	AC	222 ms 92,856 KB
testcase_12	AC	307 ms 97,620 KB
testcase_13	AC	169 ms 90,240 KB
testcase_14	AC	235 ms 90,872 KB
testcase_15	AC	167 ms 90,044 KB
testcase_16	AC	168 ms 90,496 KB
testcase_17	AC	254 ms 90,912 KB
testcase_18	AC	243 ms 90,892 KB
testcase_19	AC	266 ms 90,508 KB
testcase_20	AC	241 ms 90,752 KB
testcase_21	AC	234 ms 90,752 KB
testcase_22	AC	231 ms 90,752 KB
testcase_23	AC	256 ms 90,368 KB
testcase_24	AC	267 ms 90,240 KB
testcase_25	AC	278 ms 90,240 KB
testcase_26	TLE	-
testcase_27	AC	544 ms 151,956 KB
testcase_28	AC	332 ms 98,564 KB
testcase_29	AC	313 ms 98,816 KB
testcase_30	AC	203 ms 92,492 KB
testcase_31	AC	153 ms 89,472 KB
testcase_32	AC	161 ms 89,344 KB
testcase_33	TLE	-
testcase_34	TLE	-
testcase_35	MLE	-
testcase_36	AC	1,834 ms 448,088 KB
testcase_37	AC	335 ms 98,924 KB
testcase_38	AC	545 ms 196,656 KB
testcase_39	AC	363 ms 137,228 KB
testcase_40	AC	318 ms 94,612 KB
testcase_41	AC	366 ms 100,004 KB
testcase_42	AC	156 ms 89,316 KB
testcase_43	AC	154 ms 89,440 KB
testcase_44	AC	153 ms 89,364 KB

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

ソースコード

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)}
MFG=MFGraph(2*N+2)
s=0
t=2*N+1
for i in range(N):
    MFG.add_edge(s,i+1,1)
    MFG.add_edge(i+N+1,t,1)
    for j in range(N):
        if A[i]^A[j] in pow2:
            MFG.add_edge(i+1,j+N+1,1)
flow=MFG.flow(s,t)
ans=N-flow//2
print(ans)

yukicoder

結果

テストケース

ソースコード