結果
問題 | No.470 Inverse S+T Problem |
ユーザー |
|
提出日時 | 2016-12-28 12:32:44 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 182 ms / 2,000 ms |
コード長 | 6,443 bytes |
コンパイル時間 | 4,376 ms |
コンパイル使用メモリ | 81,176 KB |
実行使用メモリ | 48,568 KB |
最終ジャッジ日時 | 2024-12-22 13:39:41 |
合計ジャッジ時間 | 7,405 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 27 |
ソースコード
import java.io.*;import java.util.*;public class Main_yukicoder470 {private static Scanner sc;private static Printer pr;private static void solve() {int n = sc.nextInt();char[][] u = new char[n][];for (int i = 0; i < n; i++) {u[i] = sc.next().toCharArray();}if (n > 52) {pr.println("Impossible");return;}V = n * 2;edges = new ArrayList<>();redges = new ArrayList<>();for (int i = 0; i < V; i++) {edges.add(new ArrayList<>());redges.add(new ArrayList<>());}vs = new ArrayList<>();used = new boolean[V];cmp = new int[V];for (int i = 0; i < n; i++) {for (int j = i + 1; j < n; j++) {if (u[i][0] == u[j][0]) {add_edge(i, j + n);add_edge(j, i + n);}if (u[i][1] == u[j][1] && u[i][2] == u[j][2]) {add_edge(i, j + n);add_edge(j, i + n);}if (u[i][2] == u[j][2]) {add_edge(i + n, j);add_edge(j + n, i);}if (u[i][0] == u[j][0] && u[i][1] == u[j][1]) {add_edge(i + n, j);add_edge(j + n, i);}if (u[i][0] == u[j][2]) {add_edge(i, j);add_edge(j + n, i + n);}if (u[i][1] == u[j][0] && u[i][2] == u[j][1]) {add_edge(i, j);add_edge(j + n, i + n);}if (u[i][2] == u[j][0]) {add_edge(i + n, j + n);add_edge(j, i);}if (u[i][0] == u[j][1] && u[i][1] == u[j][2]) {add_edge(i + n, j + n);add_edge(j, i);}}}int k = scc();for (int i = 0; i < n; i++) {if (cmp[i] == cmp[i + n]) {pr.println("Impossible");return;}}for (int i = 0; i < n; i++) {if (cmp[i] > cmp[i + n]) {pr.printf("%c %c%c\n", u[i][0], u[i][1], u[i][2]);} else {pr.printf("%c%c %c\n", u[i][0], u[i][1], u[i][2]);}}// pr.printf("%.10f\n", ret);}private static int V;private static List<List<Integer>> edges;private static List<List<Integer>> redges;private static List<Integer> vs;private static boolean[] used;private static int[] cmp;private static void add_edge(int from, int to) {edges.get(from).add(to);redges.get(to).add(from);}private static void dfs(int v) {used[v] = true;for (int e : edges.get(v)) {if (!used[e]) {dfs(e);}}vs.add(v);}private static void rdfs(int v, int k) {used[v] = true;cmp[v] = k;for (int e : redges.get(v)) {if (!used[e]) {rdfs(e, k);}}vs.add(v);}private static int scc() {Arrays.fill(used, false);vs.clear();for (int v = 0; v < V; v++) {if (!used[v]) {dfs(v);}}Arrays.fill(used, false);int k = 0;for (int i = vs.size() - 1; i >= 0; i--) {if (!used[vs.get(i)]) {rdfs(vs.get(i), k++);}}return k;}// ---------------------------------------------------public static void main(String[] args) {sc = new Scanner(System.in);pr = new Printer(System.out);solve();pr.close();sc.close();}@SuppressWarnings("unused")private static class Scanner {BufferedReader br;Scanner (InputStream in) {br = new BufferedReader(new InputStreamReader(in));}private boolean isPrintable(int ch) {return ch >= '!' && ch <= '~';}private boolean isCRLF(int ch) {return ch == '\n' || ch == '\r' || ch == -1;}private int nextPrintable() {try {int ch;while (!isPrintable(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}return ch;} catch (IOException e) {throw new NoSuchElementException();}}String next() {try {int ch = nextPrintable();StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (isPrintable(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}int nextInt() {try {// parseInt from Integer.parseInt()boolean negative = false;int res = 0;int limit = -Integer.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Integer.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}int multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}long nextLong() {try {// parseLong from Long.parseLong()boolean negative = false;long res = 0;long limit = -Long.MAX_VALUE;int radix = 10;int fc = nextPrintable();if (fc < '0') {if (fc == '-') {negative = true;limit = Long.MIN_VALUE;} else if (fc != '+') {throw new NumberFormatException();}fc = br.read();}long multmin = limit / radix;int ch = fc;do {int digit = ch - '0';if (digit < 0 || digit >= radix) {throw new NumberFormatException();}if (res < multmin) {throw new NumberFormatException();}res *= radix;if (res < limit + digit) {throw new NumberFormatException();}res -= digit;} while (isPrintable(ch = br.read()));return negative ? res : -res;} catch (IOException e) {throw new NoSuchElementException();}}float nextFloat() {return Float.parseFloat(next());}double nextDouble() {return Double.parseDouble(next());}String nextLine() {try {int ch;while (isCRLF(ch = br.read())) {if (ch == -1) {throw new NoSuchElementException();}}StringBuilder sb = new StringBuilder();do {sb.appendCodePoint(ch);} while (!isCRLF(ch = br.read()));return sb.toString();} catch (IOException e) {throw new NoSuchElementException();}}void close() {try {br.close();} catch (IOException e) {// throw new NoSuchElementException();}}}private static class Printer extends PrintWriter {Printer(PrintStream out) {super(out);}}}