結果
| 問題 | No.443 GCD of Permutation |
| ユーザー |
 arukuka
|
| 提出日時 | 2016-11-11 23:48:44 |
| 言語 | Java (openjdk 23) |
| 結果 |
WA
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 7,415 bytes |
| コンパイル時間 | 2,699 ms |
| コンパイル使用メモリ | 83,776 KB |
| 実行使用メモリ | 59,564 KB |
| 最終ジャッジ日時 | 2024-11-25 10:42:12 |
| 合計ジャッジ時間 | 10,430 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 2 |
| other | AC * 21 WA * 7 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.math.BigInteger;import java.util.*;import java.util.function.BiFunction;import java.util.function.Function;import java.util.function.Supplier;public class Main {String ch(ArrayList<Character> l) {StringBuilder sb = new StringBuilder();for (char c : l) {sb.append(c);}return sb.toString();}void run() {char[] n = sc.next().toCharArray();ArrayList<Character> l = new ArrayList<>();HashSet<Character> set = new HashSet<>();for (char c : n) {l.add(c);set.add(c);}if (set.size() == 1) {System.out.println(new String(n));return;}if (n.length == 2) {BigInteger a = new BigInteger(new String(n));char tmp = n[0];n[0] = n[1];n[1] = tmp;BigInteger b = new BigInteger(new String(n));System.out.println(a.gcd(b));return;}ArrayList<BigInteger> bl = new ArrayList<>();TreeSet<String> set2 = new TreeSet<>();for (; ; ) {ArrayList<Character> A = new ArrayList<>(l);Collections.shuffle(A);if (set2.contains(ch(A))) {continue;}set2.add(ch(A));bl.add(new BigInteger(ch(A)));if (bl.size() >= 3) {break;}}Collections.sort(bl);BigInteger a = bl.get(0);BigInteger b = bl.get(1);BigInteger c = bl.get(2);debug(a, b, c);BigInteger ba = b.subtract(a);BigInteger cb = c.subtract(b);Arrays.sort(n);BigInteger d = new BigInteger(new String(n));System.out.println(ba.gcd(cb).gcd(d));}Scanner sc = new Scanner(System.in);public static void main(String[] args) {new Main().run();}int ni() {return Integer.parseInt(sc.next());}void debug(Object... os) {System.err.println(Arrays.deepToString(os));}class BIT<T> {int n;ArrayList<T> bit;BiFunction<T, T, T> bif;/*** 1-indexed なBinary Indexed Treeを構築する** @param n 容量* @param bif 適用させる関数* @param sup 初期値*/BIT(int n, BiFunction<T, T, T> bif, Supplier<T> sup) {this.n = n;bit = new ArrayList<>(n + 1);for (int i = 0; i < n + 1; ++i) {bit.add(sup.get());}this.bif = bif;}/*** iの位置の値をvで更新する** @param i index* @param v 新しい値*/void update(int i, T v) {for (int x = i; x <= n; x += x & -x) {bit.set(x, bif.apply(bit.get(x), v));}}/*** クエリー** @param defaultValue 初期値* @param i index* @return [1, i]までfを適用した結果*/T reduce(T defaultValue, int i) {T ret = defaultValue;for (int x = i; x > 0; x -= x & -x) {ret = bif.apply(ret, bit.get(x));}return ret;}}long MOD = 1_000_000_007;/*** 繰り返し2乗法を用いたべき乗の実装** @return a^r (mod 1,000,000,007)*/long pow(long a, long r) {long sum = 1;while (r > 0) {if ((r & 1) == 1) {sum *= a;sum %= MOD;}a *= a;a %= MOD;r >>= 1;}return sum;}/*** 組み合わせ* O(n)** @return {}_nC_r*/long C(int n, int r) {if (n < r) {return 0;}long sum = 1;for (int i = n; 0 < i; --i) {sum *= i;sum %= MOD;}long s = 1;for (int i = r; 0 < i; --i) {s *= i;s %= MOD;}sum *= pow(s, MOD - 2);sum %= MOD;long t = 1;for (int i = n - r; 0 < i; --i) {t *= i;t %= MOD;}sum *= pow(t, MOD - 2);sum %= MOD;return sum;}double GOLDEN_RATIO = (1.0 + Math.sqrt(5)) / 2.0;/*** 黄金分割探索** @param left 下限* @param right 上限* @param f 探索する関数* @param comp 上に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue)* 下に凸な関数を探索するときは、Comparator.comparingDouble(Double::doubleValue).reversed()* @return 極値の座標x*/double goldenSectionSearch(double left, double right, Function<Double, Double> f, Comparator<Double> comp) {double c1 = divideInternally(left, right, 1, GOLDEN_RATIO);double c2 = divideInternally(left, right, GOLDEN_RATIO, 1);double d1 = f.apply(c1);double d2 = f.apply(c2);while (right - left > 1e-9) {if (comp.compare(d1, d2) > 0) {right = c2;c2 = c1;d2 = d1;c1 = divideInternally(left, right, 1, GOLDEN_RATIO);d1 = f.apply(c1);} else {left = c1;c1 = c2;d1 = d2;c2 = divideInternally(left, right, GOLDEN_RATIO, 1);d2 = f.apply(c2);}}return right;}/*** [a,b]をm:nに内分する点を返す*/double divideInternally(double a, double b, double m, double n) {return (n * a + m * b) / (m + n);}long gcd(long a, long b) {if (b == 0) {return a;}return gcd(b, a % b);}int gcd(int a, int b) {if (b == 0) {return a;}return gcd(b, a % b);}long lcd(long a, long b) {return (a / gcd(a, b)) * b;}int lcd(int a, int b) {return (a / gcd(a, b)) * b;}/*** http://qiita.com/p_shiki37/items/65c18f88f4d24b2c528b*/static class FastScanner {private final InputStream in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;public FastScanner(InputStream in) {this.in = in;}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();}}}}