結果

問題 No.1900 Don't be Powers of 2
ユーザー ShirotsumeShirotsume
提出日時 2022-03-25 02:02:59
言語 Java21
(openjdk 21)
結果
AC  
実行時間 939 ms / 2,000 ms
コード長 6,974 bytes
コンパイル時間 3,301 ms
コンパイル使用メモリ 92,012 KB
実行使用メモリ 193,832 KB
最終ジャッジ日時 2024-05-06 00:49:19
合計ジャッジ時間 17,024 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 118 ms
41,336 KB
testcase_01 AC 112 ms
41,192 KB
testcase_02 AC 102 ms
40,280 KB
testcase_03 AC 245 ms
44,740 KB
testcase_04 AC 247 ms
45,944 KB
testcase_05 AC 257 ms
45,048 KB
testcase_06 AC 233 ms
45,100 KB
testcase_07 AC 228 ms
44,612 KB
testcase_08 AC 219 ms
45,200 KB
testcase_09 AC 214 ms
43,764 KB
testcase_10 AC 162 ms
42,084 KB
testcase_11 AC 213 ms
43,312 KB
testcase_12 AC 243 ms
46,096 KB
testcase_13 AC 138 ms
41,460 KB
testcase_14 AC 232 ms
44,220 KB
testcase_15 AC 140 ms
41,680 KB
testcase_16 AC 134 ms
41,732 KB
testcase_17 AC 251 ms
44,672 KB
testcase_18 AC 233 ms
44,268 KB
testcase_19 AC 228 ms
45,148 KB
testcase_20 AC 233 ms
44,640 KB
testcase_21 AC 227 ms
44,064 KB
testcase_22 AC 218 ms
44,196 KB
testcase_23 AC 190 ms
44,352 KB
testcase_24 AC 187 ms
44,860 KB
testcase_25 AC 252 ms
44,260 KB
testcase_26 AC 897 ms
193,244 KB
testcase_27 AC 364 ms
57,864 KB
testcase_28 AC 262 ms
48,956 KB
testcase_29 AC 261 ms
49,120 KB
testcase_30 AC 157 ms
42,400 KB
testcase_31 AC 100 ms
40,236 KB
testcase_32 AC 107 ms
40,504 KB
testcase_33 AC 931 ms
193,596 KB
testcase_34 AC 910 ms
193,832 KB
testcase_35 AC 939 ms
193,352 KB
testcase_36 AC 670 ms
157,704 KB
testcase_37 AC 260 ms
48,252 KB
testcase_38 AC 429 ms
75,916 KB
testcase_39 AC 269 ms
54,432 KB
testcase_40 AC 258 ms
45,996 KB
testcase_41 AC 269 ms
49,328 KB
testcase_42 AC 104 ms
40,600 KB
testcase_43 AC 114 ms
41,444 KB
testcase_44 AC 108 ms
41,184 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.ArrayList;
import java.util.Scanner;
class MaxFlow {
    private static final class InternalCapEdge {
        final int to;
        final int rev;
        long cap;
        InternalCapEdge(int to, int rev, long cap) { this.to = to; this.rev = rev; this.cap = cap; }
    }
    public static final class CapEdge {
        public final int from, to;
        public final long cap, flow;
        CapEdge(int from, int to, long cap, long flow) { this.from = from; this.to = to; this.cap = cap; this.flow = flow; }
        @Override
        public boolean equals(Object o) {
            if (o instanceof CapEdge) {
                CapEdge e = (CapEdge) o;
                return from == e.from && to == e.to && cap == e.cap && flow == e.flow;
            }
            return false;
        }
    }
    private static final class IntPair {
        final int first, second;
        IntPair(int first, int second) { this.first = first; this.second = second; }
    }

    static final long INF = Long.MAX_VALUE;

    private final int n;
    private final java.util.ArrayList<IntPair> pos;
    private final java.util.ArrayList<InternalCapEdge>[] g;

    @SuppressWarnings("unchecked")
    public MaxFlow(int n) {
        this.n = n;
        this.pos = new java.util.ArrayList<>();
        this.g = new java.util.ArrayList[n];
        for (int i = 0; i < n; i++) {
            this.g[i] = new java.util.ArrayList<>();
        }
    }

    public int addEdge(int from, int to, long cap) {
        rangeCheck(from, 0, n);
        rangeCheck(to, 0, n);
        nonNegativeCheck(cap, "Capacity");
        int m = pos.size();
        pos.add(new IntPair(from, g[from].size()));
        int fromId = g[from].size();
        int toId = g[to].size();
        if (from == to) toId++;
        g[from].add(new InternalCapEdge(to, toId, cap));
        g[to].add(new InternalCapEdge(from, fromId, 0L));
        return m;
    }

    private InternalCapEdge getInternalEdge(int i) {
        return g[pos.get(i).first].get(pos.get(i).second);
    }

    private InternalCapEdge getInternalEdgeReversed(InternalCapEdge e) {
        return g[e.to].get(e.rev);
    }

