結果
問題 | No.470 Inverse S+T Problem |
ユーザー | ぴろず |
提出日時 | 2016-12-19 05:31:44 |
言語 | Java21 (openjdk 21) |
結果 |
WA
|
実行時間 | - |
コード長 | 7,468 bytes |
コンパイル時間 | 2,566 ms |
コンパイル使用メモリ | 80,508 KB |
実行使用メモリ | 204,764 KB |
最終ジャッジ日時 | 2024-12-22 13:07:28 |
合計ジャッジ時間 | 22,212 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 56 ms
42,200 KB |
testcase_01 | WA | - |
testcase_02 | AC | 56 ms
42,160 KB |
testcase_03 | AC | 56 ms
167,636 KB |
testcase_04 | AC | 55 ms
42,188 KB |
testcase_05 | AC | 57 ms
170,644 KB |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
testcase_09 | AC | 58 ms
36,700 KB |
testcase_10 | AC | 62 ms
37,452 KB |
testcase_11 | AC | 86 ms
38,816 KB |
testcase_12 | AC | 58 ms
37,068 KB |
testcase_13 | AC | 62 ms
37,312 KB |
testcase_14 | AC | 86 ms
38,472 KB |
testcase_15 | WA | - |
testcase_16 | AC | 60 ms
37,124 KB |
testcase_17 | AC | 63 ms
36,948 KB |
testcase_18 | AC | 62 ms
37,604 KB |
testcase_19 | WA | - |
testcase_20 | AC | 57 ms
37,000 KB |
testcase_21 | AC | 81 ms
38,540 KB |
testcase_22 | AC | 82 ms
38,648 KB |
testcase_23 | AC | 86 ms
38,736 KB |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | TLE | - |
testcase_29 | WA | - |
testcase_30 | TLE | - |
ソースコード
package invsplust; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.InputMismatchException; import java.util.NoSuchElementException; public class Main { public static void main(String[] args) { IO io = new IO(); int n = io.nextInt(); String[] u = new String[n]; for(int i=0;i<n;i++) { u[i] = io.next(); } solve(n,u,io); } public static void solve(int n, String[] u, PrintWriter io) { //右側で分割するのを真とする TwoSAT ts = new TwoSAT(n); for(int i=0;i<n;i++) { String u1 = u[i]; for(int j=i+1;j<n;j++) { String u2 = u[j]; for(int k=0;k<4;k++) { //2つの文字列の分割の方法2^2=4通り int l1 = (k >> 1) & 1; int l2 = k & 1; String s1 = u1.substring(0, l1 + 1); String t1 = u1.substring(l1 + 1, 3); String s2 = u2.substring(0, l2 + 1); String t2 = u2.substring(l2 + 1, 3); //(3文字なのでs1=t1やs2=t2はありえない) if (s1.equals(s2) || s1.equals(t2) || t1.equals(s2) || t1.equals(t2)) { //ダメなのでこの分割をしたとき0になるような節を追加する ts.addClause(l1 == 0, i, l2 == 0, j); } } } } boolean[] right = ts.solve(); if (right == null) { io.println("Impossible"); return; } for(int i=0;i<n;i++) { int len = right[i] ? 2 : 1; String s = u[i].substring(0, len); String t = u[i].substring(len, 3); io.print(s); io.print(' '); io.println(t); } io.flush(); } } class TwoSAT { int n; SCC graph; public TwoSAT(int n) { this.n = n; graph = new SCC(n * 2); //¬x0, ..., ¬xn, x0, ..., xn } //(¬x0 ∨ x1) -> (false, 0, true, 1) public void addClause(boolean tf1, int x1, boolean tf2, int x2) { // System.out.println((tf1 ? "" : "¬") + x1 + "∨" + (tf1 ? "" : "¬") + x2); graph.addEdge(x1 + (tf1 ? 0 : n), x2 + (tf2 ? n : 0)); //¬x1 -> x2 graph.addEdge(x2 + (tf2 ? 0 : n), x1 + (tf1 ? n : 0)); //¬x2 -> x1 } //充足不可能なときnull, そうでなければ真偽の割り当て public boolean[] solve() { graph.scc(); int[] order = graph.order; boolean[] res = new boolean[n]; for(int i=0;i<n;i++) { if (order[i] == order[i+n]) { return null; } if (order[i+n] > order[i]) { res[i] = true; } } return res; } } class SCC { int n; ArrayList<Integer>[] graph; //グラフ ArrayList<Integer>[] rgraph; //逆辺からなるグラフ ArrayList<Integer> vertices; //帰りがけ順に頂点を並べる boolean[] used; int[] order; //強連結成分のトポロジカル順序 int sccNum; @SuppressWarnings("unchecked") public SCC(int n) { this.n = n; graph = new ArrayList[n]; rgraph = new ArrayList[n]; for(int i=0;i<n;i++) { graph[i] = new ArrayList<>(); rgraph[i] = new ArrayList<>(); } } public void addEdge(int from,int to) { // System.out.println(from + "->" + to); graph[from].add(to); rgraph[to].add(from); } private void dfs(int v) { used[v] = true; for(int u: graph[v]) { if (!used[u]) { dfs(u); } } vertices.add(v); } private void rdfs(int v, int k) { used[v] = true; order[v] = k; for(int u: rgraph[v]) { if (!used[u]) { rdfs(u, k); } } } public void scc() { used = new boolean[n]; order = new int[n]; vertices = new ArrayList<>(); sccNum = 0; for(int i=0;i<n;i++) { if (!used[i]) { dfs(i); } } Arrays.fill(used, false); for(int i=vertices.size()-1;i>=0;i--) { int v = vertices.get(i); if (!used[v]) { rdfs(v, sccNum++); } } } //scc()の後に呼び出して強連結成分をトポロジカル順序で返す @SuppressWarnings("unchecked") public ArrayList<Integer>[] restoreSCCs() { ArrayList<Integer>[] res = new ArrayList[sccNum]; for(int i=0;i<sccNum;i++) { res[i] = new ArrayList<>(); } for(int i=0;i<n;i++) { res[order[i]].add(i); } return res; } } class IO extends PrintWriter { private final InputStream in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; public IO() { this(System.in);} public IO(InputStream source) { super(System.out); this.in = source;} 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 static boolean isNewLine(int c) { return c == '\n' || c == '\r';} public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();} public boolean hasNextLine() { while(hasNextByte() && isNewLine(buffer[ptr])) ptr++; 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 char[] nextCharArray(int len) { if (!hasNext()) { throw new NoSuchElementException(); } char[] s = new char[len]; int i = 0; int b = readByte(); while(isPrintableChar(b)) { if (i == len) { throw new InputMismatchException(); } s[i++] = (char) b; b = readByte(); } return s; } public String nextLine() { if (!hasNextLine()) { throw new NoSuchElementException(); } StringBuilder sb = new StringBuilder(); int b = readByte(); while(!isNewLine(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() { long nl = nextLong(); if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i<n;i++) a[i] = nextInt(); return a;} public long[] nextLongArray(int n) { long[] a = new long[n]; for(int i=0;i<n;i++) a[i] = nextLong(); return a;} public double[] nextDoubleArray(int n) { double[] a = new double[n]; for(int i=0;i<n;i++) a[i] = nextDouble(); return a;} public void nextIntArrays(int[]... a) { for(int i=0;i<a[0].length;i++) for(int j=0;j<a.length;j++) a[j][i] = nextInt();} public int[][] nextIntMatrix(int n,int m) { int[][] a = new int[n][]; for(int i=0;i<n;i++) a[i] = nextIntArray(m); return a;} public char[][] nextCharMap(int n,int m) { char[][] a = new char[n][]; for(int i=0;i<n;i++) a[i] = nextCharArray(m); return a;} public void close() { super.close(); try {in.close();} catch (IOException e) {}} }