結果
問題 |
No.3173 じゃんけんの勝ちの回数
|
ユーザー |
|
提出日時 | 2025-05-23 08:06:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 468 ms / 2,000 ms |
コード長 | 5,273 bytes |
コンパイル時間 | 3,344 ms |
コンパイル使用メモリ | 86,908 KB |
実行使用メモリ | 62,996 KB |
最終ジャッジ日時 | 2025-05-23 08:07:02 |
合計ジャッジ時間 | 19,687 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 33 |
ソースコード
import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.NoSuchElementException; import java.util.Queue; import java.util.Random; public class Main implements Runnable { //Runnableを実装する public static void main(String[] args) { new Thread(null, new Main(), "", 1024 * 1024 * 1024).start(); } final long mod=(long)998244353; int MAX=200010; long[]fac=new long[MAX]; long[]ifac=new long[MAX]; long[]inv=new long[MAX]; { Arrays.fill(fac, 1); Arrays.fill(ifac, 1); Arrays.fill(inv, 1); for(int i=2;i<MAX;++i) { fac[i]=i*fac[i-1]%mod; inv[i]=mod-(mod/i)*inv[(int)(mod%i)]%mod; ifac[i]=inv[i]*ifac[i-1]%mod; } } long comb(int n, int k) { if(k<0||n-k<0)return 0; return fac[n]*ifac[k]%mod*ifac[n-k]%mod; } public void run() { FastScanner sc = new FastScanner(); Random rnd=new Random(); PrintWriter pw=new PrintWriter(System.out); int T=sc.nextInt(); for(int t=0;t<T;++t) { long[]A=new long[3]; long[]B=new long[3]; for(int i=0;i<3;++i) { A[i]=sc.nextLong(); } for(int i=0;i<3;++i) { B[i]=sc.nextLong(); } long all=Arrays.stream(A).sum(); long max=0; for(int i=0;i<3;++i) { max+=Math.min(A[i], B[(i+1)%3]); } MaxFlow mf=new MaxFlow(8); int source=6; int sink=7; for(int i=0;i<3;++i) { mf.setCap(source, i, A[i]); mf.setCap(i+3, sink, B[i]); } long INF=100000000; for(int i=0;i<3;++i) { for(int j=0;j<3;++j) { if(j!=(i+1)%3) { mf.setCap(i, j+3, INF); } } } long min=all-mf.get(source, sink); pw.println(min+" "+max); } pw.close(); } static void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } class MaxFlow { class Edge { int v; int cap; int flow; } int n; long[][] cap; long[][] flw; ArrayList<Integer>[] g; @SuppressWarnings("unchecked") public MaxFlow(int n) { this.n = n; cap = new long[n][n]; flw = new long[n][n]; g = new ArrayList[n]; Arrays.setAll(g, i -> new ArrayList<>()); } void setCap(int u, int v, long a) { cap[u][v] += a; } long res(int u, int v) { return cap[u][v] - flw[u][v] + flw[v][u]; } int[] d; int[] itr; int s, t; int get(int s, int t) { if (s == t) return 0; this.s = s; this.t = t; for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { if (cap[i][j] != 0 || cap[j][i] != 0) { g[i].add(j); g[j].add(i); } } } int ans = 0; while (true) { Queue<Integer> que = new ArrayDeque<>(); que.add(s); d = new int[n]; itr = new int[n]; Arrays.fill(d, n + 1); d[s] = 0; while (!que.isEmpty()) { int v = que.poll(); for (int u : g[v]) { if (d[u] == n + 1 && res(v, u) != 0) { d[u] = d[v] + 1; que.add(u); } } } if (d[t] == n + 1) break; while (true) { long add = dfs(s, Integer.MAX_VALUE); ans += add; if (add == 0) break; } } return ans; } long dfs(int v, long upper) { if (v == t) return upper; while (itr[v] < g[v].size()) { int nv = g[v].get(itr[v]); itr[v]++; if (res(v, nv) != 0 && d[nv] == d[v] + 1) { long add = dfs(nv, Math.min(upper, res(v, nv))); if (add != 0) { long x = Math.min(add, cap[v][nv] - flw[v][nv]); add -= x; flw[v][nv] += x; flw[nv][v] -= add; return add + x; } } } return 0; } } } class FastScanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } public int nextInt() { return (int) nextLong(); } }