    public CapEdge getEdge(int i) {
        int m = pos.size();
        rangeCheck(i, 0, m);
        InternalCapEdge e = getInternalEdge(i);
        InternalCapEdge re = getInternalEdgeReversed(e);
        return new CapEdge(re.to, e.to, e.cap + re.cap, re.cap);
    }

    public CapEdge[] getEdges() {
        CapEdge[] res = new CapEdge[pos.size()];
        java.util.Arrays.setAll(res, this::getEdge);
        return res;
    }

    public void changeEdge(int i, long newCap, long newFlow) {
        int m = pos.size();
        rangeCheck(i, 0, m);
        nonNegativeCheck(newCap, "Capacity");
        if (newFlow > newCap) {
            throw new IllegalArgumentException(
                String.format("Flow %d is greater than the capacity %d.", newCap, newFlow)
            );
        }
        InternalCapEdge e = getInternalEdge(i);
        InternalCapEdge re = getInternalEdgeReversed(e);
        e.cap = newCap - newFlow;
        re.cap = newFlow;
    }

    public long maxFlow(int s, int t) {
        return flow(s, t, INF);
    }

    public long flow(int s, int t, long flowLimit) {
        rangeCheck(s, 0, n);
        rangeCheck(t, 0, n);
        long flow = 0L;
        int[] level = new int[n];
        int[] que = new int[n];
        int[] iter = new int[n];
        while (flow < flowLimit) {
            bfs(s, t, level, que);
            if (level[t] < 0) break;
            java.util.Arrays.fill(iter, 0);
            while (flow < flowLimit) {
                long d = dfs(t, s, flowLimit - flow, iter, level);
                if (d == 0) break;
                flow += d;
            }
        }
        return flow;
    }

    private void bfs(int s, int t, int[] level, int[] que) {
        java.util.Arrays.fill(level, -1);
        int hd = 0, tl = 0;
        que[tl++] = s;
        level[s] = 0;
        while (hd < tl) {
            int u = que[hd++];
            for (InternalCapEdge e : g[u]) {
                int v = e.to;
                if (e.cap == 0 || level[v] >= 0) continue;
                level[v] = level[u] + 1;
                if (v == t) return;
                que[tl++] = v;
            }
        }
    }

    private long dfs(int cur, int s, long flowLimit, int[] iter, int[] level) {
        if (cur == s) return flowLimit;
        long res = 0;
        int curLevel = level[cur];
        for (int itMax = g[cur].size(); iter[cur] < itMax; iter[cur]++) {
            int i = iter[cur];
            InternalCapEdge e = g[cur].get(i);
            InternalCapEdge re = getInternalEdgeReversed(e);
            if (curLevel <= level[e.to] || re.cap == 0) continue;
            long d = dfs(e.to, s, Math.min(flowLimit - res, re.cap), iter, level);
            if (d <= 0) continue;
            e.cap += d;
            re.cap -= d;
            res += d;
            if (res == flowLimit) break;
        }
        return res;
    }

    public boolean[] minCut(int s) {
        rangeCheck(s, 0, n);
        boolean[] visited = new boolean[n];
        int[] stack = new int[n];
        int ptr = 0;
        stack[ptr++] = s;
        visited[s] = true;
        while (ptr > 0) {
            int u = stack[--ptr];
            for (InternalCapEdge e : g[u]) {
                int v = e.to;
                if (e.cap > 0 && !visited[v]) {
                    visited[v] = true;
                    stack[ptr++] = v;
                }
            }
        }
        return visited;
    }

    private void rangeCheck(int i, int minInclusive, int maxExclusive) {
        if (i < 0 || i >= maxExclusive) {
            throw new IndexOutOfBoundsException(
                String.format("Index %d out of bounds for length %d", i, maxExclusive)
            );
        }
    }

    private void nonNegativeCheck(long cap, String attribute) {
        if (cap < 0) {
            throw new IllegalArgumentException(
                String.format("%s %d is negative.", attribute, cap)
            );
        }
    }
}
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N];
		for(int i = 0; i < N; i++){
			a[i] = sc.nextInt();
		}
		ArrayList<Integer> odd = new ArrayList<>();
		ArrayList<Integer> even = new ArrayList<>();
		for(int i = 0; i< N; i++){
			if (Integer.bitCount(a[i]) % 2 == 1) odd.add(a[i]);
			else even.add(a[i]);
		}
		int n = odd.size();
		int m = even.size();
		MaxFlow G = new MaxFlow(N + 2);

		for(int i = 0; i < n; i++){
			G.addEdge(0, i + 1, 1);
		}

		for(int i = 0; i < m; i++){
			G.addEdge(i + n + 1, N + 1, 1);
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if (Integer.bitCount(odd.get(i) ^ even.get(j)) == 1){
					G.addEdge(i + 1, n + j + 1, 1);
				}
			}
		}
		int F = (int) G.maxFlow(0, N + 1);
		System.out.println(N - F);



	}
}
0